## Amazon Interview Question

Country: India

Comment hidden because of low score. Click to expand.
4
of 4 vote

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++):

``````#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string A;

string findMaxNumDiv235(string A){
int n = A.length();
string res;
res = A;

sort(res.rbegin(), res.rend()); // sort descending order

// Check division by 2 and 5:
if (res[n-1]  != '0') return "no number can be formed";

// Check division by 3:
int SumDigit = 0;
for(int i=0; i<n; i++) SumDigit += res[i] - '0';

// Divisible by 3?:
if (SumDigit % 3 == 0) return res;

// Not divisible by 3:
// Delete 1 digit:
for(int i = n-2; i>=0; i--)
if ( (res[i] - '0') %3 == SumDigit %3){
res.erase(i,1);
return res;
};

// Delete 2 digits:
for(int i = n-2; i>=0; i--)
if ( (res[i] - '0') %3 != 0){
res.erase(i-1,2);
return res;
};

return "no number can be formed";
};

int main()
{
A = "16870";
A = "174470";
A = "01";
cout <<"Input: "<<A<<endl;
cout <<"The biggest number is: "<<findMaxNumDiv235(A)<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

@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?

Comment hidden because of low score. Click to expand.
0

I dont think your code is right though !!

Comment hidden because of low score. Click to expand.
0

@Tony Stark: have you tried it? Or, you may refer to bob's comments above for explanation.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````/**
*
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
* @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};
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!!!");

}

}``````

Comment hidden because of low score. Click to expand.
0

I think it may be wrong for this input A = 42110.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

The answer should be 4110.

Comment hidden because of low score. Click to expand.
0

``````/**
*
*/
package Amazon;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
* @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 };
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) {

}
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!!!");

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

we can do something for 3 if it's originally impossible, by ignoring one or two digits.
The example suggested so.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

Actually answer should be 8760 .....

Comment hidden because of low score. Click to expand.
0

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)) {
}
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);
}
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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

it is very simple
steps
1) Sort the list in descending order
2) generate all the subset of collections
3) for each no in collection try check number is divisible by 30 and keep updating maximum no which is divisible by 30

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the smallest and the largest number that can be formed. That gives the range of numbers. Then question becomes what is the sum of divisors of 30 in that range which can be found in constant time as the it is sum of arithmetic progression. Did I miss something

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.