ProductSet | Topcoder Archive

Problem Statement

You are given three inclusive ranges of nonnegative integers. R_i = [ lows[i], highs[i] ] denotes the ith range. Define the set S as follows:

	S = { a₁ * a₂ * a₃ : a_i in R_i }

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

```
{1,1,1}
```
```
{2,2,2}
```
```
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
```
{0,1,1}
```
```
{2,2,2}
```
```
Returns: 5
```
Now the possible products are 0, 1, 2, 4, and 8.
```
{0,0,0}
```
```
{100,100,100}
```
```
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.
```
{100,100,1}
```
```
{100,100,1}
```
```
Returns: 1
```
```
{0,0,0}
```
```
{100,100,0}
```
```
Returns: 1
```

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.