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
  • 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, 2015 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, 2015 at 13:16

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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