Efficiently Count Number of Ones at Deepest Level in Recursive Floor-Ceil Splitting of Large Binary Number

I made something, it can handle 10**6 bits fine but the more you increase the load the heavier it becomes you can comment out outputs and try it out with 10**6

Without output print() won't block I/O and it'll run faster

#import time
## division
def div(n):
    if n == 1:
        return (1,)
    return (n // 2 + 1, n // 2) if n % 2 else (n // 2, n // 2)
## check if all items is 1s
def is_complete(lst):
    return all(x == 1 for x in lst)

## list without 1s
## use between levels
def delete(lst):
    return [x for x in lst if x != 1]

def next_level(lst):
    new_lst = []
    for x in lst:
        new_lst.extend(div(x))
    return new_lst

inp = int(input("-> "))
#inp = 10**5
#inp = 10**6
#inp = 10**7
level = 0
current = [inp]

## keep looping until all equals 1
start = time.time()
while not is_complete(current):
    current = delete(current)
    print(f"level {level}: {current}")
    current = next_level(current)
    level += 1
#print(f"took: {time.time()-start} seconds to finish")
Mod = 10**9+7
## comment prints for faster result
## leave only the prints you need
print(f"level {level}: {current}")
print(f"Number of 1s(ones): {len(current)}")
print(f"Modulo is: {len(current)%Mod}")

It took ~5(4.9) On my machine when using 10**7 (with outputs )

A recursive approach would divide the number by 2 according to the given rules, which means the string of binary digits is stripped from its rightmost digit, and of that digit was a 1, that should become a "carry" for one of the two partitions (since it must add this 1 to the half). Instead of stripping the digit, you could just have an index point to the last digit without really altering the input string.

Also, you would benefit from memoization, based on that index and whether there is a carry or not. This would make the algorithm run in linear time in terms of the number of digits in the input string.

Here is an implementation in JavaScript:

const MOD = 1000000007;

// Recursive helper function for the main function further down:
function recur(dp, s, index, carry) {
    if (dp[carry][index] == 0) { // Not memoized yet?
        if (+s[index] === carry) { // Number is even, so subtrees are equal:
            const res = recur(dp, s, index - 1, carry);
            dp[carry][index] = [(res[0] * 2) % MOD, res[1] + 1];
        } else { // Number is odd, so one of them gets a carry
            const left = recur(dp, s, index - 1, 0);
            const right = recur(dp, s, index - 1, 1);
            if (left[1] == right[1]) { // Both subtrees have same height
                dp[carry][index] = [(left[0] + right[0]) % MOD, left[1] + 1]; // Add up
            } else { // The right subtree is higher:
                dp[carry][index] = [right[0], right[1] + 1]; // Keep count from largest subtree only
            }
        }
    }
    return dp[carry][index];
}

// Main function: s is the input string of binary digits.
function recursive(s) {
    // Prepare for memoization:
    const dp = [Array(s.length).fill(0), Array(s.length).fill(0)]; // 1st dimension is carry (0 or 1), 2nd is index in s
    // Fill in base cases:
    dp[0][0] = [1, 0]; // Reaching leaf without carry: count is 1, subtree height is 0
    dp[1][0] = [2, 1]; // Reaching leaf with carry: count is 2, subtree height is 1.
    return recur(dp, s, s.length - 1, 0)[0];
}

With the final snippet below you can run it.

Iterative approach

When we analyse this problem a bit more, we find that the leaves of the binary tree that would be traversed through recursion, are all located in the two deepest levels of that tree. This can be shown like this:

A shortest root-to-leaf path in the tree is the one to the leftmost leaf, i.e. where each edge represents a division by 2 and flooring the result. There are ⌊log₂𝑛⌋ such edges on this path. A longest root-to-leaf path is achieved by the path to the rightmost leaf. Here each edge represents a division by 2 and ceiling the result. There are ⌈log₂𝑛⌉ edges on that path. The difference between these two path lengths is at most 1, and so the leaves of any such tree can be at the bottom two levels only.

The leaves that are on the one-but-bottom level, are the nodes that would become parents if the input value were to increase to the next power of 2. So the distance of 𝑛 to the least power of 2 that is not less than 𝑛, is the number of leaves that are not at the bottom level.

This is 2^{⌈log₂𝑛⌉}−𝑛.

As we know the total number of leaves is 𝑛, the desired outcome is 𝑛−(2^{⌈log₂𝑛⌉}−𝑛) or 2𝑛−2^{⌈log₂𝑛⌉}.

In other words, we can leave out the most significant (leftmost) digit, which will always be a 1, and evaluate what remains and multiply it by 2. Only when the input has no other 1-digit (when it is a power of 2) we need to return that power itself, not 0.

Here is code for that approach:

function iterative(s) {
    let power = 1;
    let n = 0;
    for (let i = s.length - 1; i > 0; i--) {
        power = (power * 2) % MOD
        if (s[i] == "1") n = (n + power) % MOD;
    }
    return s.lastIndexOf("1") ? n : power;
}

The following runnable snippet calculates the result for 𝑛 up to 10000, using both above described solutions, and asserts that the outcomes are the same:

const MOD = 1000000007;

function recur(dp, s, index, carry) {
    if (dp[carry][index] == 0) { // Not memoized yet?
        if (+s[index] === carry) { // Number is even, so subtrees are equal:
            const res = recur(dp, s, index - 1, carry);
            dp[carry][index] = [(res[0] * 2) % MOD, res[1] + 1];
        } else { // Number is odd, so one of them gets a carry
            const left = recur(dp, s, index - 1, 0);
            const right = recur(dp, s, index - 1, 1);
            if (left[1] == right[1]) { // Both subtrees have same height
                dp[carry][index] = [(left[0] + right[0]) % MOD, left[1] + 1]; // Add up
            } else { // The right subtree is higher:
                dp[carry][index] = [right[0], right[1] + 1]; // Keep count from largest subtree only
            }
        }
    }
    return dp[carry][index];
}

function recursive(s) {
    // Prepare for memoization:
    const dp = [Array(s.length).fill(0), Array(s.length).fill(0)]; // 1st dimension is carry (0 or 1), 2nd is index in s
    // Fill in base cases:
    dp[0][0] = [1, 0]; // Reaching leaf without carry: count is 1, subtree height is 0
    dp[1][0] = [2, 1]; // Reaching leaf with carry: count is 2, subtree height is 1.
    return recur(dp, s, s.length - 1, 0)[0];
}

function iterative(s) {
    let power = 1;
    let n = 0;
    for (let i = s.length - 1; i > 0; i--) {
        power = (power * 2) % MOD
        if (s[i] == "1") n = (n + power) % MOD;
    }
    return s.lastIndexOf("1") ? n : power;
}

// Test that both solutions return the same values for 0 < n < 10000
for (let n = 1; n < 10000; n++) {
    const bin = n.toString(2); // The input is a string of binary digits
    const a = recursive(bin);
    const b = iterative(bin);
    if (a !== b) throw "diff for n " + n;
}
console.log("The results are consistent for 0 < n < 10000");