Please help to solve this problem

suman_18733097 · May 10, 2021, 7:48am

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

Output 1

Explanation 1

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

Input 2

Output 2

Explanation 2

There are many, but I guess you can understand

Input 3

1111111111

Output 3

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.

cubefreak777 · May 10, 2021, 7:55am

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 ?

suman_18733097 · May 10, 2021, 8:00am

The following is mentioned bro

a + b \le N

cubefreak777 · May 10, 2021, 8:00am

Ah I see, my bad.

anon41318104 · May 10, 2021, 8:00am

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)

cubefreak777 · May 10, 2021, 3:23pm

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.

cubefreak777 · May 10, 2021, 3:30pm

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

hyphencore79 · May 10, 2021, 4:14pm

Please explain the approach .

manvi_03 · May 10, 2021, 5:49pm

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

cubefreak777 · May 10, 2021, 6:01pm

Summary

manvi_03 · May 10, 2021, 6:04pm

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!

cubefreak777 · May 10, 2021, 6:05pm

Thanks!

dhruv788 · May 10, 2021, 10:20pm

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

hyphencore79 · May 11, 2021, 5:04am

What is the use of j in the function

kaustavbose · May 11, 2021, 5:31am

Same question

cubefreak777 · May 11, 2021, 8:11am

NOTATION:

S is the binary string given.
N is length of S.
(A,B) is any valid pair such that conditions given hold true.
X = A+B=A \oplus B
D(S) is the decimal representation of binary string S.
C(i) is the number of set bits in i.
S[i \dots N] is the suffix of S after index i.

We can reduce the problem to find the following summation, since it is given in the problem that A+B \le D \implies X \le D. So we just have sum up the number of pairs for all possible values of X. i.e. the following summation.

R= \sum_{X=0}^{D(S)} 2^{C(X)}

But how to find this? obviously, we can’t naively iterate overall all values from 0 to 2^N where N\le 10^5.
So we’ll use digit dp to find R.

DIGIT DP STATES AND TRANSITIONS:

DP[i] → \displaystyle \sum_{k=0}^{D(S[i \dots N])}2^{C(k)} i.e. Sum of 2^{C(k)} for all 0 \le k \le D(S[i \dots N]) in the suffix of S after index i.
Transitions are pretty straightforword.

IF S[i]=0:

Then it’d be the same as the answer we obtained at index i+1 (Since we have no option but to put a zero in here otherwise it’ll be greater than D(S[i \dots N])

\boxed{DP[i]=DP[i+1]}

IF S[i]=1:

Now we can put either a zero or a 1 at index i.
If we happen to put a 0 then for the entire suffix from i+1 to N we can have any number of set bits we want. So the number of numbers with k set bits would just be \displaystyle \binom{N-1-i}{k} but since the contribution of each number with k set bits is 2^k so total contribution would be \displaystyle \sum_{k=0}^{N-1-i}\binom{N-1-i}{k}2^k
But what if we put a 1 at index i then it is clearly evident that it is the sub subproblem for suffix from i+1 that we solved already i.e. DP[i+1] but with one extra set bit so the contribution from this subpart will be 2 \times DP[i+1]. So the transition will look like.

DP[i]=2 \times DP[i+1]+\sum_{k=0}^{N-1-i}\binom{N-1-i}{k}2^k \\ \sum_{k=0}^{N-1-i}\binom{N-1-i}{k}2^k=(1+2)^{N-1-i}=3^{N-1-i} \\ \boxed{DP[i]=2 \times DP[i+1]+3^{N-1-i}}

Base case is DP[N]=1 and final answer R would just be DP[0].

ASYMPOTICS.

Time & Space complexity for this solution is \mathcal{O}(N)

CODE FOR REFERENCE

#include "bits/stdc++.h"
#define ll long long   
using namespace std ;
const int M = 1e9+7,mxN=1e7;
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(){
  string s ; cin >> s ;
  int n = s.size() ;  
  dp[n]=1;
  for(int i=n-1;~i;--i)
    dp[i]=(s[i]=='0'?dp[i+1]:(2*dp[i+1]+pM(3,n-1-i))%M)  ;
  cout << dp[0] ;
}

Solutions that involve converting the entire string to integer as presented by @suman_18733097, won’t work for strings greater than length 10^4(thanks to python, C++ would’ve failed to handle strings of length 60 ) it is because you’re essentially storing 2^{10^5} in int data type which is way way too much!!.

cubefreak777 · May 11, 2021, 8:14am

You don’t need to have j, that was just for simplicity. j=N-1-i

Check this

#include "bits/stdc++.h"
#define ll long long   
using namespace std ;
const int M = 1e9+7,mxN=1e7;
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(){
  string s ; cin >> s ;
  int n = s.size() ;  
  dp[n]=1;
  for(int i=n-1;~i;--i)
    dp[i]=(s[i]=='0'?dp[i+1]:(2*dp[i+1]+pM(3,n-1-i))%M)  ;
  cout << dp[0] ;
}

hyphencore79 · May 11, 2021, 8:52am

Thank You for clearing doubt

anon41318104 · May 11, 2021, 11:47am

@cubefreak777 thanks a lot for helping

anon41318104 · May 11, 2021, 11:55am

@cubefreak777 could share some best resources to become good in dp