# How to find the smallest number with just 0 and 1 which is divided by a given number

algorithmdivisionmath

Every positive integer divide some number whose representation (base 10) contains only zeroes and ones.

One can prove that:

Consider the numbers 1, 11, 111, 1111, etc. up to 111… 1, where the
last number has n+1 digits. Call these numbers m1, m2, … , mn+1. Each has a
remainder when divided by n, and two of these remainders must be the same.
Because there are n+1 of them but only n values a remainder can take.
This is an application of the famous and useful “pigeonhole principle”;

Suppose the two numbers with the same remainder are mi and mj
, with i < j. Now subtract the smaller from the larger. The resulting number, mi−mj, consisting of j – i ones followed by i zeroes, must be a multiple of n.

But how to find the smallest answer? and effciently?

#### Best Solution

The question equals to using 10i mod n (for each i, it can be used at most once) to get a sum m of n. It's like a knapsack problem or subset sum problem. In this way, dynamic programming will do the task.

In dynamic programming the complexity is `O(k*n)`. k is the number of digits in answer. For n<105, this code works perfectly.

Code:

``````#include <stdio.h>
#define NUM 2000

int main(int argc, char* argv[])
{
signed long pow[NUM],val[NUM],x,num,ten;
int i,j,count;
for(num=2; num<NUM; num++)
{
for(i=0; i<NUM; pow[i++]=0);
count=0;
for(ten=1,x=1; x<NUM; x++)
{
val[x]=ten;

for(j=0; j<NUM; j++)if(pow[j]&&!pow[(j+ten)%num]&&pow[j]!=x)pow[(j+ten)%num]=x;
if(!pow[ten])pow[ten]=x;
ten=(10*ten)%num;
if(pow)break;
}

x=num;
printf("%ld\tdivides\t",x=num);
if(pow)
{
while(x)
{
while(--count>pow[x%num]-1)printf("0");
count=pow[x%num]-1;
printf("1");
x=(num+x-val[pow[x%num]])%num;
}
while(count-->0)printf("0");
}
printf("\n");
}
}
``````

PS: This sequence in OEIS.