Project Euler #148: Exploring Pascal's triangle.
Project Euler #148: Exploring Pascal's triangle.
+ 0 comments I have tried sum of all natural number ie for 8th row no of elements is S(8) for 8 row and 5 col it is S(8)  S( 8  5)
similerly there is some pattern in no divisible by 7 since number for row 14 = S(14)  S( 14  14)  (S(14/7) * S(6))
+ 1 comment import math f=math.factorial result=[] tc=int(raw_input()) for i in range(tc): n_row,n_col=raw_input().split(' ') count=0 for r in range(int(n_row)): c=0 while c<int(n_col) and c<r+1: value=(f(r)/(f(c)*f(rc))) if value%7!=0: count=count+1 c=c+1 result.append(count) for i in result: print i
I'm getting timed out!
+ 0 comments Is anyone getting the same answer as I got? my output: 12 3842 2852 for input: 3 5 3 100 100 100 50; As per the best of my knowledge I have written correct logic for program. So can you tell me whether my second and third output number is wrong or right?why?


+ 0 comments Got it for N == R. But not getting it right when R < N. Need to work on it. Any clue?
private static long pascal(int N, int R) { long count = 0; long div71 = 0; // divisible by 7 forming big pattern starting after row 49 long div72 = 0; // divisible by 7 forming small pattern starting after row 7 long div7 = 0; // Divisible by 7 long total = 0; int i = 0;
long n = N; i = 0; while (n >= 49) { div71 = div71 + i * (48 * 49)/2; div72 = div72 + (i+1) * (6 * 7)/2 * (6 * 7)/2; i++; n = n  49; } if(N > 7  n > 0) { if(N >= 49) div71 = div71 + i*(48*49/2)  i*(48n)*(49n)/2; else if(n > 7) { i = 0; while(n > 7) { div72 = div72 + (i)*(6*7)/2; n = n  7; i++; } if(n > 0) { div72 = div72 + (i)*(6*7)/2  (i)*(6n)*(7n)/2; } } } if(R >= N) total = N * (N+1)/2; else { total = R*(R+1)/2 + (NR)*R; } div7 = div71 + div72; count = total  div7; System.out.println("N: " + N + " R: " + R + " Total: " + total + " Count: " + count); return count; }
+ 1 comment I almost solved it in O(1) time. But according to my algo for test case 100,100 no of entries divisible by 7 is 3217. But testcase answer is 50502361 = 2869. How I am able to find more no of entries divisible by 7, than actually is.
Here is my algo......
8th row (7C1, 7C2, ... 7C6) are all divisible by 7;
9th row (8C2, 8C3, ... 8C6) are all divisible by 7;
10th row (9C3, 9C4, ... 9C6) are all divisible by 7;
11th row (10C4, 10C5, 10C6) are all divisible by 7;
12th row (11C5, 11C6) are divisible by 7;
13th row (12C6) is only no. divisible by 7;
14th row NONE is divisible by 7;
So I generalise it like this....
8th row (1 to 6) total 6 entries
9th row (2 to 6) total 5 entries
.
.
13the row (6) total 1 entries
Sum of entries divisible by 7 till 14th row is 6+5+4+...+1 = 21;
Start again with 15th row count entries divisible by 7.
15th row (113) total 13 entries
16th row (213) total 12 entries
.
.
20th row (613) total 8 entries
21th row 0 entries
Sum it 13+12+...+8 = (7+6)+(7+5)+(7+4)+...+(7+1) = (42 + 21);
Find Sum again from row 22nd to 28
For rows(2228): (42*2 + 21)
For rows(2935): (42*3 + 21)
.
.
Actually we can generalise it........
For rows(17): (0);
For rows(814): (42*0 + 21);
For rows(1521): (42*1 + 21);
For rows(2228): (42*2 + 21);
For rows(2935): (42*3 + 21);
For rows(3642): (42*4 + 21);
.
.
.
For rows(9298): (42*11 + 21);
For row 99th (98C1, 98C2, ... 98C97) total 97 entries are divisible by 7.
For row 100th 96 entries are divisible.
Total will be 3217 entries divisible by 7.
But in testcase answer it is 5050  2361 = 2689.
Can somebody explain where I am wrong....?
Please... Thanks...
Sort 12 Discussions, By:
Please Login in order to post a comment