C: Bits

https://open.kattis.com/problems/bits

• Firstly, we can keep successively (integer) dividing the number by $10$ to obtain the previous states of the calculator.

• Now, for each such number, we need to count the number of ones in the binary representation, and find the maximum value among those counts.

• This is now the classic problem of converting a number to its binary representation.

  • There are builtin functions to do this! bin(x) in Python, Integer.toBinaryString(x) in Java, and bitset<32>(x).to_string() in C++ all give you the binary representation of the number.

C++ is amazing: __builtin_popcount(x) directly gives you the number of ones in the binary representation of the integer x!