Saitama’s Punch

CONCEPTS USED:

Basic Mathematics

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given an array A which contains the sorted time points at which a hero named Saitama punches and paralyzes his enemy Garou, also given time interval K for the time, his enemy is paralyzed with each punch. Your task is to determine the total time for which Garou is paralyzed.

See original problem statement here

For Example:

Input : 

N = 3, K = 2
A = [1 4 6]

Output : 6

Explanation : 

1st punch on time point = 1, paralyzes him for 2 units of time [1 to 2]

2nd punch on time point = 4, paralyzes him for another 2 units of time [4 to 5]

3rd punch on time point = 6, paralyzes him for another 2 units of time [6 to 7]

Therefore, Saitama paralyzes Garou for 6 units of time.
Input : 

N = 3, K = 2
A = [1 2 6]

Output : 5

Explanation : 

1st punch on time point = 1, paralyzes him for 2 units of time [1 to 2].

2nd punch on time point = 2, Garou is already paralyzed at this point of time, so he was only paralyzed for 2 - 1 = 1 unit of time with the first punch, now again he is paralyzed for another 2 units of time [2 to 3].

3rd punch on time point = 6, paralyzes him for another 2 units of time [6 to 7].

Therefore, Saitama paralyzes Garou for 5 units of time.

SOLVING APPROACH:

  1. Start by adding K to the first time point in the array and store it in palalyze_till variable, this will give us the time point till when the Garou is paralyzed by the first punch of Saitama.

  2. Now traverse the array starting from the second element and check whether the calculated paralyze_till is less than or equal to current element, A[i] of the array. This implies Garou was paralyzed for K units of time and now is awake according to data structures and algorithms. If Yes, increment the value of total_time by K and update paralyze_till = A[i] + K.

  3. If paralyze_till is greater than current element, A[i]. This implies that Garou is still paralyzed and again we need to paralyze it for K units of time. So we add the time for which it was paralyzed till now and move ahead, updating total_time = A[i] - A[i] and paralyze_till = A[i] + K.

  4. Finally add the time for which Garou was paralyzed by the last punch i.e. K units of time.

SOLUTIONS:

[TABS_R id=552]
[forminator_quiz id=”558″]

Space Complexity: O(1)
Previous post Minimum number of notes
Next post Quadrilateral

Leave a Reply

Your email address will not be published. Required fields are marked *