Count Number of Binary Strings1

#1

what’s wrong with my code
i have tried both approaches, bottom up as well as top down, in both approaches it shows WA
pls check, go to my submissions for code else i will send u the link

#2

@archit_18 hey archit share your implementation with us through cb.lk/ide we will help you out.

#3

sure, here’s the link

#4

@archit_18 hey archit a simple solution is could be with bottom up dp.
make a function n_digits and pass the value of n in the function
inside the function declare two array inside the function int a[n],int b[n]
and mark index 0 of both the array is 1
like
a[0]=1;
b[0]=1;
now apply a loop from i=1 to upto <=n
and do
a[i]=a[i-1]+b[i-1];
b[i]=a[i-1];
and return
a[n-1]+b[n-1];
do dry run on this logic

#5

yes i’ve tried that too, but it also shows WA

#6

have a look at this
int main()
{
int t; cin>>t;
while(t–){
int n;
cin>>n;
int a[n],b[n];
a[0]=b[0]=1;
for(int i=1;i<n;i++){
a[i] = a[i-1]+b[i-1];
b[i]=a[i-1];
}
debug1(a[n-1]+b[n-1]);
}
return 0;
}

#7

@archit_18 hey archit your approach is right but replace your debug1 line as cout<<a[n-1]+b[n-1]<<endl;
and use long long int instead of int because data type is not strong enough to store the result.

1 Like
#8

debug1() does the same work as cout<<a[n-1]+b[n-1]<<endl;.
maybe it was the issue of data type. i’ll try after changing to ll

#9

it worked after changing datatype, thanks

#10

pls tell me what’s wrong with this approach
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[100][2];
ll solve(int n, int ld)
{
if(n == 1){
return 1;
}
if(dp[n][ld]!=-1){
return dp[n][ld];
}
int ans=0;
if(ld == 0){
ans = solve(n-1, 0) + solve(n-1, 1);
}
else{
ans = solve(n-1, 0);
}
return dp[n][ld] = ans;
}
int main()
{
int t; cin>>t;
while(t–){
int n;
cin>>n;
memset(dp,-1,sizeof(dp));
ll ans=0;
for(int i=0;i<2;i++){
ans+=solve(n, i);
}
cout<<ans<<endl;
}
return 0;
}

#11

Hello @archit_18,

The logic of your code is correct.
But, it is not printing the desired output for if the value of ans is large.
The output it is producing is junk values.

Why?
You have declared the ans in the main function as long long but forget to do the same for ans in the solve() function.

Give a like, if you are satisfied.
Hope, this would help.