Math Division

Problem Statement🔗

Brief Explanation:

Ecrade has a number x (given as a binary string) and wants to shrink it down to 1 using two possible operations:

1. Floor Division: x → ⌊x / 2⌋ (rounds down)

2. Ceiling Division: x → ⌈x / 2⌉ (rounds up)

Each operation is equally likely (50% chance). To Find the expected number of operations needed to get x down to 1 — modulo 10⁹ + 7.

Observations:

Even Numbers:

Both operations give the same result: x / 2.

No randomness here.

Odd Numbers:

Floor division: x → (x — 1) / 2

Ceiling division: x → (x + 1) / 2

The outcome depends on the PROBABILITY(My favourite!).

Constraint:

n→(1≤n≤10⁵)

Approach:

• The input is in the binary number system, most of you would have thought to convert it to decimal, but just take a deep breath. I prefer it to be binary because using binary shifting we can easily divide the number by 2.
• Now to solve this problem efficiently, we use Dynamic Programming (DP). The key idea is to track the expected number of operations needed for each number using two values:
• The necessary condition
  By observing the question we can clearly conclude that
  If x is Even we can neither perform floor division nor ceil division because both will result in the same number. So there is a shifting of 0 bit(no shifting basically)
• Now if x is odd :

Here, floor and ceiling division lead to different results: (x-1)/2 and (x+1)/2, so we account for both:

Get Himmy’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Ea = 1 + (Ea + Eap) / 2 → We take the average number of steps from both possible transitions.(remember it is average of binary numbers don’t get confused)

Eap = 1 + Eap → If transitioning from x+1, we add 1 and use its previous value.

Solution*🔗(CF submission code: 311027556):

Initialization

We start with Ea = 0 (since 1 → 1 takes 0 steps).

E(a+1) = 1 (since 2 → 1 takes 1 step).

Processing Each Bit

If the bit is ‘0’ (even number):

• newEa = 1 + Ea (divide by 2, then use Ea).
• newE(a+1) = 1 + (Ea + E(ap1)) / 2 (average of two cases, +1 for the operation).

If the bit is ‘1’ (odd number):

• newEa = 1 + (Ea + E(ap1)) / 2
• newE(ap1) = 1 + E(ap1)

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
const int inv2 = 500000004; // Modular inverse of 2 under MOD
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
 
        long long E_a = 0, E_ap1 = 1; // Initial values after processing the first bit '1'
 
        for (int i = 1; i < n; ++i) {
            char c = s[i];
            long long new_E_a, new_E_ap1;
 
            if (c == '0') {
                // Current number is even
                new_E_a = (1 + E_a) % MOD; //modulo operations.
                new_E_ap1 = (1 + (E_a + E_ap1) * inv2 % MOD) % MOD;
            } else {
                // Current number is odd
                new_E_a = (1 + (E_a + E_ap1) * inv2 % MOD) % MOD;
                new_E_ap1 = (1 + E_ap1) % MOD;
            }
 
            E_a = new_E_a;
            E_ap1 = new_E_ap1;
        }
 
        cout << E_a << '\n';
    }
 
    return 0;
}

Modulo Operations

Everything is kept within 10⁹ + 7 using the modular inverse of 2.
(This operation is an SOP in competitive programming to make the compiler deliver integers in the limit of the computational world.)

*To view the solution on CF you need to participate in at least one CF contest.