Codesignal Solution: sumOdious
An odious number is a nonnegative integer that has an odd number of 1
s in its binary representation. The first few odious numbers are therefore 1 ("1")
, 2 ("10")
, 4 ("100")
, 7 ("111")
, 8 ("1000")
, 11 ("1011")
, and so on.
Given an integer k
, find and return the sum of the first k
odious numbers, modulo 10^{6} + 7
.
Example

For
k = 4
, the output should besumOdious(4) = 14
.The sum of the first
4
odious numbers is1 + 2 + 4 + 7 = 14
. 
For
k = 10
, the output should besumOdious(10) = 95
.
Input/Output
 [time limit] 4000ms (js)

[input] integer k
Guaranteed Constraints:
1 ≤ k ≤ 10^{9}
. 
[output] integer
The sum of the first
k
odious numbers, modulo10^{6} + 7
.
Solution
This problem can be tackled by observing the pattern the series generates. For that, we implement the actual problem statement naively.
function count(n) { var s = 0; while (n) s+= n & 1, n>>= 1; return s; } function sumOdious(n) { var s = 0; var c = 0; for (var i = 1; c < n; i++) if (count(i) & 1) { s+= i; c++; } return s % (1e6 + 7); } for (var i=0; i <= 10; i++) { console.log(i, sumOdious(i)) }
After executing the code, we see the following series:
\[\{1, 3, 7, 14, 22, 33, 46, 60, ...\}\]
Looking up the pattern reveals the known series A173209 with the following closed form solution:
\[a(n) = n^2  (n + 1) \backslash 2 + \min(n \bmod 2, \text{hammingWeight}(n) \bmod 2)\]
We need the parity of the hamming weight here, which can be calculated recursively quite easily under the module two:
h = x => x ? 1 + h(x >> 1) & 1: 0
Given \(h\), the minimum of the parity of the hamming weight and \(n \bmod 2\) is simply
\[\min(n \bmod 2, \text{hammingWeight}(n) \bmod 2) := n \& 1 \& h(n) \]
Since we calculate everything under mod 2 already, we can remove the mod two from the \(h\) function:
h = x => x ? 1 + h(x >> 1) : 0
Finally, we can implement the whole solution:
m = 1e6 + 7 sumOdious = n => (n % m * n + (n & 1 & h(n))  (++n >> 1)) % m
There is one little optimization possible: We can move the definition of the \(h\)function into sumOdious.
m = 1e6 + 7 sumOdious = n => (n % m * n + (h = x => x ? n & 1 ^ h(x >> 1) : 0)(n)  (++n >> 1)) % m