Codingame Solution: Number of letters in a number - Binary
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\)).
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}\)
\(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));