What's Next

Problem

Johnny is playing with a large binary number, B. The number is so large that it needs to be compressed into an array of integers, A, where the values in even indices (0, 2, 4, …) represent some number of consecutive 1 bits and the values in odd indices (1, 3, 5, …) represent some number of consecutive 0 bits in alternating substrings of B.

For example, suppose we have array A = [4, 1, 3, 2, 4]. A[0] represents 1111, A[1] represents 00, A[2] represents 111, A[3] represents 00, and A[4] represents 1111. The number of consecutive binary characters in the substring of corresponds to integer A[i], as shown in this diagram:

When we assemble the sequential alternating sequences of 1’s and 0’s, we get 11110111001111.

We define setCount(B) to be the number of 1’s in a binary number, B. Johnny wants to find a binary number, D, that is the smallest binary number >B where setCount(B) = setCount(D). He then wants to compress D into an array of integers, C (in the same way that integer array A contains the compressed form of binary string B).

Johnny isn’t sure how to solve the problem. Given array A, find integer array C and print its length on a new line. Then print the elements of array C as a single line of space-separated integers.

My Solution

I’m providing the solution for Python and JS, please leave on the comments if you found a better way.

This was a hard problem for me though it’s catalogued as medium, I had to ask for help, and I need to thank reddit for pointing me on the right direction for solving it.

It was also very tricky to handle all the edge cases, hence all the if statements and doing different stuff for different lengths.

Note that I’m also providing a “solution” for JS. The code is valid, though, way more complicated to understand than Python for several reasons, among them:

List handling of Python vs JS
Reducers vs simple functions
Sample inputs being huge numbers going out of the normal for JS ints

All calculations had to be performed as BigInt, but that’s not enough, for some cases on the sample inputs, the numbers were too big even for BigInt to handle. So the JS code won’t pass the validations on HackerRank, but the code is valid, and works if the numbers are within range.

def whatsNext(arr):
    # set bits are at each even index
    last_idx = len(arr) -1
    
    # case: last_idx == 0
    if last_idx == 0:
        if arr[0] == 1:
            # input is [1] => 1, then the output is [1,1] => 10
            print(2)
            print(*[1, 1])
        else:
            # input is [x] => 1*x, then the output is [1,1, x-1] => 10(1*[x-1])
            print(3)
            print(*[1, 1, arr[0] - 1])
        return

    # find index for least significant set bit
    # last_idx & 1 can be 0 or 1, 1 if last_idx ends with 1
    i = last_idx-1 if last_idx & 1 else last_idx

    # case: last_idx == 1
    if last_idx == 1:
        # the input has 2 elements, 1s and 0s
        # if the input is [2, 1] => 110 then the output is [1, 2, 1] => 1001
        t = [1, arr[1] + 1, arr[0] - 1]
        
    # case: last bit group is off
    elif last_idx != i:
        t = arr[:i-1] + [arr[i-1] -1, 1, arr[-1] + 1, arr[i] -1]
    # case: last bit group is set
    else:
        t = arr[:i-1] + [arr[i-1] -1, 1, 1, arr[i] -1]

    # handle zeros
    if not t[-1]:
        t.pop(-1)

    if t.count(0):
        i_lst = []
        for i,a in enumerate(t):
            if not a:
                #  combine bits around zero
                t[i-1] += t[i+1]
                i_lst.append(i)
                
        # remove zero and extra bits
        for i in i_lst[-1:-1-len(i_lst):-1]:
            t.pop(i+1)
            t.pop(i)

    print(len(t))
    print(*t)

function whatsNext(arr) {
    // set bits are at each even index
    const last_idx = arr.length -1;
    
    // case: last_idx == 0
    if (last_idx == 0) {
        if (arr[0] == 1) {
            // input is [1] => 1, then the output is [1,1] => 10
            console.log(2);
            console.log('1 1');
        } else {
            // input is [x] => 1*x, then the output is [1,1, x-1] => 10(1*[x-1])
            console.log(3);
            console.log(`1 1 ${BigInt(arr[0]) - BigInt(1)}`);
        }
        return;
    }

    // find index for least significant set bit
    // last_idx & 1 can be 0 or 1, 1 if last_idx ends with 1
    const i = last_idx & 1 ? last_idx-1 : last_idx;
    let t;

    // case: last_idx == 1
    if (last_idx == 1) {
        // the input has 2 elements, 1s and 0s
        // if the input is [2, 1] => 110 then the output is [1, 2, 1] => 1001
        t = [1, arr[1] + 1, arr[0] - 1];
    } else if (last_idx != i) {
        // case: last bit group is off
        t = arr.slice(0, i-1).concat([arr[i-1] -1, 1, BigInt(arr[arr.length-1]) + BigInt(1), BigInt(arr[i]) - BigInt(1)]);
    } else {
        // case: last bit group is set
        t = arr.slice(0, i-1).concat([arr[i-1] -1, 1, 1, BigInt(arr[i]) - BigInt(1)]);
    }

    // handle zeros
    if (!t[t.length - 1]) t.pop();

    // check if we have 0s
    if (t.reduce((v, acc) => v === 0 ? acc+1 : acc, 0) > 0) {
        const i_lst = [];
        const tl = t.length;
        for (let i=0;i<tl;i++) {
            if (t[i] === 0) {
                //  combine bits around zero
                t[i-1] = BigInt(t[i-1]) + BigInt(t[i+1]);
                i_lst.push(i);
            }
        }

        // remove zero and extra bits
        for (let i=-1;i>-1-i_lst.length;i--) {
            t.splice(i_lst[i_lst.length+i], 2);
        }
    }

    console.log(t.length);
    console.log(t.reduce((v, acc) => `${v} ` + acc));
}