## Amazon Interview Question

**Country:**India

I think there is no need to consider pairs of numbers.

Three cases:

1) Sum of digits divisible by 3 - no need to do anything.

2) Sum of digits equals 1 or 2 modulo 3. Search for smallest digit that gives same remainder modulo 3

3) Sum of digits equals 1 or 2 modulo 3 = x. but all digits are 3-x. Just take 2 smallest digits and remove them.

ah, sorry, in your code you are doing exactly that thing. (explanation confused a litl bit)

@bob: Thanks!

I have just made some changes into my explanation.

My explanation for the case divisible by 3 is little bit confusing (compared to actual implementation).

However, if the question asked for other division, e.g. divisible by 9, then that explanation could still be applied. Isn't it?

```
/**
*
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
/**
* @author mangesh
*
*/
public class GenerateMAX {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer a[] = { 1, 2, 4, 5, 6, 1, 0 ,9,2,0};
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(a));
Collections.sort(list);
if (list.get(0) != 0) {
System.out.println("Can not find such number!!!");
return;
}
int k = 1;
while (true) {
long number = list.get(0);
for (int i = 1; i < list.size(); i++) {
number += (long) (list.get(i) * Math.pow(10, i));
}
if (number % 3 == 0) {
System.out.println(number);
return;
}
while (true) {
if(list.get(k) % 3!= 0){
list.remove(k);
break;
}
k++;
if (k >= list.size())
break;
}
if (k >= list.size())
break;
}
System.out.println("Can not find such number!!!");
}
}
```

I think it is giving correct answer 420 ...... Why u think it is wrong? give me test cases.....

```
/**
*
*/
package Amazon;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
/**
* @author mangesh
*
*/
public class GenerateMAX {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer a[] = { 4,2,1,1,0 };
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(a));
ArrayList<Long> max = new ArrayList<Long>();
Collections.sort(list);
if (list.get(0) != 0) {
System.out.println("Can not find such number!!!");
return;
}
int k = 1;
int nocosiderDigit = -1;
boolean remove = false;
while (true) {
long number = list.get(0);
int pow = 1;
for (int i = 1; i < list.size(); i++) {
if (nocosiderDigit == i)
continue;
number += (long) (list.get(i) * Math.pow(10, pow++));
}
if (number % 3 == 0) {
max.add(number);
}
while (true) {
if (list.get(k) % 3 != 0) {
if (!remove)
nocosiderDigit = list.indexOf(list.get(k));
else
list.remove(k);
k++;
break;
}
k++;
if (k >= list.size())
break;
}
if (k >= list.size()) {
if (max.size() == 0 && !remove) {
k = 1;
remove = true;
} else {
break;
}
}
}
if (max.size() > 0) {
Collections.sort(max);
System.out.println(max.get(max.size() - 1));
System.out.println(max.toString());
} else
System.out.println("Can not find such number!!!");
}
}
```

you cant do anything for 3 just check if it is possible or not. add all digits and the sum should be devisible by 3.

for 2 and 5 ..... the number should have 0 at its units place and then take the rest numbers such that hightes close to 9 is is in the left side and so on.

In this case 1: array = 18760, why the result is 8760, I think 8610 is the right answer...

I used the BFS method by deleting one digit in each level to get the result.

And also use a Map to filter the duplicate node.

For example:

level 0: 8761

level 1: 876 871 861 761

level 2: 87 86 76 .....

