2
\$\begingroup\$

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 <= T <= 1000
0 < N < 104

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 :)

\$\endgroup\$
  • 2
    \$\begingroup\$ Correct me if I am wrong. There are \$2^N\$ patterns, and only one of them has no bulbs on. \$\endgroup\$ – vnp Feb 22 '15 at 6:00
  • \$\begingroup\$ @vnp Yes, I checked and the answer is indeed 2^N patterns. Could you tell me how you arrived at that expression? \$\endgroup\$ – thebenman Feb 22 '15 at 13:16
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The key thing to note from here is that \$a^b \; \text{mod} \; n\$ has a well known method. \$\endgroup\$ – Veedrac Feb 22 '15 at 19:37
  • \$\begingroup\$ @Veedrac Could you explain what the method is? Is it Binary Exponentiation? \$\endgroup\$ – thebenman Feb 25 '15 at 13:31
  • 1
    \$\begingroup\$ @thebenman en.wikipedia.org/wiki/… \$\endgroup\$ – Veedrac Feb 25 '15 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.