Problem Statement |
| | You are given three inclusive ranges of nonnegative integers. Ri = [ lows[i], highs[i] ] denotes the ith range.
Define the set S as follows:
S = { a1 * a2 * a3 : ai in Ri }
In other words, S is the set of all possible products formed by taking exactly one element from each of the three ranges. Return the number of distinct values in S. |
| |
Definition |
| | | Class: | ProductSet | | Method: | howMany | | Parameters: | int[], int[] | | Returns: | int | | Method signature: | int howMany(int[] lows, int[] highs) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | lows and highs will each contain exactly 3 elements. |
| - | Each element of highs will be between 0 and 100, inclusive. |
| - | Element i of lows will be between 0 and highs[i], inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 4 | The possible distinct products are 1, 2, 4, and 8. All of the products are listed below:
1*1*1 = 1
1*1*2 = 2
1*2*1 = 2
1*2*2 = 4
2*1*1 = 2
2*1*2 = 4
2*2*1 = 4
2*2*2 = 8
|
|
|
| 1) | |
| | | Returns: 5 | | Now the possible products are 0, 1, 2, 4, and 8. |
|
|
| 2) | |
| | | Returns: 46912 | | Note that the maximum possible product is 100*100*100 = 1 million. Marking off all possible products, we see there are only 46912 distinct values. |
|
|
| 3) | |
| | |
| 4) | |
| | |