All roads lead to Rome, all numbers lead to Binary

I check through all the numbers containing only zeros and ones by converting all positive integers into binary.

Java code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public class brilliant201410111913{
    public static void main(String[] args){
        for(int i=1;;i++){
            if(Long.parseLong(Integer.toBinaryString(i))%98961==0){
                System.out.print("    "+Integer.toBinaryString(i)+"\n    ");
                break;
            }
        }
    }
}

Output:

1110010010001
Press any key to continue . . .

$98961 \times i = n$

If $n$ is the integer composed of only $1$ 's and $0$ 's, then $n$ must equal $1$ or $0$ mod $10$ . The values of $i$ that allow this are themselves $1$ or $0$ mod $10$ . So the only values of $i$ we would have to check are $10k$ or $10k + 1$ . This cuts our search space by $10$ . An implementation using this idea in Java.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class rome {
    public static boolean is_one_zero(long n) {
        // Returns true if n is all 0s and 1s

        while (n != 0) {
            if (n % 10 > 1)
                return false;
            else
                n /= 10;
        }
        return true;
    }

    public static void main(String[] args) {
        long i = 1;
        while (true) {
            if (is_one_zero(98961 * i * 10)) {
                System.out.println(98961 * i * 10);
                break;
            } else if (is_one_zero(98961 * i * 10 + 1)) {
                System.out.println(98961 * i * 10 + 1);
                break;
            }
            i++;

        }
    }

}

i used a simple heuristic to speed up iterations.

first of all, let us assume that we have to multiply 'c' to 98961 to get the solution. now, the unit digit of 'c' has got to be 1 because if it's 0, we can trim it down to get a smaller multiplier. since unit digit of 'c' is 1, tens digit of 'c' must be 4 or 5 to keep the tens digit of product 0 or 1 correspondingly.

hence iterate by using a multiplier c which increments by 10 if it's tens digit is 4 and by 90 it it's tens digit is 5. thus the last two digits of c remain 41 and 51. we can continue with this reasoning but even this much gives a fast enough solution (within 0.047 seconds on my PC).

Here is the c++ code,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#define ll long long int
using namespace std;
bool binary(ll x)
{
    while(x>0)
    {
        if((x%10)>1)
            return false;
        x/=10;
    }
    return true;
}
int main()
{
    ll x=98961;
    ll b=x;
    ll c=41;
    int t1,t2;
    while(!binary(x))
    {
        t1=c/10;
        t2=t1%10;
        if(t2==4)
            c+=10;
        else
            c+=90;
        x=b*c;
    }
    cout<<x<<endl;
    return 0;
} 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def plusone(n):
     n = [i for i in reversed(list('0' + str(n)))]
     for i in xrange(len(n)):
             if n[i] == '1':
                     n[i] = '0'
             elif n[i] == '0':
                     n[i] = '1'
                     break
     n = int(''.join(([i for i in reversed(n)])))
     return n

i = 1
while i%98961:
    i = plusone(i)
print i

Fastest algorithm

I also used the fact that $98691$ has to multiplied by $10i$ and $10i+1$ to have the last digit of the multiple be $0$ and $1$ respectively. I used the following Python code.

 i = 1 

 while True:

         s = str(989610*i)

     result = filter(lambda x: x=='0' or x=='1', s)

     if result == s: break

     s = str(98961*(10*i+1))

     result = filter(lambda x: x=='0' or x=='1', s)

     if result == s: break

     i += 1

print s

I solved this by generating all integers in base 10 containing 0s and 1s, and using BFS algorithm to get the smallest multiple. C++ code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <bits/stdc++.h>
#define cb(x) (x)*(x)*(x)
using namespace std;
long long num;
queue <long long> bfq; // BFS queue
int main() {
    bfq.push(1); // 
    while (!bfq.empty()) {
        num=bfq.front(); // get the front number
        if (num%98961 == 0) break; // if the number is divisible by 98961, then it is the answer
        else {
            bfq.push(num*10); // add the number with '0' and push it to the queue
            bfq.push((num*10)+1); //add the number with '1' and push it to the queue
        }
        bfq.pop();
    }
    cout << num;
    return 0;
}

Boom, 1110010010001

No clever mathematics, easy to code.

Simple brute-force in Python:

def f(x):
    while x:
        if x % 10 != 0 and x % 10 != 1:
            return False
        x = x / 10
    return True

n = 98961
while not f(n):
    n = n + 98961
print n

I have solved this problem with C++ using Dynamic Programming(DP). Here's my solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include<iostream>
#include<cstring>
using namespace std;

const int mod = 98961, L = 100;
int dp[L][mod + 5];

int solve(int p, int m) {
    if(!m) return 0;

    if(p == L) return 1e9;

    if(dp[p][m] != -1) return dp[p][m];

    dp[p][m] = 1e9;
    dp[p][m] = min(dp[p][m], 1 + solve(p + 1, (m * 10 + 1) % mod));
    dp[p][m] = min(dp[p][m], 1 + solve(p + 1, (m * 10) % mod));

    return dp[p][m];
}

void pp(int p, int m) {
    if(!m || p == L) return;

    if(dp[p][m] == 1 + solve(p + 1, (m * 10 + 1) % mod)) {
        cout << 1;
        pp(p + 1, (m * 10 + 1) % mod);
        return;
    } else if(dp[p][m] == 1 + solve(p + 1, (m * 10) % mod)) {
        cout << 0;
        pp(p + 1, (m * 10) % mod);
        return;
    }
}

int main() {
    memset(dp, -1, sizeof dp);
    cout << "Length: " << solve(1, 1) + 1 << endl;
    cout << "Number: 1";
    pp(1, 1);
    cout << endl;
    return 0;
}

1
2

Length: 13
Number: 1110010010001