-4

Ok, so I was wondering how can one check whether two numbers have the same digits, e.g. 21 and 12 are ok, also 1233 and 2313, but 123 and 1233 are not, meaning that the digits are permutation of another number's digits.

I know how to do it with arrays or strings or maps, but the problem is, that I don't want to do it with either of those, if there exists another solution.

The solution with arrays / maps:

Map<int, int> counter = new HashMap<int, int>();
for (int i = 0; i < 10; i++)
    counter.put(i, 0);
int x = 2421, y = 4223; // testcase
while (x > 0 || y > 0) {
    if (x == 0 || y == 0) // if they are not the same length, one will be 0 and thus they are not permutations
        return false;
    counter.put(x%10, counter.get(x%10) + 1);
    counter.put(y%10, counter.get(y%10) - 1);
    x /= 10;
    y /= 10;
}
// For each digit we added 1 to the counter if it was found in `x`
// and subtract 1 if it was found in `y`.
return counter.values() == [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

Now, the array approach is completely the same, since using a map for digits 0-9 is the same as using the key for map as the index in array. The solution without any data structure looks far from ideal to me:

private static boolean haveSameDigits(int x, int y) {
    // Because we are not allowed to use maps, declare 10 vars...
    int c0 = 0;
    int c1 = 0;
    int c2 = 0;
    int c3 = 0;
    int c4 = 0;
    int c5 = 0;
    int c6 = 0;
    int c7 = 0;
    int c8 = 0;
    int c9 = 0;

    while (x > 0 || y > 0) {
      if (x == 0 || y == 0)
          return false;
      if ((x % 10) == 0)
          c0++;
      else if ((x % 10) == 1)
          c1++;
      else if ((x % 10) == 2)
          c2++;
      else if ((x % 10) == 3)
          c3++;
      else if ((x % 10) == 4)
          c4++;
      else if ((x % 10) == 5)
          c5++;
      else if ((x % 10) == 6)
          c6++;
      else if ((x % 10) == 7)
          c7++;
      else if ((x % 10) == 8)
          c8++;
      else if ((x % 10) == 9)
          c9++;
      if ((y % 10) == 0)
          c0--;
      else if ((y % 10) == 1)
          c1--;
      else if ((y % 10) == 2)
          c2--;
      else if ((y % 10) == 3)
          c3--;
      else if ((y % 10) == 4)
          c4--;
      else if ((y % 10) == 5)
          c5--;
      else if ((y % 10) == 6)
          c6--;
      else if ((y % 10) == 7)
          c7--;
      else if ((y % 10) == 8)
          c8--;
      else if ((y % 10) == 9)
          c9--;

      x /= 10;
      y /= 10;
    }

    return c0 == 0 && c1 == 0 && c2 == 0 && c3 == 0 && c4 == 0 && c5 == 0 && c6 == 0 && c7 == 0 && c8 == 0 && c9 == 0
}

I have googled about it but no matter what I typed I ended up with a solution using strings or arrays.

I am not looking for a solution, I actually don't want it, I just need a hint to the approach.

Adding some more information: There is nothing prohibiting me from using any data structure I want, this is my program and nobody will be checking over what I do. I am just that kind of person that likes to learn new stuff, so I was wondering if there is a quick solution to it.

As stated in the comments, one can iterate over both numbers and check for each number in range (0,9) inclusive, how many times they appear in string but that obviously yields time complexity of O(n*n) which is not optimal.

Sam Hanley
  • 4,707
  • 7
  • 35
  • 63
campovski
  • 2,979
  • 19
  • 38

2 Answers2

2

You do not want to convert to string, or to use any helper data structures. How about this then: Create a hash from the numbers, in the form xor(2^d for every digit d in n)?

For example, hash(3112) will be (in binary) 1100.

Since you do not want a solution, here's some pseudocode (aka Python):

def hash(n):
    r = 0
    while n > 0:
        d = n % 10    # last digit
        n = n // 10   # remaining digits
        r = r ^ 2**d  # xor with 2^d
    return r

def perm(n, m):
    return hash(n) == hash(m)

Update: Turns out that the above does not work properly, as XOR can only keep track of whether a digit appears an even or odd number of times. Instead, you could create a hash using multiples of prime numbers. This way, hash(3112) becomes 7 * 3 * 3 * 5. While this uses a list to keep the first ten prime numbers, it does not create any new lists, arrays or maps while checking individual pairs of numbers. Also, keep in mind that the resulting hash might get very large -- larger than Java's int or long types. (You can probably take the modulo of another large prime number, but I'm not sure about that part.)

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
def hash(n):
    r = 1
    while n > 0:
        d = n % 10   # last digit
        n = n // 10  # remaining digits
        r = r * primes[d]
    return r
tobias_k
  • 81,265
  • 12
  • 120
  • 179
  • Now this looks like something I was looking for! – campovski Nov 11 '17 at 14:50
  • Ah, no, wait, that does not work correctly... this will recognize numbers as permutations if every same digit appears either an even or odd number of times. E.g., it would return `True` for `3` and `333`... leaving this here for now, maybe it helps someone else come up with a full solution. – tobias_k Nov 11 '17 at 14:53
  • Yep, indeed, well spotted! Might be something out of it... I was trying with bitwise and and xor combination too, but didn't get to a point where I would say that that solution truly works for all possible cases – campovski Nov 11 '17 at 15:02
0

You can parse int's to strings and check with .contains

final List<Integer> intsForCheck = new ArrayList<>();

for (int i = 1; i < 180; i++)
    intsForCheck.add(i);

final int num = 17;
intsForCheck.forEach(integer -> check(integer,num));


public static void check(int integer,int num)
{
    final String _int = String.valueOf(integer);
    final String _num = String.valueOf(num);

    System.out.println(_int + (_int.contains(_num) ? " contains" : " not contains") + _num);
}
SapLalo
  • 43
  • 7