Online Java Practice Problem PascalCount

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)2003, TopCoder, Inc. All rights reserved.

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)

Class

public class PascalCount { public int howMany(int i, int d) { // fill in code here } }

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

Comments?

Last modified: Mon Mar 6 09:39:47 EST 2006