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:

http://oeis.org/A064194

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

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] ;
}


@anon41318104

1 Like

hey @cubefreak777 how do you put your code in a drop-down way(â–Ľ)? using some latex code?

Summary

1 Like
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