CareerCup

public int findDivisibleNum(int k) {
        Set<Integer> numList = new ConcurrentSkipListSet<>();
        numList.add(0);
        numList.add(1);

        for(int i = 10; i < Integer.MAX_VALUE; i = i * 10) {
            HashSet<Integer> newList = new LinkedHashSet<>();
            for(Integer num : numList) {
                newList.add(num + i);
            }
            for(Integer num : newList) {
                if(num != 0 && num % k == 0) {
                    return num;
                }
            }
            numList.addAll(newList);
        }
        return -1;
}

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
}

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

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

}

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

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

  }

/**
 * 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.
 * @author lalitazad 
 */
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[0] = 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 []{};
		
		
	}
	
	
	
	
	
	

}

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.

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

import java.util.TreeSet;

public class SmallestDivisible {

    public static long smallestDivisibleBy(int a) {
	TreeSet<Long> possibles = new TreeSet<Long>();
	possibles.add(10L);
	possibles.add(11L);

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

	    long nextP = p * 10;
	    if (nextP > p) possibles.add(nextP);

	    nextP = nextP + 1;
	    if (nextP > p) possibles.add(nextP);
	}

	return -1;
    }


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

sorry but i didnt understand the question properly i guess.
Please help me to understand......am very new to this site
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?

Sorry but i think i didnt understand question properly.
Please help me in this.....m very new to this site
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?

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

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

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

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;

}

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

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

            Console.ReadLine();

        }

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

            Console.ReadLine();

        }

#include <stdio.h>

#define INT_MAX 0xFFFFFFFF
int add = 1;

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

{{}}

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')

public static String multiple(int A) {

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

            if (!visited.contains(rem))
            {
                visited.add(rem);
                queue.add(temp+"0");
                queue.add(temp+"1");
            }
        }

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

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

"""
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
	return tobin(i)
print("smallest multiple: ",smallestMultiple(7))

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





}

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





}

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

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

            Console.ReadLine();

        }

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

static int findNumber(int num)
{
int tens=10;
while(tens%num!=0)
{
tens=tens*10;
if(tens>1111111111)
{
System.out.println("No Answer for this number");
return 0;
}
}
return tens;
}

static int findNumber(int num)
{
int tens=10;
while(tens%num!=0)
{
tens=tens*10;
if(tens>1111111111)
{
System.out.println("No Answer for this number");
return 0;
}
}
return tens;
}

static int findNumber(int num)
	{
		  int tens=10;
			while(tens%num!=0)
			{
				tens=tens*10;
				if(tens>1111111111)
				{
					System.out.println("No Answer for this number");
					return 0;
				}
			}
			return tens;
		}