# Saitama’s Punch

#### CONCEPTS USED:

Basic Mathematics

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:

```#include <stdio.h>

int main()
{
int t; scanf("%d", &t);
while(t--){
int n, k; scanf("%d %d", &n, &k);
int arr[n];
for(int i=0; i<n; i++)
scanf("%d", &arr[i]);

long long sum = 0;
long long curr_time = arr + k;
for(int i=1; i<n; i++){
if(curr_time <= arr[i]){
sum += k;
}
else{
sum += arr[i] - arr[i-1];
}
curr_time = arr[i] + k;
}
/* adding time for the last punch */
sum += k;

printf("%lld\n", sum);
}

return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;

int main()
{
int t; cin>>t;
while(t--){
int n, k; cin>>n>>k;
int arr[n];
for(int i=0; i<n; i++)
cin>>arr[i];

long long sum = 0;
long long curr_time = arr + k;
for(int i=1; i<n; i++){
if(curr_time <= arr[i]){
sum += k;
}
else{
sum += arr[i] - arr[i-1];
}
curr_time = arr[i] + k;
}
/* adding time for the last punch */
sum += k;

cout << sum << endl;
}
return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();

while(t --> 0){
int n = sc.nextInt();
int k = sc.nextInt();
int arr[] = new int[n];

for(int i=0; i<n; i++)
arr[i] = sc.nextInt();

long sum = 0;
long curr_time = arr + k;

for(int i=1; i<n; i++){
if(curr_time <= arr[i]){
sum += k;
}
else{
sum += arr[i] - arr[i-1];
}
curr_time = arr[i] + k;
}
/* adding time for the last punch */
sum += k;

System.out.println(sum);

}
}
}

```