## Amazon Interview Question for SDE1s

• 0

Country: United States
Interview Type: Written Test

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

``````public int findDivisibleNum(int k) {
Set<Integer> numList = new ConcurrentSkipListSet<>();

for(int i = 10; i < Integer.MAX_VALUE; i = i * 10) {
for(Integer num : numList) {
}
for(Integer num : newList) {
if(num != 0 && num % k == 0) {
return num;
}
}
}
return -1;
}``````

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

My assumptions:

1. Ones and Zeros number must be ~evenly~ divisible by A (probably obvious).
2. Begin the sequence at 10 ("0" and "1" aren't eligible)
3. The problem domain is constrained to <= 1111111111 (max signed int containing only 1 and 0 digits).

``````int smallestOneZeroMultiple(int A)
{
for (int i = 2; 2 < 1111111111; ++i)
{
// Convert i from binary format to decimal "1's and 0's"
int multiple = 0;
for (int j = 0; i < 32; ++j)
{
if (i & (1 << j))
multiple += 10 ^ j;
}

if ((multiple % A) == 0)
return
}

return -1; // Couldn't find a multiple
}``````

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

Whoops, I screwed up on line 10. Want to raise 10 to the power j, not XOR 10 and j :-p

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

``````int smallestOneZeroMultiple(int divisible)
{
int mul=2;
int re=mul*divisible;
while(re<1111111111){
if(CheckOnlyOneZero(re))
return re;
mul++;
re=mul*divisible;
}
return -1;
}

bool CheckOnlyOneZero(int num){
int i=0;
while(num>=10){
i=num%10;
num=num/10;
if(i==1 || i==0)
continue;
else
return false;
}
if(num==1 || num==0)
return true;
else
return false;
}``````

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

``````{
int isAllowed(int val){
while(val){
int rem;
rem = val % 10;
if(rem!=0 && rem!=1) return 0;
val = val / 10;
}
return 1;
}

int findSmallest(int A){
int i = 0;
while(1){
if(i != 0 && i % A == 0 && isAllowed(i)) {
printf("Found:%d",i);
return i;
}
i++;
}
}``````

}

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

Another text-based (and therefore not efficient or elegant) answer in java.

This compiles and works, but dies for A >= 396. (Interview question: why?)

``````public static long findCoolNumber(int a) {
for (long result = 1; result < Long.MAX_VALUE; result++) {
String binValue = Long.toBinaryString(result);
long toDecimal = Long.parseLong(binValue);
if ((toDecimal % a) == 0) {
}
}

return 0; // or other sentinal, or throw exception if you like.

}``````

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

``````/**
* Given a number A, find the smallest number which has only 1s and
* 0s as its digits which divisible by the number A. For example:
* if the given number A is 4, the smallest number with 1s and 0s is
* which is divisible by 4 is 100.
*/
package careercup;

public class FindNumber {

public static void main(String args[]) {
FindNumber n = new FindNumber();
int digits =65;
int [] bitsArray = new int[digits];
n.createBits( digits,15,15);
}

// checks for flipping the bits
private int checkMathMul(int count, int power)
{
return	( count/((int)Math.pow(2, power))>=1)?1:0;
}

// generates a sum of the binary representation and divides by the divisor to check perfect divison
private int checkForDivision(int [] arrayBits, int divisor)
{
int sum =0;
for(int i=0;i<arrayBits.length;i++)
sum+=(int) Math.pow(10, i) * arrayBits[i];
System.out.println("sum :"+sum);
if(sum%divisor ==0)
return sum;
return -1;
}

/*
* it creates a binary representation of the array, and check for the smallest dividend. the number is the divisor here!
* */
private  int[] createBits( int count, int number, int n)
{
int []bitsArray  = new int[n];
for(int i=1;i<count;i++)
{
bitsArray = i%2;
for(int x=1;x<n;x++)
bitsArray[x]= 	checkMathMul(i, x);

for(int j=bitsArray.length-1;j>=0;j--)
System.out.print(bitsArray[j]+" ");
System.out.println();
int result = checkForDivision(bitsArray, number);
if(result != -1)
{
System.out.println("Smallest divisor: "+result);
return bitsArray;
}

}
return new int []{};

}

}``````

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

Implement BFS

1. verify given number is 1 if yes then return true.
2. If if it not then put 1 into queue
3. In while (true) pop queue item, Lets say it is "X"
4. if(INT_MAX/10 < X) return false
5. Multiply X by 10 mod by given number if remainder is zero then return true
6. else add the number to queue.
7. if((INT_MAX-1)/10 > X) return false
8. Multiply X by 10 and add 1 mod by given number if remainder is zero then return true
9. else add the number to queue.

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

C#
--------------

``````int DivisibleNmberFinder(int divisor)
{
Queue<int> q = new Queue<int>();

q.Enqueue(1);

while(q.Count() > 0)
{
int number = q.Dequeue();

if (number % divisor == 0) return number;
else
{
string seed = number.ToString();
if (seed.Length < divisor)
{
q.Enqueue(Convert.ToInt32(seed+"0"));
q.Enqueue(Convert.ToInt32(seed+"1"));
}
}
}

return -1;
}``````

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

``````import java.util.TreeSet;

public class SmallestDivisible {

public static long smallestDivisibleBy(int a) {
TreeSet<Long> possibles = new TreeSet<Long>();

while(!possibles.isEmpty()) {
long p = possibles.pollFirst().longValue();
if (p % a == 0) {
return p;
}

long nextP = p * 10;

nextP = nextP + 1;
}

return -1;
}

public static void main (String[] args) {
System.out.println(smallestDivisibleBy(Integer.parseInt(args)));
}
}``````

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

sorry but i didnt understand the question properly i guess.
my understanding is-
1. they are looking for binary of smallest number which is divisible by given number
2. the smallest number which is divisible by any number is that number itself
so they are asking for binary of same number?

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

Sorry but i think i didnt understand question properly.
My understanding is-
1. they are asking for binary number which is divisible by given number
2. least number which is divisible by any number is that number itself ....
so are they asking for binary of the same number?

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

``````int findSmallestDivisible(int sum, int n)
{
if( sum > INT_MAX || sum <=0) return INT_MAX;
if(sum % n == 0) return sum;
int min0 = findSmallestDivisible(sum * 10 + 0, n);
int min1 = findSmallestDivisible(sum * 10 + 1, n);
return min(min0, min1);
}``````

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

``````int findSmallestDivisible(int sum, int n)
{
if( sum > INT_MAX || sum <=0) return INT_MAX;
if(sum % n == 0) return sum;
int min0 = findSmallestDivisible(sum * 10 + 0, n);
int min1 = findSmallestDivisible(sum * 10 + 1, n);
return min(min0, min1);
}``````

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

ok, this is really easy, just generate all permutations of 0,1 digits one by one and check if they divide 4, here is a simple c++ code that does it:
int smallestZeroOneDividingN(vector<int>digits, string number, int start, int end, int n)
{
int currentNumber = string_Atoi(number);
if(currentNumber != 0 && currentNumber % n == 0)
{
return currentNumber;
}
if(start == end)
{
return -1;
}
for(int i = 0 ; i < digits.size (); i++)
{
number[start] = digits[i];
int res = smallestZeroOneDividingN(digits, number, start + 1, end, n);
if(res != -1)
return res;
}
return -1;
}

int smallestZeroOneDividingN(int n)
{
vector<int> digits;
digits.push_back(0);
digits.push_back(1);

string number = "";
for(int i = 2; i < INT_MAX; i++)
{
number.resize(i);
int res = smallestZeroOneDividingN(digits, number, 0, number.size(), n);
if(res != -1)
return res;
}
return n;
}

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

``````public int helper(int n, String p)
{
if(p.length()<"1111111111".length() && Integer.parseInt(p)<1111111111 && Integer.parseInt(p)%n==0)
return Integer.parseInt(p);
else if(p.length()<"1111111111".length() && Integer.parseInt(p)<1111111111)
return Math.min(helper(n, p+"0"),helper(n, p+"1"));
return Integer.MAX_VALUE;``````

}

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

The easiest way is to keep multiplying the number by every possible integer and checking if the result has only 1's and zeros.

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

``````static void Main(string[] args)
{
int x = 10;
int num = 4; //input
while (x % 4 != 0)
{
x = x * 10;
}
Console.WriteLine(x);

}``````

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

``````static void Main(string[] args)
{
int x = 10;
int num = 4; //input
while (x % 4 != 0)
{
x = x * 10;
}
Console.WriteLine(x);

}``````

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

#include <stdio.h>

#define INT_MAX 0xFFFFFFFF

int min(int num1, int num2)
{
if (num1 == -1 && num2 == -1)
{
//couldn't find the min divisible in int range
return -1;
}
else if (num1 == -1)
{
//no divisible in other path
return num2;
}
else if(num2 == -1)
{
//no divisible in other path
return num1;
}
//if both positive
return (num1<num2) ? num1 : num2;
}

int findmindiv(int num, int n)
{
if (num >= INT_MAX || num<=0 || n == 0) return -1;
if (num % n == 0) return num;
int min0 = findmindiv(num * 10 + 0, n);
int min1 = findmindiv(num * 10 + 1, n);
return min(min0, min1);
}

void main()
{
int n;
int more = 1;
while (more == 1)
{
printf("Enter the number:");
scanf_s("%d", &n);
printf("Min divisible made of just 1s and 0s is: %d\n\n", findmindiv(1, n));

printf("More?:");
scanf_s("%d", &more);
}

getch();
}

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

{{}}

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

``````def multiple(n):
q = Queue.Queue()

q.put('1')
while True:
cur_num = q.get()
if int(cur_num) % n == 0:
return cur_num
q.put(cur_num+'0')
q.put(cur_num+'1')``````

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

``````public static String multiple(int A) {

HashSet<Integer> visited = new HashSet<>();
String temp;
while (!queue.isEmpty())
{
temp = queue.poll();
int rem = mod(temp,A);
if (rem==0) return temp;

if (!visited.contains(rem))
{
}
}

return "";
}

public static int mod(String s,int n)
{
int rem = 0;
int len = s.length();
for (int i=0;i<len;i++)
{
rem = rem*10 + (s.charAt(i)-'0');
rem = rem%n;
}

return rem;
}``````

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

FOR MULTIPLES WITH ANY NUMBER OF DIGITS:

``````struct node{
string s;
int rem;
node(string t, int x){
this->s = t;
this->rem = x;
}
};

string smallestMultiple(int n) {
queue<node> q;
q.push(node("1",1%n));

vector<int> seen(n,0);

while(q.size()){
node x = q.front(); q.pop();

if(x.rem == 0)
return x.s;

int rem0 = (10*x.rem)%n, rem1 = (10*x.rem +1)%n;

string s0 = x.s+"0", s1= x.s+"1";

if(!seen[rem0])     q.push(node(s0,rem0)), seen[rem0]=1;

if(!seen[rem1])     q.push(node(s1,rem1)), seen[rem1]=1;
}

return "-1";
}``````

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

"""
To solve this problem, there are many approaches, One of the optimised being as shown below
To easily get numbers with only 1s and 0s, we can loop through numbers from 1 to infinity and get the
binary encode of it

That is
get the number to get its lowest multiple made up of 1s and 0s
next create a loop which starts from 0
inside the loop, for each looping variable, convert it to binary
Best practice is to return the binary number as an integer
next, if the binary representation of the variable is divisible by the intended number, return the binary
representation of the looping instance
else, increment the looping variable and continue as above

At the end, what will be returned will be the smallest multiple of our number with 1s and 0s
"""

"""
this can be expressed in PseudoCode as show

Start
Get Number
set i to 1
convert i to binary

while binary of i divided by Number is not equal to 0
increment i by 1 and convert to binary
return i

EndWhile
"""

``````def tobin(n):
b= []
while(n>0):
d=n%2
b.append(d)
n=n//2
b.reverse()
res = [str(i) for i in b]
return int("".join(res))

def smallestMultiple(a):
i = 1
while (tobin(i) % a != 0):
i += 1
print("smallest multiple: ",smallestMultiple(7))``````

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

package com.shashi.carrercup;

/**
*
* @author shashi
*/
public class FindNumber {

public static void main(String args[])
{
FindNumber n=new FindNumber();
System.out.print(n.getNumber(4));
}
public int getNumber(int number)
{
//check for invalid condition
if(number<0)
return 0;
//if not do some operations
//let take maximum 8 bit digit
int max=11111111;
int current;
int c1=0;
for(int i=2;i<max;i++)
{
//take the current number
boolean check=false;
current=number*i;
//copy number
c1=current;
while(current>0)
{
int rem=current%10;
if(rem == 0 || rem == 1 )
{
current=current/10;
if(current == 0)
{
check=true;
break;
}
}
else
{
break;
}
}
//you got first min if check is true
if(check)
break;
}
return c1;
}

}

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

package careercup;

public class FindNumber {

public static void main(String args[]) {
FindNumber n = new FindNumber();
n.findIfDivisible(4);
//System.out.print(n.getNumber(4));
}

public int findIfDivisible(int num)
{
int i,count=0;
for( i=10;;i=i*10)
{
if(i%num==0)
break;
//i=i*10;
count++;
if(count>100)
return -1;

}
System.out.println(i);
return i;
}

}

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

We know that any number that only has 1s an 0s can be interpreted as a bit string.
We know that since our maximum bitstring for long is 1111111111 that this is the bit representing 1023.

So we simply find a conversion from all integers from 1 to 1023 (inclusive) to their corresponding bitstring values then check if this bitstring can divide our given number.

It is possible to avoid the overhead of String to long conversion by simply writing your own method for the conversion from int to long directly.

The function convertDecToLong runs in 32 operations since it will bitshift at most 32 times. Running this operations something around 1023 times will give us an estimated ~32000 operations - much better than the brute force of 1111111111 operations.

``````public static long min(int n) {

for (int i = 0; i <= 1023; i++) {

long possibility = convertDecFromBin(i);

if (isDivisible(possibility, n)) {

return possibility;
}
}

return -1;
}

public static long convertDecFromBin(int n) {

long output = 0;
int x = n;
int currentDecPlace = 0;
while (x != 0) {

output = ((x & 1) == 1) ? (output + (long)Math.pow(10, currentDecPlace)) : output;
currentDecPlace++;
x >>= 1;
}

return output;
}``````

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

``````static void Main(string[] args)
{
int x = 10;
int num = 4; //input
while (x % 4 != 0)
{
x = x * 10;
}
Console.WriteLine(x);

}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

This can be done using a decimal to binary conversion.

``````<?php

function findBin(\$n) {
\$b = '';
while (\$n >=1) {
if (\$n % 2 == 0) {
\$b = '0' . \$b;
} else {
\$b = '1' . \$b;
}
\$n = (int) (\$n / 2);
}
return \$b;
}

function findSmallest(\$n) {
\$p = 1;
\$b = findBin(\$p);
while (\$b % \$n != 0) {
\$p++;
\$b = findBin(\$p);
}
return \$b;
}

for (\$i = 1; \$i < 10; \$i++) {
var_dump(findSmallest(\$i));
}``````

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

Actually the smallest number divisible by A is A itself; I assume that zero doesn't count. So all we need is to call findBin(A).

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

@ ranan.fraer : Could you explain this for A = 5 where the smallest number divisible by A with only ones and zeroes is "10" ?

Comment hidden because of low score. Click to expand.
-2
of 2 vote

static int findNumber(int num)
{
int tens=10;
while(tens%num!=0)
{
tens=tens*10;
if(tens>1111111111)
{
return 0;
}
}
return tens;
}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

static int findNumber(int num)
{
int tens=10;
while(tens%num!=0)
{
tens=tens*10;
if(tens>1111111111)
{
return 0;
}
}
return tens;
}

Comment hidden because of low score. Click to expand.

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.