BottlesOnShelf | Topcoder Archive

Problem Statement

There are N bottles on a shelf (numbered from 1 to N). Some little kids are playing football near the shelf. Sometimes it happens that their ball hits the shelf and every bottle with an index between left[i] and right[i], inclusive, that is also divisible by damage[i] falls on the ground and breaks.

Given N and the arrays left, right and damage. The ball has hit the shelf exactly M times, where M is the size of each of the three arrays. Count and return the number of bottles broken by the kids.

Definition

Class:: BottlesOnShelf
Method:: getNumBroken
Parameters:: int, int[], int[], int[]
Returns:: int
Method signature:: int getNumBroken(int N, int[] left, int[] right, int[] damage)
(be sure your method is public)

Constraints

N will be between 1 and 1,000,000,000, inclusive.
left, right and damage will each contain between 1 and 18 elements, inclusive.
left, right and damage will contain the same number of elements.
Each element of left and right will be between 1 and N, inclusive.
For each i, left[i] will be less than or equal to right[i].
Each element of damage will be between 1 and 42, inclusive.

Examples

```
7
```
```
{1}
```
```
{7}
```
```
{2}
```
```
Returns: 3
```
Every second bottle has been broken by the kids. The shelf looks like this (.-unbroken, X-broken): .X.X.X.
```
7
```
```
{1,1}
```
```
{7,7}
```
```
{2,3}
```
```
Returns: 4
```
Every bottle dividible by 2 or 3 has been broken. .XXX.X.
```
7
```
```
{1,1,1}
```
```
{7,7,7}
```
```
{2,3,6}
```
```
Returns: 4
```
Now every bottle divisible by 6 has been broken also, but the result is the same as in last example. .XXX.X.
```
10
```
```
{1,6}
```
```
{5,10}
```
```
{1,7}
```
```
Returns: 6
```
From the first half of the shelf, every bottle has been broken. From the second half only the bottle with number 7 has been broken. XXXXX.X...
```
5
```
```
{4}
```
```
{4}
```
```
{7}
```
```
Returns: 0
```
None bottle has been broken.

1000000000

{1}

{1000000000}

{1}

Returns: 1000000000

Every bottle has been broken.

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.