# { What's Next }

Solving the Programming Challenge

# 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` represents `1111`, `A` represents `00`, `A` represents `111`, `A` represents `00`, and `A` 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 == 1:
# input is  => 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 - 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, arr - 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 == 1) {
// input is  => 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) - 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, arr - 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));
}
``````