Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
Suppose n has m digits. We will generate all m, m+1,m+2 ,m+3.. digit numbers comprising of digits 0 and 7 in the increasing order and then check for each generated number if it is divisible by n.
Suppose n is 3812. In this case we will generate all the 4,5,6.. digit numbers consisting of 0 and 7 through combination, for ex the first one will be 7000, 2nd 7007, 3rd 7070, 4th 7077, 5th 7700, likewise and check for each generated number if it is divisible by n. We will keep on generating the numbers until and unless we find one which is divisible by n.
In other case, suppose n is 8812. In this case we will start from generating 5 digit numbers consisting of 0 and 7 as the maximum 4 digit number 7777 is smaller than the n itself.
Use 2 queues:
queue1: for numbers with 0 at unit place
queue2: for numbers with 7 at unit place
get minimum of these two queues.Check if it is divisible by n. if yes return it else insert in queues as per the critetia.
unless i'm missing something very obvious, wouldn't any combination of 0 *and* 7 will be divisible by 7 ?
so if an integer N is divisible by any combination of 0 and 7 - it is divisible by 07 - which is obviously be smallest of any such combination.
This is because
(07)+ is divisible by 7
(70)+ is divisible by 7
Of course i'm assuming that the question implies that we must use both 0 and 7.
That said, the question is a bit vague and certainly needs more clarification.
Initially choose some number k of the form 7x10^x for some x, where k > the given number N.
- Murali Mohan February 11, 2014Suppose k = 7000,
1. Place a 7 one position at a time and see if N divides k. For ex: 7007, 7070,7700.
2. Then place 2 7's at positions and see like in 7077, 7707, 7770 etc. and test if N divides k.
In essence, the problem is asking to generate the possible combinations of 7's and 0's and then check for divisibility. The problem is combinatorial in nature and my solution has exponential time complexity in the number of digits of N.