Optimizing Diwali Lights problem in C

Question

I was trying to solve the Diwali Lights challenge on HackerRank.

Problem Statement

On the eve of Diwali, Hari is decorating his house with a serial light bulb set. The serial light bulb set has N bulbs placed sequentially on a string which is programmed to change patterns every second. If atleast one bulb in the set is on at any given instant of time, how many different patterns of light can the serial light bulb set produce?

Note: Lighting two bulbs *-* is different from **-

Input Format

The first line contains the number of test cases T, T lines follow. Each line contains an integer N, the number of bulbs in the serial light bulb set.

Output Format

Print the total number of patterns modulo 10⁵

Constraints

1 <= T <= 1000
0 < N < 10⁴

Sample Input

2
1
2

Sample Output

1
3

The Code I had written is

#include<stdio.h>
# define MAX 10000 // assuming we need first 100 rows
unsigned long long triangle[MAX + 1][MAX + 1];

void makeTriangle() {
    int i, j;

    // inietialize the first row
    triangle[0][0] = 1; // C(0, 0) = 1

    for(i = 1; i < MAX; i++) {
        triangle[i][0] = 1; // C(i, 0) = 1
        for(j = 1; j <= i; j++) {
            triangle[i][j] = (triangle[i - 1][j - 1] + triangle[i - 1][j]) %100000;
        }
    }
}

unsigned long long C(int n, int r) {
    return triangle[n][r];
}
/*long long C(int N, int R)
    {
        if(R > N/2) R = N - R;
        int i;
        unsigned long long ans = 1;
        for(i=1; i<=R; i++)
        {
            ans *= N-R+i;
            ans /=i;
        }
    //  printf("N=>%d R=>%d ANS=>%lld\n", N, R, ans);
        return ans;
    }
 */
int main()
{
    makeTriangle();
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int N;
        scanf("%d", &N);
        //  int copy = N;
        int i;
        unsigned long long int answer =0;
        switch (N)
        {
        case 1:
            printf("1\n");
            break;
        case 2:
            printf("3\n");
            break;
        default:
        {   
            int limit = N%2==0? (N /2) -1:(N/2);    // Caluculate nCr till N/2 and multiply by 2
            int n_even =0;
            if( N%2 ==0)            // calculate nC(n/2) only when N is Even
            {
                n_even = C(N,N/2);  
            }
            for(i=1;i<=limit;i++)
            {
                answer +=(2*C(N,i));
                answer %= 100000;
            }
            printf("%lld\n", (answer+ 1+ n_even) % 100000); //+1 is for nCn which is 1 always 
            break;
        }
        }
    }
    return 0;
}

The answer is pretty straightforward as it can be obtained by the summation of nCr. But there were a few hiccups when I tried to implement the same.

In my first attempt I had used the commented function C(N,R) to calculate the nCr each and every time for all the test cases. But this approach gave me a TLE error. So I decided I'd compute the values for nCr for all the values in with the makeTriangle() function and then whenever I called this function it would return me the computed value by looking up the array in O(1) time.

However, even this approach gave me a Time limit Exceeded error. Hence I was wondering if there could be any other optimizations that I could do with this code or a possible different approach to this problem :)

Answer 1

As @vnp has pointed out, each bulb can have two states, so the number of possibilities is \$2^N\$. However, the state where all bulbs are off is prohibited, so subtract one, and is the answer is simply \$(2^N -1) \mod 10^5\$.

The tricky part of the problem is that \$2^{{10}^4} -1\$ is a very large number to work with, so calculating \$(2^N -1) \mod 10^5\$ is a non-trivial problem.