21/06/2021

[Java] Moments when all lights are blue

While looking for a different exercise, I found this one and decided to give it a go: given an array of unique integers in the range 1..N representing the moments when a light in position input[i] is turned on, return the number of moments when ALL lights are on (Y) in an interrupted sequence.
We call these sequences "blue lights", initially all lights are off (I).

Example:

1 2 3 4
I I I I


at moment 1 we turn on light 2:
1 2 3 4
I Y I I


light 2 is on, but not all lights up to the current moment (1) are on in an interrupted sequence
as we would need also light 1 to be on

at moment 2 we turn on light 1:
1 2 3 4
Y Y I I


lights 1 and 2 are on, at this moment all lights up to the current moment (2) are on in an interrupted sequence as there are no OFF lights in between 1..2

at moment 3 we turn on light 4:
1 2 3 4
Y Y I Y


lights 1,2,4 are on but light 3 is off. At this moment (3) not all lights are on in an interrupted sequence
since light 3 (end of current sequence) is off

at moment 4 we turn on light 3:
1 2 3 4
Y Y Y Y


at this moment (4) all lights are on in an interrupted sequence.

We need an uninterrupted sequence of lights to be on at a precise moment in order to consider it a blue sequence.
Since we have an array of length 1..N with values 1..N and no duplicates, there is only one moment where a certain light will be turned on.
If at moment X all lights 1..X are on, it means we flipped all switches from 1 to X, which means we have seen all values in range 1..X in our array so far.


The sum of all numbers in this range is:

 X(X+1)/2
 

Therefore if at a certain moment X the sum of all values seen in the array is exactly equal to the sum of all numbers in range 1..X, we have flipped all switches up to X and therefore have an uninterrupted sequence of lights.
We simply count how many times does this happen while walking over the whole array and have our result.

Time complexity is O(N) and space is O(1).

You can check my implementation of momentsWhenBulbsAreBlue on my Gist along with some tests in MomentsWhenBulbsAreBlueJTests.
   

No comments:

Post a Comment

With great power comes great responsibility