PascalCount | Topcoder Archive

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.
```
0
```
```
3
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.