Optimizing Diwali Lights problem in C 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 105
  
  Constraints
  
  1 &lt;= T &lt;= 1000
  0 &lt; N &lt; 104
  
  Sample Input

2
1
2

  
  Sample Output

1
3



The Code I had written is 

#include&lt;stdio.h&gt;
# 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 &lt; MAX; i++) {
        triangle[i][0] = 1; // C(i, 0) = 1
        for(j = 1; j &lt;= 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 &gt; N/2) R = N - R;
        int i;
        unsigned long long ans = 1;
        for(i=1; i&lt;=R; i++)
        {
            ans *= N-R+i;
            ans /=i;
        }
    //  printf("N=&gt;%d R=&gt;%d ANS=&gt;%lld\n", N, R, ans);
        return ans;
    }
 */
int main()
{
    makeTriangle();
    int T;
    scanf("%d", &amp;T);
    while(T--)
    {
        int N;
        scanf("%d", &amp;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&lt;=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 :)
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.