Interview Question
Country: United States
I would divide the answer on two parts.
At first, we need to count how many 3-digit numbers can be made using 1, 2, 3, 4 or 5. It is obvious that on every digit we can use every number, so 3 digits, 5 numbers: 5*5*5 = 125 different 3-digit numbers. But those numbers can have even number repetitions, like 223 or 444.
So secondly, we need to count number of such 3-digit numbers with repetitions of 2 and 4. We can see, that for this case 22X it is possible to have 5 numbers, as well as for this case 2X2, and for this case X22. That way we have 3*5 combinations for '2' and 3*5 for '4'.
That way we have the answer: 5*5*5 - 3*5 - 3*5 = 125 - 15 - 15 = 95.
222 gets counted three times instead of only once (22X, 2X2, X22). Same for 444 in your solution. If you adjust for that, you get 99 as well.
A simple solution in Java
public static void main(String[] args){
//1
int[] dictionary = {1, 2, 3, 4, 5};
boolean[] unique = new boolean[dictionary.length];
for (int i = 0 ; i < dictionary.length; i++)
unique[i] = false;
int digit = 3;
PermMod("", digit, dictionary, unique, 0);
}
private static void PermMod(String solution, int digit, int[] dictionary, boolean[] unique, int sLength) {
if (sLength == digit){
System.out.println(solution);
return;
}
for (int i = 0; i < dictionary.length; i++){
if (unique[i])
continue;
if (dictionary[i]%2 == 0){
unique[i] = true;
PermMod(solution+" "+dictionary[i], digit, dictionary, unique, sLength+1 );
unique[i] = false;
}else{
PermMod(solution+" "+dictionary[i], digit, dictionary, unique, sLength+1);
}
}
}
}
If I understand the question correctly, we allow 1,3,5 to be repeated, but 2 and 4 not. Then we can solve it like this. Divide all possible triples into four non-intersecting classes 0 through 3 by the number of odd digits and count the number of triples in each class:
- Sasha Pachev February 25, 2014class 0 - empty because you cannot make a 3-digit number out of just 2 and 4 without one of them repeating
class 1 - we have one odd digit and two even. This divides into three non-intersecting sub-classes by picking the position of the odd digit. In each of those classes we can pick the odd digit in 3 different ways, and once we have done that we have to have both 2 and 4, and we can only pick their order out of 2 possibilities. So class 1 has 3*3*2 = 18 triples.
class 2 - two odd and one even. There are three picks for the position of the even digit. Once the position is chosen, the odd digits to fill the other two can be chosen in 3^2 = 9 different ways. Additionally there are 2 ways to pick the even digit for the position. So we have 3*9*2 = 54 triples.
class 3 - all digits are odd. So 3^3 = 27.
Adding up the number of elements in each class, we get the answer of 0 + 18 + 54 + 27 = 99.