CareerCup

Elegant and fast way - to regard 9 as '1' bit and 0 - as '0' bit. In this case we just iteravely increase binary number and check that translated version (from binary '10..' to '90..') is divisable by the provided number

public class Smallest0And9DivisibleNumber {
    public static int find(int divisible) {
        int bin = 1;
        while (true) {
            int res = translate(bin);
            if (res % divisible == 0) {
                return res;
            }
            bin += 1;
        }
    }

    private static int translate(int bin) {
        int result = 0;
        for (int i = Integer.toBinaryString(bin).length(); i > 0; i--) {
            result *= result != 0 ? 10 : 0;
            int mask = 1 <<  (i - 1);
            result += (bin & mask) == mask ? 9 : 0;
        }
        return result;
    }

    public static void main(String[] args) {
        assert find(10) == 90;
        assert find(99) == 99;
        assert find(33) == 99;
        assert find(3) == 9;
        assert find(333) == 999;
        assert find(300) == 900;
        assert find(303) == 909;
        assert find(3033) == 9099;
        assert find(3303) == 9909;
    }
}

#include<stdio.h>
unsigned int ninezero(unsigned int num1,int divNum)
{
if ( num1% divNum == 0 )
return num1;
while(1)
{
num1=num1*10+9;
if (num1 % divNum == 0)
break;
num1/=10;
num1=num1*10+0;
if (num1 % divNum ==0 )
break;
}
return num1;
}
int main()
{
unsigned int num1=9;
int divNum;
printf("enter a number");
scanf("%d",&divNum);
printf("the number is %d",ninezero(num1,divNum));
return 0;
}

Does it work for all test cases?? I mean what if i give 990,999 as divNum ?

Not a good solution, taking time for large input, but it's working. Any improvements in the code or new solution are most welcome.
{
import java.util.Scanner;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
class FindDivisible
{

public static void main(String wat[])
{
int num=Integer.parseInt(wat[0]);
boolean flag=true;
Pattern pat=Pattern.compile("[1-8]+");
Matcher mat;
/* if(9%num==0)
{
System.out.println("Result is : 9");
flag=false;
}*/

long sum=num;
String sumInString;

while(flag)
{
try
{

sumInString=Long.toString(sum);
mat=pat.matcher(sumInString);
if(!mat.find())
{
char [] tempChar=sumInString.toCharArray();
if((tempChar[0]=='9')&&(tempChar[tempChar.length-1]=='0'||tempChar[tempChar.length-1]=='9'))
{
System.out.println("Result is :"+sumInString);
flag=false;
}
}
sum+=num;
}

catch(Exception ex){ break;}
}

}
}
}

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int nine_zero(int n)
{
    vector<int> values;

    values.push_back(9%n);
    int index = 0;

    while ( values[index] != 0 ) {
        index++;
        cout << "        " << index << endl;
        if ( index%2 ) {
            values.push_back((values[(index-1)/2]*10)%n);
        } else {
            values.push_back((values[index-1]+9)%n);
        }
    }

    // output index
    index++;
    string output;
    while (index != 0 ) {
        output = ((index%2)==1? '9' :'0') + output;
        index /=2;
    }
    cout << "Res:" << output << endl;
    return 0;
}

I have one solution for this question , I hope it might be helpful to you guys,
Solution: try to get all combination of 0 and 9 numbers of given range and add it into the list. Iterate the list and divide the number by given number .

I haven't put any error handling.

public void FindDivisor (int inputnumber,int firstnumber,int secondnumber)
// takes the input number and the two numbers that an be used to for the divisor number
{
int number=1;
int divisor=divisornumber(number,firstnumber,secondnumber);
while (divisor%inputnumber!=0)
{ number++;
divisor=divisornumber(number,firstnumber,secondnumber);
}
System.out.println(" The Dividor is " +divisor);
}
public String ReturnBinaryString(int number) {
String S="";
if (number==0)
return "0";
else if (number ==1)
return "1";
else return (S.concat(ReturnBinaryString(number/2)) +(number%2));

}

