Codingame Solution: Number of letters in a number - Binary

Original Problem

Goal

Find the nth term in the sequence starting with $$S(0) = \text{start}$$ and defined by the rule:

Given a term in the sequence, $$S(i)$$, the next term, $$S(i+1)$$ can be found by counting the letters (ignoring whitespace) in the spelled-out binary representation of $$S(i)$$.

As an example, starting from 5 ($$S(0) = 5$$), we convert to the binary representation, 101, then spell it out as an English string "one zero one", and count the letters which yields 10 ($$S(1) = 10$$).
Input
Line 1: integers start and n, separated by a space
Output
Line 1: the nth term in the sequence, expressed as an integer
Constraints
$$1 \leq n \leq 10^{18}$$
$$1 \leq \text{start} \leq 10^{18}$$

Solution

To pass all tests, we work with BigInt the whole time. Since we need to count the number of digits of the binary representation, we write a count function for that job:

function count(x) {
let r = 0n;
while (x) {
r+= 4n - (x & 1n);
x>>= 1n;
}
return r;
}

First I got impressed by the range of the input value $$n$$, but the series converges pretty fast so that a naive implementation works perfectly well

let [start, n] = readline().split .map(x => BigInt(x));
for (var i = 0; i < n; i++) {
var next = count(start);
if (start == next) {
break;
}
start = next;
}
print(parseInt(start));

« Back to problem overview