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
For example, suppose we have array
A = [4, 1, 3, 2, 4].
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
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
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
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.