Drive The Car

 

PROBLEM 51: Drive The Car

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 10/04/2023

Suppose you are a car driver and you have to drive a car on a track divided into "N" number of sub-tracks. You are also given the value of "K" i.e. the total kilometers the car can drive on each sub-track. If the car can't cover a sub-track, you can add any unit of Petrol to it. With each unit of petrol added, the total kilometers your car can travel will increase by one unit.You have to return the minimum unit of Petrol your car requires to cover all the sub-tracks. If no extra unit of petrol is required, return -1.

Solution: 

class Solution:

    def required(self, a, n, k):

        # Your code goes here

        cnt = 0

        l = []

        for i in a:

            if i <= k:

                pass

            else:

                cnt = (i-k)

                l.append(cnt)  

                k = i

        

        if cnt > 0:

            return sum(l)

        else:

            return -1

def main():

    T = int(input())

    while(T > 0):

        sz = [int(x) for x in input().strip().split()]

        n, m = sz[0], sz[1]

        a = [int(x) for x in input().strip().split()]

        ob=Solution()

        print(ob.required(a, n, m))

        T -= 1

if __name__ == "__main__":

    main()

Example 1:

Input:
N = 5, K = 7
arr[] = {2, 5, 4, 5, 2}
Output:
-1
Explanation:
No extra petrol required, as K is greater
than all the elemnts in the array hence -1.

Example 2:
Input:
N = 5, K = 4
arr[] = {1, 6, 3, 5, 2}
Output:
2
Explanation:
You are given 5 sub-tracks with different
kilometers. Your car can travel 4 km on
each sub-track. So, when you come on
sub-track 2nd you have to cover 6 km of
distance, so you need to have 2 unit of
petrol more to cover the distance, for
3rd sub-track, now your car can travel
6 kilometers, so no problem and so on.

    

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 105
1 ≤ K ≤ 1018
1 ≤ A[] ≤ 1018