TopCoder problem "ClapLight" used in SRM 196 (Division I Level One , Division II Level Two)

Problem Statement

    I have a light that changes from on to off or from off to on when I clap twice. The light's sensor samples the noise level in the room at short intervals and it triggers the light to change whenever it detects a low noise level followed by exactly 2 high noise levels followed by a low noise level.

"High" or "low" is based on a threshold noise level. When the sampled noise level is as high or higher than the threshold level, the noise level is classified as "high"; otherwise it is classified as "low". I have a int[] background that is a typical sequence of sensor readings when normal activity is taking place. I want software that will choose the threshold value so that it has the following properties:

  1. 1) It causes more than 50% of all the values in background to be classified "low".
  2. 2) It is the lowest possible threshold value that satisfies the 50% rule and that does not cause background to trigger the light to change.

Create a class ClapLight that contains a method threshold that is given the int[] background and that returns the desired threshold value.



Method signature:int threshold(int[] background)
(be sure your method is public)


-background will contain between 4 and 50 elements inclusive.
-Each element of background will be between 0 and 1000 inclusive.


Returns: 7
The threshold must be at least 7 to exceed more than 50% of the samples, and with the threshold set at 7 every reading will be classified "low" and the light will not be triggered.
{ 5,8,7,6,12,8,4,3,2,6 } 
Returns: 9
The threshold must exceed at least 6 of these values to satisfy the 50% rule. So it must be at least 7. But with the threshold set at 7 the sequence 5, 8, 7, 6 would trigger the light. A threshold of 8 will allow the sequence 6,12,8,4 to trigger the light. A threshold of 9 will never cause this sequence to trigger the light.
Returns: 2
Remember that the high noise levels must be both preceded and followed by low noise levels to trigger the light.
Returns: 4

Problem url:

Problem stats url:




zoidal , lbackstrom , brett1479

Problem categories:

Brute Force