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

Input/Output

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