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