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