You can learn more about what to expect in these emails here.
Table of Contents
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:
A to B conversion example
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.
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.
defwhatsNext(arr):
# set bits are at each even index last_idx = len(arr) -1# case: last_idx == 0if 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-1if last_idx &1else last_idx
# case: last_idx == 1if 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 offelif last_idx != i:
t = arr[:i-1] + [arr[i-1] -1, 1, arr[-1] +1, arr[i] -1]
# case: last bit group is setelse:
t = arr[:i-1] + [arr[i-1] -1, 1, 1, arr[i] -1]
# handle zerosifnot t[-1]:
t.pop(-1)
if t.count(0):
i_lst = []
for i,a in enumerate(t):
ifnot a:
# combine bits around zero t[i-1] += t[i+1]
i_lst.append(i)
# remove zero and extra bitsfor i in i_lst[-1:-1-len(i_lst):-1]:
t.pop(i+1)
t.pop(i)
print(len(t))
print(*t)
functionwhatsNext(arr) {
// set bits are at each even index
constlast_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
consti=last_idx&1?last_idx-1:last_idx;
lett;
// 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];
} elseif (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) {
consti_lst= [];
consttl=t.length;
for (leti=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 (leti=-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));
}
You can learn more about what to expect in these emails here.
Our website uses cookies to make your browsing experience better. By using our site you agree to our use of cookies. Learn more by reading our privacy policy.