gourahari.das
BAN USER1. First sum up all numbers from 1 thru 100. Lets say its SUM.
2. Loop thru the input array. Substract each item from SUM.
You will have the missing number in SUM finally.
public static void main(String[] args) {
int input[] = { 2, 3, 4, 5, 6, 7, 8, 9, 28, 29, 30, 10, 11, 12, 13, 18,
44, 45, 74, 75, 76, 77, 21, 22, 78, 79, 80, 19, 20, 23, 24, 25,
26, 27, 31, 1, 32, 33, 34, 35, 36, 50, 51, 52, 53, 62, 63, 64,
70, 71, 85, 86, 87, 54, 37, 95, 96, 92, 93, 38, 99, 100, 83,
84, 17, 90, 91, 41, 39, 40, 97, 46, 66, 67, 68, 69, 47, 48, 49,
14, 15, 16, 72, 73, 98, 42, 43, 81, 82, 60, 61, 88, 89, 94, 55,
56, 57, 58, 59 };
int sum = (100*101)/2;
for (int i : input) {
sum -= i;
}
System.out.println("Missing number: " + sum);
}
public static void main(String[] args) {
int input[] = { 1, 2, 4, 3 };
int allProduct = 1;
for (int i : input) {
allProduct *= i;
}
for (int i : input) {
System.out.println("All other product for " + i + ": " + allProduct/i);
}
Complexity: O(n) + O(n) = O(n)
- gourahari.das January 28, 20141. To be the smallest number, all the digits have to be in ascending order.
2. To get those digits, keep dividing N with numbers from 2 thru 9 (Lets say this is "i" in a for loop of 2 thru 9).
3. If N is divisible by i, divide and store the result of the division back in N. Keep this "i" as left most digit of the result. If N is still divisible, repeat this step without incrementing the for loop counter (i).
4. One more last point, to get the lowest number run the loop in reverse, i.e. from 9 thru 2.
5. Finally after all divisions done, we should get N = 1 for a success use case. Else make the result as -1.
6. Break from the loop if you get N = 1.
Sample Input: 100
N = 100
Start i = 9 (100 is not divisible by 9). Keep decrementing i by 1.
Hence i = 8, 7, 6, 5 (100 is divisible by 5)
N = N / i. thats N = 100/5 = 20. Keep i as the leftmost digit of the result. result = 5.
N is still divisible by 5.
N = N / i. thats N = 20/5 = 4. Keep i as the leftmost digit of the result. result = 55.
Now N is no more divisible by 5.
Decrement i by 1. i = 4 (4 is divisible by 4)
N = N / i. thats N = 4/4 = 1. Keep i as the leftmost digit of the result. result = 455.
Now N = 1, Exit.
Result = 455
Sample Input: 16
N = 16
Start i = 9 (16 is not divisible by 9)
Decrement i by 1. i = 8 (16 is divisible by 8)
N = N / i. thats N = 16/8 = 2. Keep i as the leftmost digit of the result. result = 8.
Decrement i by 1. i = 7 (100 is not divisible by 7). Keep decrementing i by 1.
Hence i = 6, 5, 4, 3, 2 (2 is divisible by 2)
N = N / i. thats N = 2/2 = 1. Keep i as the leftmost digit of the result. result = 28.
Now N = 1, Exit.
Result = 28
Here is the java code...
public static void main(String[] args) {
int number = 100;
int result = 0;
int count = 1;
for (int i = 9; i > 1; i--) {
while (0 == number % i) {
result = i * count + result;
number /= i;
count *= 10;
}
if (1 == number) break;
}
if (1 != number) result = -1;
System.out.println(result);
}
Just return 0. Don't care of any inputs.
- gourahari.das January 28, 2014