Adobe Interview Question
Country: United States
As @@@@@@@ said, checking against {2, 3, 6}, {2, 4, 8}, {3, 4, 6, 8} will suffice because {2, 3, 4, 6} and {2, 3, 6, 9} are supersets of {2, 3, 6}
2348 would have 2,3,4,8,6,12,32,24,96,192 which are all unique and hence number is valid even though 2,4,8 is a subset
2348 would have 2, 3, 4, 8, 2*3, 2*4, ....
as you can see 8 comes twice, and hence 2348 is not valid
Read the question again and see the way the products are being formed b4 downvoting a comment!
First thing which should be done is make a set of all digits in the number.
- anotherguy October 13, 2013Case 1. If any digit is present twice in the set, then our number is not valid.
Case 2. If the digit 1 is present, then it is not valid.
Case 3. If all digits are unique and 1 is not present, then there must be two subsets, say {d1, d2,.. dk} and {e1, e2, .. el} s.t.
d1*d2*..dk = e1*e2*...el
If some of the digits on both sides are the same, then remove them from both. So we have two non-intersecting subsets such that
d1*d2*..*dk = e1*e2*..*el
Suppose the digit 7 is present on either side. Then the other side should also have 7 as a factor, which is not possible(because 7 cannot be repeated and no other digit is divisible by 7). Same thing with 5.
So both sides can only have 2 and 3 as prime factors. Let us enumerate all such possible cases:
2*3 = 6
2*4 = 8
2*6 = 3*4
2*8 = No other combo
2*9 = 3*6
3*4 = 2*6
3*6 = 2*9
3*8 = 4*6
3*9 = No other combo
4*6 = 3*8
4*8 = No other combo
4*9 = No other combo
6*8 = No other combo
6*9 = No other combo
8*9 = No other combo
So a number is invalid if
1. Digits repeat
2. The digit 1 is present
3. Any one of these is a subset of the digits: {2, 3, 6}, {2, 4, 8}, {2, 3, 4, 6}, {2, 3, 6, 9}, {3, 4, 6, 8}