We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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 5050-2361 = 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 (1-13) total 13 entries
16th row (2-13) total 12 entries
.
.
20th row (6-13) 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(22-28): (42*2 + 21)
For rows(29-35): (42*3 + 21)
.
.
Actually we can generalise it........
For rows(1-7): (0);
For rows(8-14): (42*0 + 21);
For rows(15-21): (42*1 + 21);
For rows(22-28): (42*2 + 21);
For rows(29-35): (42*3 + 21);
For rows(36-42): (42*4 + 21);
.
.
.
For rows(92-98): (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...
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #148: Exploring Pascal's triangle.
You are viewing a single comment's thread. Return to all comments →
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 5050-2361 = 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 (1-13) total 13 entries
16th row (2-13) total 12 entries
.
.
20th row (6-13) 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(22-28): (42*2 + 21)
For rows(29-35): (42*3 + 21)
.
.
Actually we can generalise it........
For rows(1-7): (0);
For rows(8-14): (42*0 + 21);
For rows(15-21): (42*1 + 21);
For rows(22-28): (42*2 + 21);
For rows(29-35): (42*3 + 21);
For rows(36-42): (42*4 + 21);
.
.
.
For rows(92-98): (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...