```
import java.util.*;
public class MaxNumber {
public static void main(String[] args) {
int[] arr = {7,7,7,6,0};
MaxNumber obj = new MaxNumber();
int result = obj.getMaxNumber(arr);
System.out.println(result);
}
public int getMaxNumber(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
Arrays.sort(arr);
int num = 0;
for (int i = arr.length - 1; i >= 0; i--) {
num = num * 10 + arr[i];
}
//System.out.println(num);
if (num % 10 != 0) {
return -1;
}
// delete last digit '0'
num = num / 10;
Queue<Integer> queue = new LinkedList<>();
// filter duplicate case;
Map<Integer, Boolean> map = new HashMap<>();
queue.offer(num);
while (queue.size() != 0) {
int top = queue.poll();
if (isValidForDividByThree(top)) {
return top * 10;
}
List<Integer> allSubNum = getSubNodesByDeleteOneDigit(top);
for (Integer i : allSubNum) {
if (!map.containsKey(i)) {
queue.offer(i);
map.put(i, true);
}
}
}
return -1;
}
private List<Integer> getSubNodesByDeleteOneDigit(int num) {
List<Integer> resultList = new ArrayList<>();
int length = getLength(num);
for (int i = 0; i < length; i++) {
int result = deleteIndexAtI(num, i);
resultList.add(result);
}
return resultList;
}
private int deleteIndexAtI(int num, int index) {
int lastPartNumber = num % (int)Math.pow(10.0, index);
int firstPartNumber = num / (int)Math.pow(10.0, index + 1);
firstPartNumber = firstPartNumber * (int)Math.pow(10.0, index);
return firstPartNumber + lastPartNumber;
}
private int getLength(int num) {
int length = 0;
while (num != 0) {
length++;
num = num / 10;
}
return length;
}
private boolean isValidForDividByThree(int num) {
int sum = 0;
while (num != 0) {
sum += num % 10;
num = num / 10;
}
if (sum % 3 == 0) {
return true;
}
return false;
}
}
```

```
struct MaxNumGenerator{
int maxValue;
int * values;
int numValues;
MaxNumGenerator()
{
maxValue=-1;
}
int LargestCustomNumber(int * digits, int length)
{
maxValue=-1;
values = digits;
numValues = length;
generateAllNumbers();
return maxValue;
}
void generateAllNumbers()
{
int * used = new int [numValues];
for(int i =0; i < numValues; i++)
used[i]=0;
generateCombinations(used, 0, 0);
}
bool isValid(int sum)
{
return (sum >0 && (sum % 30) == 0);
}
void generateCombinations(int * used, int usedCount, int sum);
}
;
void MaxNumGenerator::generateCombinations(int * used, int usedCount, int sum)
{
int index=-1;
if(isValid(sum) && sum > maxValue) maxValue=sum;
for(int i =0; i < numValues; i++)
{
if(used[i] ==0)
{
used[i]=1;
index =i;
int factor=(values[i] * pow(10.0, usedCount));
generateCombinations(used, usedCount +1, sum+factor);
used[i]=0;
}
}
}
```

To form a number that divisible by both 2 and 5, the input array must have a "0", otherwise no such number can be formed. Put that "0" at the end.

Now to form a number divisible by 3: We need to "delete" some digits so that sum of the remaining is divisible by 3.

Let S be the sum of digits.

If S is divisible by 3: keep all.

If S is not divisible by 3: we try to "delete" one digit first, if not possible then try delete two digits. No need to try delete three or more digits, since either delete one or two digits will do.

We choose to delete digits that the maximum number can be formed from these digits is minimum. This make sure that the remaining digits can form a maximum number.

Let B be the array of digits after delete one or two these digits.

Sort B decreasingly.

The final number is formed by concatenating digits in B.

Example:

------------

A = 1 7 4 4 7 0

We have sum S = 23, not divisible by 3.

Try to delete one digit: Impossible! Have to delete 2 digits.

Find set of digit pair to delete: (1, 4); (4,4); (4,7); (7,7) (Note: we concern the set of pairs; repeated pairs are ignored).

Among these pairs, we should delete the pair (1,4) since the maximum number this pair can form is 41, which is the smallest number compared to other pairs.

Thus, B = 7 4 7 0

Sorted B = 7 7 4 0

The final answer is 7740.

Implementation is not complicated: (code in C++):

- ninhnnsoc September 27, 2014