# Codesignal Solution: sumOdious

Original Problem

An odious number is a non-negative integer that has an odd number of 1s 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 106 + 7.

Example

• For k = 4, the output should be
sumOdious(4) = 14.

The sum of the first 4 odious numbers is 1 + 2 + 4 + 7 = 14.

• For k = 10, the output should be
sumOdious(10) = 95.

Input/Output

• [time limit] 4000ms (js)
• [input] integer k

Guaranteed Constraints:
1 ≤ k ≤ 109.

• [output] integer

The sum of the first k odious numbers, modulo 106 + 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

« Back to problem overview