java - How to improve: Given two integers, return the number of digits that they share -

i received question during interview, question

given 2 integers, return number of digits share.

for example 129 , 431 return 1 - both share digit 1, no other digit. 95 , 780 return 0, since none of integers overlap.

my thoughts iterate through digits, store them hashtable , check .containskey.

my java solution:

public int commondigits(int x, int y) {      int count = 0;      hashtable<integer, string> ht = new hashtable<integer, string>();       while (x != 0) {           ht.put(x % 10, "x");          x /= 10;      }       while (y != 0) {          if ((ht.containskey(y % 10)) {              count++;          }          y /= 10;      }      return count; } 

but takes o(n) space , o(n + m) time, anyways can improve this?

why not use simple bit fiddling? 

public int commondigits(int x, int y) {   int dx = 0;   while (x != 0) {     dx |= 1 << (x % 10);     x /= 10;   }   int count = 0;   while (y != 0) {     int mask = 1 << (y % 10);     if ((dx & mask) != 0) {       count ++;       dx &= ~mask;     }     y /= 10;   }   return count; } 

this sets corresponding bit in dx for each digit in x. in second loop, each digit in x, code checks whether has entry in dx. if so, it's counted , bit reset avoid double-counting (note missing in code, consider 123 , 141). doesn't use additional storage (dx , count bytes if matters).

note don't need hashtable in solution -- use hasset or bitset..

your code translated using bitset double-counting problem fixed:

public int commondigits(int x, int y) {   int count = 0;   bitset ht = new bitset();    while (x != 0) {       ht.set(x % 10, true);      x /= 10;   }   while (y != 0) {      if ((ht.get(y % 10)) {          count++;          ht.set(y % 10, false);      }      y /= 10;   }   return count; } 

both snippets work same way, latter has more overhead bitset (and embedded array) instance.

this article shows why bitset better boolean array in general case: http://chrononsystems.com/blog/hidden-evils-of-javas-byte-array-byte

edit:

if counting same digit multiple times desired (was not clear examples in question), use int array store counts:

public int commondigits(int x, int y) {   int count = 0;   int[] digits = new int[10];    while (x != 0) {       digits[x % 10]++;      x /= 10;   }   while (y != 0) {      if (digits[x % 10] > 0) {          count++;          digits[x % 10]--;      }      y /= 10;   }   return count; }