CODEWITHSUNDEEP
c
lacer
lacer

Reputation: 81

0-1 sequences without repeating 1's

My task is to write a program, where the input is an exponent of 2, and the output is the number of sequences (out of the maximum 2^n sequences) where there are no 1's next to each other. (n<=50)

For example, on the input of 3, the output is 5, because 2^3=8 and out of the 8 possibilities the only acceptable ones are: (000, 001, 010, 100, 101) and (110,011,111) are not acceptable because there are 2 or more 1's next to each other.

My program works fine until 31, upon the number 32 it stops working, overflow issues I guess. I tried long int and unsigned int, none of those seemed to help. 

#include <stdio.h>
#include <math.h>

main(){
    int t,i,n,j,ki;
    scanf("%d",&t);
    for (i=1;i<=t;i++){
            scanf("%d",&n);
            ki=pow(2,n)-(n*(n-1))/2;
            printf("Scenario #%d:\n%d\n\n",i,ki);
    }
    return 0;
}

Help me pl0x.

Upvotes: 0

Views: 131

Answers (1)

barak manos
barak manos

Reputation: 30166

For variable ki:

Step #1: Use unsigned long long instead of int.

Step #2: Use 1<<n instead of pow(2,n).

Step #3: Use llu% instead of %d.

int main()
{
    int t,i,n;
    unsigned long long ki,one=1;
    scanf("%d",&t);
    for (i=1;i<=t;i++)
    {
        scanf("%d",&n);
        ki = (one<<n)-n*(n-1)/2;
        printf("Scenario #%d:\n%llu\n\n",i,ki);
    }
    return 0;
}

Upvotes: 2

Related Questions