No of pairs aXorb==a+b in the range 1 to deimcal form of given binary string

for exam

givn string str=1000011101

find no of pairs of a,b in range 1 to decimal from of str

such that aXorb==a+b

I am pretty sure this problem is from one of the contests - Hackwithinfy and Infytq. It was one of the problems my friend had to solve. We later thought of upsolving it. I tried finding a pattern in the output - Wrote a brute-force solution and generated answers for smaller values of N. Luckily, I found the pattern on OEIS.

Hereâ€™s how it worked.

The sequence available on OEIS:

What you would like to stress more is this part: (The recurrence relation)

a(2n) = 3\times a(n),\ a(2n+1) = 2\times a(n+1)+a(n), with\ a(1) = 1.

The implementation.

## Python Code

```
import sys
sys.setrecursionlimit(10**6)
map = dict()
mod = 10**9 + 7
def solve(N):
if N in map:
return map[N]
elif N == 0:
return 0
elif N == 1:
return 1
elif N % 2 == 0:
ans = solve(N // 2)
map[N] = (ans * 3) % mod
return map[N]
else:
ans = 2 * solve(N // 2) + solve(N // 2 + 1)
map[N] = ans % mod
return map[N]
def main():
N = int(input(), 2) + 1
print(solve(N) % mod)
main()
```

This is a DP approach. Unfortunately, this approach was giving Segmentation fault in local machine for strings of length 10^6. Though it was still working fine with strings of length 10^5. The worst-case time it had taken to run against inputs of length 10^5 was around 1-2 seconds though.

Maybe, @cubefreak777 can help us with more optimal approach.

I hope this thing isnâ€™t ongoing?

Yup, these are recruiting contests (I guess) and are over ( I am sure).

I didnâ€™t go through your solution can you tell me your solutionâ€™s complexity? And some samples would be great if you have any.

Also, do we have a report number of ordered pairs or unordered pairs?

I guess I have the problem statement.

You are given a positive Integer N in base two. Your task is to print the total number of pairs of non-negative integers (a, b) that satisfy the following conditions.

- a + b \le N
- a + b = a \oplus b

Here \oplus operation represents the bitwise XOR Operation.

Since the answer could be extremely large print it modulo 10^9 + 7

Note: The Input does not contain leading zeroes.

**Input Format**

The first line contains a string, N, denoting the Integer N in base two.

**Constraints**

1 \le |N| \le 10^5

**Sample Input(s)**

Input 1

```
10
```

Output 1

```
5
```

Explanation 1

```
Pairs satisfying the conditions are: (0, 0), (0, 1), (0, 2), (1, 0), (2, 0)
```

Input 2

```
100
```

Output 2

```
11
```

## Explanation 2

There are many, but I guess you can understand

Input 3

```
1111111111
```

Output 3

```
59049
```

Explanation 3

```
Sample case for debugging purpose
```

My Approach (In between Naive and Optimal)

I read the given String into an Integer. In Python, `int(input(), 2)`

converts the given binary string into an integer. Then, I applied the Recurrence relation using a Dictionary to store previously calculated values. But still, it didnâ€™t work for large values of N.

Coming to the time complexity, I guess itâ€™s O(N\log N), where N is the length of Binary String.

For the first sample shouldnâ€™t the answer be 7 ? or may be I got the question wrong.

[i,j] = [0, 0]

[i,j] = [0, 1]

[i,j] = [0, 2]

[i,j] = [1, 0]

[i,j] = [1, 2]

[i,j] = [2, 0]

[i,j] = [2, 1]

these pairs ?

The following is mentioned bro

- a + b \le N

Ah I see, my bad.

**Sample test cases:**

1)input : 10

Output: 2

Explanation : As decimal equivalent 10 is 2.Only pairs are (1,2) and (2,1)

2)input: 101

Output: 10

Explanation : As decimal equivalent 101 is 5.Few pairs are (1,4),(1,2) and (2,1)

I think youâ€™re mistaken, a and b can be zero as well, according to the constraints given by Suman, also it makes more sense to include 0.

Sorry, I got a little caught up with something important so couldnâ€™t reply. I think we can solve it with digit dp. Iâ€™m attaching the code itâ€™s pretty neat to understand, though feel free to ping me if you need an explanation of my approach.

## CODE

```
#include "bits/stdc++.h"
#define ll long long
using namespace std ;
const int M = 1e9+7,mxN=1e5;
int dp[mxN+1] ;
ll pM(ll b,int p){
ll r=1 ;
for(;p;b=(b*b)%M,p/=2)
if(p&1)
r=(r*b)%M ;
return r ;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s ; cin >> s ;
int n = s.size() ;
dp[n]=1;
for(int i=n-1,j=0;~i;--i,j++)
dp[i]=(s[i]=='0'?dp[i+1]:(2*dp[i+1]+pM(3,j))%M) ;
cout << dp[0] ;
}
```

Please explain the approach .

## Thanks

Thatâ€™s a really cool thing. thanks a lot @cubefreak777 . btw got to know about your final exams from a thread. All the very best!

Thanks!

If the iâ€™th bit is set in the string then if you keep that bit unset you have 3 combinations for all remaining bits , those are {{0,1},{1,0},{0,0}}.

You cannot have {1,1} as its xor will be 0 whereas sum will be more than 0.

Where as to keep that bit set you have 2 combination available {{1,0},{0,1}}

What is the use of j in the function

Same question