TopCoder Statistics - Problem Statement

Problem Statement

The top few rows of Pascal's triangle are drawn below:

                 1
               1   1
             1   2   1
           1   3   3   1
         1   4   6   4   1

The leftmost and rightmost values of a particular row are always 1. An inner value v can be found by adding together the 2 numbers found immediately above v, on its right and left sides. For example, the 6 in the above figure is the sum of the two 3s above it. Return the number of values in row i of Pascal's triangle that are evenly divisible by d. The rows are 0-based, so row 3 contains 1,3,3,1.

Definition

Class:: PascalCount
Method:: howMany
Parameters:: int, int
Returns:: int
Method signature:: int howMany(int i, int d)
(be sure your method is public)

Notes

The jth element (0-based) of row i can be computed by the formula: i! --------------- j! * (i-j)! where k! = 1*2*...*k and 0! = 1.

Constraints

i will be between 0 and 5000000 inclusive.
d will be between 2 and 6 inclusive.

Examples

3

3

Returns: 2

Row 3 is 1,3,3,1 so there are 2 elements divisible by 3.
3

4

Returns: 0

Row 3 has no elements that are divisible by 4.
4

2

Returns: 3

1,4,6,4,1 has 3 elements divisible by 2.
4

6

Returns: 1

Row 4 has a single element divisible by 6.
5000000

6

Returns: 4999315
5000000

2

Returns: 4999745
5000000

3

Returns: 4999569
5000000

4

Returns: 4998977
5000000

5

Returns: 4999956
0

3

Returns: 0
2500000

2

Returns: 2499745
2500000

3

Returns: 2499425
2500000

4

Returns: 2498977
2500000

5

Returns: 2499989
2500000

6

Returns: 2499173
3333333

2

Returns: 3325142
3333333

3

Returns: 3332470
3333333

4

Returns: 3296470
3333333

5

Returns: 3284182
3333333

6

Returns: 3324286
101

2

Returns: 86
101

3

Returns: 84
101

4

Returns: 70
101

5

Returns: 92
101

6

Returns: 72
1671174

3

Returns: 1670743
2545758

4

Returns: 2529375
1741859

5

Returns: 1696860
4852974

5

Returns: 4690975
1743118

5

Returns: 1599119
718439

5

Returns: 684690
2199093

2

Returns: 2198070
3675517

2

Returns: 3671422
552351

5

Returns: 550432
2298594

5

Returns: 2269795
3556885

6

Returns: 3555004
2456621

4

Returns: 2440238
28977

6

Returns: 28640
3056625

3

Returns: 3050794
2892268

6

Returns: 2886065
3249155

5

Returns: 3233796
3969917

2

Returns: 3953534
4599836

5

Returns: 4484637
2774631

4

Returns: 2756200
3044694

6

Returns: 3031339
1626425

6

Returns: 1623488
2541633

4

Returns: 2540738
3788324

2

Returns: 3786277
206421

6

Returns: 205532
3951827

2

Returns: 3947732
1378788

4

Returns: 1376741
1326812

3

Returns: 1325085
2502673

3

Returns: 2501522
4794629

3

Returns: 4788798
4924436

2

Returns: 4924181
5000000

6

Returns: 4999315
500000

3

Returns: 484449
5000000

4

Returns: 4998977
5000000

2

Returns: 4999745
5000000

5

Returns: 4999956
500000

4

Returns: 499617
4987451

6

Returns: 4983884
4999999

6

Returns: 4991552
4983214

4

Returns: 4979119
500000

6

Returns: 484329
50000

5

Returns: 49993
3489965

6

Returns: 3449640
100000

6

Returns: 99507
3

6

Returns: 0
4987451

4

Returns: 4980284
4

6

Returns: 1
12

4

Returns: 7
8

5

Returns: 1

Statistics

Problem Statement for "PascalCount"

Problem Statement

Definition

Notes

Constraints

Examples