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).
2 Likes
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
1 Like
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] ;
}
1 Like
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! 
1 Like
Thanks! 
1 Like
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}}
2 Likes
What is the use of j in the function
Same question