public int divisornumber(int number,int firstnumber,int secondnumber)
{
String bibaryString=ReturnBinaryString(number);
// convert the in to String
String firststring=""+firstnumber;
String secondstring=""+secondnumber;

//replace all the 0's with first number and 1's with second number
bibaryString=bibaryString.replaceAll("0", firststring);
bibaryString=bibaryString.replaceAll("1",secondstring);
//covert the number to integer back
return (Integer.parseInt(bibaryString));

}

I haven't put any error handling.

public void FindDivisor (int inputnumber,int firstnumber,int secondnumber)
// takes the input number and the two numbers that an be used to for the divisor number
{
int number=1;
int divisor=divisornumber(number,firstnumber,secondnumber);
while (divisor%inputnumber!=0)
{ number++;
divisor=divisornumber(number,firstnumber,secondnumber);
}
System.out.println(" The Dividor is " +divisor);
}
public String ReturnBinaryString(int number) {
String S="";
if (number==0)
return "0";
else if (number ==1)
return "1";
else return (S.concat(ReturnBinaryString(number/2)) +(number%2));

}

public int divisornumber(int number,int firstnumber,int secondnumber)
{
String bibaryString=ReturnBinaryString(number);
// convert the in to String
String firststring=""+firstnumber;
String secondstring=""+secondnumber;

//replace all the 0's with first number and 1's with second number
bibaryString=bibaryString.replaceAll("0", firststring);
bibaryString=bibaryString.replaceAll("1",secondstring);
//covert the number to integer back
return (Integer.parseInt(bibaryString));

}

Question is currently badly worded - you need to say smallest positive number.. as "0" always fits your criteria being the smallest number divisible by any integer and made up of "0"s and "9"s!

static ArrayList<Integer> NextNumber(ArrayList<Integer> numArray)
{
ArrayList<Integer> newNum = new ArrayList<Integer>();
for(Integer i : numArray)
{
if(i != 0)
{
newNum.add(Integer.parseInt(i.toString() + "0"));
newNum.add(Integer.parseInt(i.toString() + "9"));
}
if(i == 0)
newNum.add(Integer.parseInt(i.toString() + "9"));
}
return newNum;
}

static int smallistDivisiable(int div)
{
int start =0;
ArrayList<Integer> num = new ArrayList<Integer>();
num.add(start);
while(true)
{
num = NextNumber(num);
for(int i: num)
{
if((i%div) == 0)
{
System.out.println(i);
return i;
}
}
}
}

I did it by using no strings through memoization. However it is limited and the code can be improved through better calculations of its own limits, but this is a rough idea:

bool FindMinNineZero(int g) {
	if(g == 0){
		printf("Num: %d\n", 0);
	}
	if(g == 1 || g==3){
		printf("Num: %d\n", 9);
	}
	static const int DIGIT_LIMIT = 10;
	static const int MAX_NUMS = 1000;
	long mem[MAX_NUMS];
	mem[0] = 0;
	mem[1] = 9;
	int upperBound = 2;
	bool found = false;
	int acc = 9;
	
	for(int i=2; i<DIGIT_LIMIT; ++i){
		acc*=10;
		int phaseBound = upperBound;
		for(int j=1; j<=phaseBound; ++j){
			if(upperBound > MAX_NUMS) {
				return false;
			}
			mem[upperBound] = acc + mem[j-1];
			printf("new num = %d\n", mem[upperBound]);
			if(mem[upperBound]%g==0) {
				printf("Found: %d\n", mem[upperBound]);
				found = true;
				break;
			}
			upperBound++;
		}
		if(found)	
			break;
	}
	return found;
}

int smallestNumFormedBy09DivisiblleBy(const int ai_divisor)
{
   int counter = 1;
   int number;

   do
   {
      number = 0;
      for (int i = 31; i >= 0; --i)
      {
         number *= 10;
         if (counter & (1 << i))
            number += 9;
      }

      ++counter;
   } while (number % ai_divisor != 0);

   return number;
}

long long int generator(int n) {
   list<long long int>ll;
   ll.push_back(9);
   while(true) {
      curr = ll.front();
      ll.pop_front();
      if(curr % n == 0) return curr;
      else {
         ll.push_back(curr*10+0);
         ll.push_back(curr*10+9);
      }
   }
   return -1;
}