How to check if 2 numbers have same digits and length?

Question

The following code snippets are 2 algorithms I have written to ascertain if 2 numbers have the same digits and length. For example:

• 12 & 21 have same digits and same length, so the output will be true
• 12 & 121 have same digits but not same length, so the output will be false

If anything is not clear, please comment and I will add more details.

Is there a better way to do this check? Better in any aspect: efficiency (time and/or space), code readability, corner cases handling etc. For example, the first approach has the risk of integer overflow but could be an OK approach as long as the numbers are not large, because the time-complexity is linear. Appreciate the feedback.

1. Hash with primes:

• in this approach, we're using a static array of 1st 10 prime numbers as a helper structure

• we then compute hash numbers for both input-numbers using the prime numbers array

• if value of both hash is same, implies the numbers have same digits and length

  public static boolean haveSameDigitsAndLengthPrimes(int a, int b) {
      int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
      int hashA=1, hashB=1;
      while (a > 0) {
          hashA *= primes[a%10];
          a /= 10;
      }
      while (b > 0) {
          hashB *= primes[b%10];
          b /= 10;
      }
      return (hashA == hashB);
  }
  

2. Count digits approach:

• in this approach, we're using a helper array of size 10 (initial value of each element = 0)

• we then iterate on both the numbers; while doing so, increment the array digit by 1 for first number and decrement by 1 for second number

• after the iteration if any of the number is still not zero, implies their length is not the same

• if any value in the helper array is not equal to 0, implies the 2 numbers are not satisfying the required conditions

  public static boolean haveSameDigitsAndLength(int a, int b) {
      int[] digits = new int[10];
      for (int i=a; i>0; i=i/10) {
          ++digits[i%10];
      }
      for (int i=b; i>0; i=i/10) {
          --digits[i%10];
      }
      for (int digit : digits) {
          if (digit != 0) {
              return false;
          }
      }
      return true;
  }
  

  2b. Count digits approach: implementation improved:

  public static boolean haveSameDigitsAndLength(int a, int b) {
      if ((a == 0 || b == 0) && a != b) {
          return false;
      }
      int[] digits = new int[10];
      int i=a, j=b;
      for (; i>0 && j>0; i/=10, j/=10) {
          ++digits[i%10];
          --digits[j%10];
      }
      if (i != 0 || j != 0) {
          return false;
      }
      for (int digit : digits) {
          if (digit != 0) {
              return false;
          }
      }
      return true;
  }
  

Test Cases:

• 12, 12 => true
• 12, 21 => true
• 123, 132 => true
• 123, 1234 => false
• 10, 1 => false

Solution 1

I am talking about second approach. You can remove one loop by merging first two loops.

bool TestEqual(int a, int b) {
    int cnts[10] = {0}, i = a, j = b;
    for (; i && j; i /= 10, j /= 10) {
        cnts[i % 10]++;
        cnts[j % 10]--;
    }
    return !i && !j; 
    for (i = 0; i < 10; ++i) {
        if (cnts[i] != 0) break;
    }
    return i == 10;
}

My code in C++, but you understand the logic. There are at least two benefits over your approach.

1. You will iterate only for the minimum length of two ints.
2. If lengths do not match, you should not check counts of digits.
3. Remove one loop.

Solution 2

I can suggest some other minor optimization that improve space, time...readability is simple. Assuming base 10(decimal numbers)!

1) Do the digit count check first. The chance of two random numbers having the same digit lengths is small. If you have a fast DigitCheck method this is not time consuming. 2) Remove the use of arrays. I use two variables as bit fields. I encode the frequencies of each digit [0,..,9] in each number using a simple bit-shifting approach. 3) As a result of only using 2 bit-fields I only need to do one comparison to confirm all the frequencies are or are not the same! In psuedo-code:

ulong encode += 1 << (LeastSignificantDigit(number) * 6)    // number % 10

I chose the multiplier 6 as 6 bits can safely hold the maximum frequency of any digit in a ulong.

public static bool IsDigitAnagram( this ulong a, ulong b )
{
    // CHECK equality of digit counts.
    if( Digits( a ) == Digits( b ) )
    {
        // CALCULATE the frequency of digits in each number.
        ulong encodeA = 0;
        ulong encodeB = 0;
        while( a != 0 )
        {
            encodeA += 1UL << ( ( int )LeastSignificantDigit( a ) * 6 );  // a % 10;
            a = ShiftRight( a );                                          // a /= 10;
            encodeB += 1UL << ( ( int )LeastSignificantDigit( b ) * 6 ); 
            b = ShiftRight( b );
        }
        // CONFIRM if the digit frequencies are identical in which case they are anagrams of each other.
        return ( encodeA == encodeB );
    }
    return ( false );
}

Comments

[arbuthnott]

doesn't method 1 return equal if inputs just have the same digits, like 23 and 32?

[Sachin Lala]

Sorry I should've added the test-cases earlier. Now I did. Hope this clarifies.

[Matt Timmermans]

Can add if (a%9 != b%9) return false at the start

[Koray]

First thing came to my mind was int.ToString().Lenght comparison, but I'm sure it is not what you want :)

[Sachin Lala]

This is helpful - thanks @abdullah. I have made the improvements in #2 Java implementation. Will await more suggestions before accepting the answer.

[Thymine]

Looks like one must remove return !i && !j; for this to work?

[MARS]

However the code does not work, you can do the test with numbers 8 and 218, from a logical point of view you can understand why