Moore’s Law (Codeforce Gym-102133G)

Problem Link : https://codeforces.com/gym/102133/problem/G

Suppose, the answer for N is X. Now, to find the answer for N+1 there could be two cases :

1. If X is not divided by 2^(N+1) : As X is divided by 2^N and X is not divided by 2^(N+1) , the value of X % 2^(N+1) is equal to 2^N. We can prove this :

X = y * 2^N (where y = 0, 1, 2, ……)
Now, if y is even then X then X = y * 2^(N+1). So, X will be divided by 2^(N+1). If y is odd then X then X = (2z + 1) * 2^N
X = z * 2^(N+1) + 2^N

So, remainder when divided by 2^(N+1) is 2^N.

Now, I have to add a multiple of 2^N with X to make it divisible by 2^(N+1). While adding multiple of 2^N I have to be careful of the digits (Only 1 and 2 can be used). So, I will add 10^Y (where Y >= N) with X and this will add a digit 1 in the front. But, if the number of digits in X is less than N then there will be some zero in between 1 and the most significant digit of X. This is because the answer for N should always have N number of digits.

2. If X is divided by 2^(N+1) : In this case, I have to add a digit so that the answer of N+1 has N+1 number of digits. Digit 1 can’t be used as 10^N is not divisible by 2^(N+1). But digit 2 can be used as (2 * 10^N) is divisible by 2^(N+1).

2 x 10^N = 2 ^ (N + 1) x 5 ^ N

So, the final solution is if the previous answer is divisible by 2^i then add digit 2 in the front of that answer. Otherwise add digit 1.

ll check(string s, ll val) {
    ll rem = 0;
    for(int i = 0; i < s.size(); i++) {
        rem = rem * 10 + (s[i] - '0');
        rem %= val;
    }
    return rem;
}
void solve()
{
    ll n;
    cin >> n;
    string s = "2";
    for(int i = 2; i <= n; i++) {
        ll val = (1LL<<i);
        val = check(s, val);
        if(val == 0)
        s = "2" + s;
        else 
        s = "1" + s;
    }
    cout << s << '\n';
}