I want to find the number of even parity numbers between two integers. Here is what I’ve written so far:

#include <bits/stdc++.h> using namespace std; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define ll long long int bool findParity(ll x) { ll y = x ^ (x >> 1); y = y ^ (y >> 2); y = y ^ (y >> 4); y = y ^ (y >> 8); y = y ^ (y >> 16); if (y & 1) return 1; return 0; } void solve() { ll a,b; cin >> a >> b; ll evenparity = 0; for(ll i = a; i <= b; ++i){ if(findParity(i)==0) evenparity++; } cout << evenparity; } signed main() { fastio; solve(); return 0; }

This works fine. However, the difference between the two integers `a`

and `b`

can be as high as `10^11`

, which means that an `O(n)`

solution like this would not work. Is there a more efficient i.e `O(1)`

solution to this problem?

## Answer

All you need is a function which calculates the even parity numbers from [0-x] interval, let’s call it sumParity, then simply return sumParity(b)-sumParity(a-1). (If I understood properly you are looking for the [a,b] closed interval.)

If start counting the parity from zero, and pair the numbers, (0-1), (2,3), (4,5) then each of these pairs has exactly 1 even and 1 odd parity. (These pairs only differ in the lowest bit).

So, if x is odd, then sumParity(x) = (x+1)/2, otherwise x/2 + parity(x).

(You already has the parity(x) function)

f(a,b) = sumParity(b)-sumParity(a-1)

It works only for positive integers, but you can easily extends the logic to negative numbers too.