Question

Infosys || OA || DSE || Power Programmer || 2023

Answer 1

Problem Statement:

 

In a large factory, there are N walls that the owner painted with different types of paints. Due to the humidity and the difference in the type of paints each wall i will take Xi minutes to dry.

 

However, there is a magic machine that we can set to work for a certain integer number of minutes and put it in front of a certain wall to speed up the drying process.

 

It is given the machine cannot be moved during its work or it will break. Also, for every minutes of work of this machine, it decreases the time remaining to dry the wall in front of it by K minutes. It is also given that if the remaining drying time for a wall is less than K, it will become 0 and dry up without any problems.

 

Your task is to find the minimum number of minutes in which all the walls of the factory can be dried.

 

Note:
We have one machine, but after finishing a wall we can move this machine to another wall.

 

Input format:

 

The first line contains an integer N, denoting the number of elements in X.
The next line contains an integer K, denoting the magic machine's acceleration number.
Each line i of the N subsequent lines (where 0 <= i < N) contains an integer describing Xi.

 

Constraints:
1 <= N <= 10^5
1 <= K <= 10^9
1 <= X[i] <= 10^9

 

Test cases:

 

Input:
1
1
1
Output:
1
Explanation:
We will let it dry without using the magic machine

 

Input:
1
2
1
Output:
1
Explanation:
We will let it dry without using the magic machine

 

Input:
1
17
35
Output:
3
Explantion:
We will use the magic machine three times in a row on the first element.