×

# SPIT2-Editorial

Author : Ankit Sagwekar
Tester : Vikesh Tiwari
Editorialist : Ankit Sagwekar

Easy

# PREREQUISITES

basics,array,implementation

# PROBLEM

Given two integers 'm' and 'n'. Find the number of combinations of bit-size 'n' in which there are no 'm' consecutive '1'.

# EXPLANATION

We are given with m and n. There are 3 cases for any given value of n and m

• Case 1: when n is less than m for this the ans will be equal to ans=pow(2,n).
eg: 3 2 all the 2 bit words i.e 00 01 10 11 will not have 3 consecutive 1 ,thus all of them are selected.

• Case 2: when n is equal to m for this the ans will be equal to ans=pow(2,n)-1.
eg: 3 3 all the 3 bit words i.e 000 001 010 011 100 101 110 111 out of which only one word will have 3 consecutive '1'.

• Case 3: when n is more than m This test case needs some computation which we will see through eg.
eg: 3 4
Here we first calculate for
m n
3 3 = 7
3 2 = 4
3 1 = 2
then adding this ,we get for 3 4 as 7+4+2=13.
here m=3 thus we calculate for 3 values and add them .
eg:4 6
here we first calculate for
m n
4 5 = 29
4 4 = 15
4 3 = 8
4 2 = 4
then adding this ,we get for 4 6 as 29+15+8+4=56.
here m=4 thus we calculated for 4 values and add them .

Note: for faster computation we can precompute all the values and can store them in 2-D matrix.

(O(N^2.logN))

# C++ Code

#include <stdio.h>
#include<math.h>
int main(void) {
long long int t,n,m,i,j,k,a[15][105],l;
scanf("%lld",&t);
for(i=2;i<=10;i++)
for(j=1;j<=50;j++)
{
if(j<i)
a[i][j]=pow(2,j);
else if(j==i)
a[i][j]=pow(2,j)-1;
else
{
k=i;
l=j-1;
while(k>0)
{   k--;
a[i][j]+=a[i][l--];
}
}
}
/*

for(i=2;i<=10;i++)
{
for(j=1;j<=50;j++)
{
printf("%lld\t",a[i][j]);
}
printf("\n");
}
*/
// you can uncomment the above section to see all the precomputed values
while(t--)
{
scanf("%lld%lld",&m,&n);
printf("%lld\n",a[m][n]);
}
return 0;
}


2561314
accept rate: 27%

19.7k350498541

 0 Could you explain why this recurrence is true? answered 26 Jun '15, 00:29 2★skybolt 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,741
×825
×77

question asked: 23 Apr '15, 07:21

question was seen: 1,037 times

last updated: 26 Jun '15, 22:35