What's Next

What's Next - A HackerRank challenge solution


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

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.

Read more on the challenge page…

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.

Si te gusta el contenido, por favor apoya mi trabajo!

Juan Cruz Martinez - Author @ Live Code Stream

Juan Cruz Martinez


Soy Juan Cruz Martinez, el fundador de LiveCodeStream.dev. Me encanta programar y creo en el poder de la programación no solo para construir un mundo mejor, sino para hacer que TU vida sea mejor.

Fundé LiveCodeStream.dev porque quería ayudarte a aprender a programar, construir una mejor carrera y, en última instancia, crear una vida mejor. Eso me sucedió hace más de una década cuando comencé a programar, y le sucede a decenas de miles de personas a diario. Quiero que TÚ te unas a esa revolución.

No importa cómo lo llames, escribir código, programación, desarrollo de software o cualquier otra cosa, las habilidades involucradas están en una demanda cada vez mayor. Y ya sea que quieras incursionar en el desarrollo de sitios web, diseño de juegos, desarrollo de blockchain o cualquier otra cosa, quiero ayudarte.