[Solved] Sunrise Contest Problem

Sunrise: Ninja is given an array ‘A’ of size ‘N’. Each element of the array represents the height of the ‘ith’ building (from left to right). He can choose any of the buildings. From that building, he wants to see the sunrise from the left of the first building.

He has some magical powers. By using them, he can increase the height of any building by 1. In the end, he wants to know the minimum number of times he needs to use the magic so that he can see the sunrise from any of the buildings.

For Example:

Let's say 'N' = 3, 'X' = {2, 1, 2}. 
If he uses the magic once to increase the height of the second building, then the array will be {2, 2, 2} and in this scenario, he can see the sunrise from any of the buildings. 
Hence, he needs to use the magic only '1' time.

Sunrise Contest Problem

Input Format:

The first line of input contains an integer 'T', denoting the number of Test cases.
For each Test case:
The first line contains a single integer 'N' denoting the number of cities.
The second line contains 'N' space-separated integers denoting the height of the buildings.

Output Format:

For each test case, you have to return the minimum number of times he needs to use the magic.

Note:

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10^5
0 <= A[i] <= 10^9

The sum of N over all test cases does not exceed 10^5.

Time Limit: 1 sec

Sample Input 1:

2
3
2 1 2
2
4 2

Sample Output 1:

1
2

Explanation For Sample 1:

For test case 1:
If he uses the magic once to increase the height of the second building, then the array will be {2, 2, 2} and in this scenario, he can see the sunrise from any of the buildings. 
Hence, he needs to use the magic only '1' time.

For test case 2:
If he uses the magic twice to increase the height of the second building, then the array will be {4, 4} and in this scenario, he can see the sunrise from any of the buildings. 
Hence, he needs to use the magic only '2' times.

Sample Input 2:

2
4
67 23 23 1
1
23

Sample Output 2:

154
0

Solution

Approach:

We need the height of the buildings on the left of each building to be either less than or equal, i.e – we need to make the array non decreasing in the minimum number of operations. To do so, iterate over the array if at any point ‘A[i] < A[i – 1]’, then increase the height of the ‘ith’ building to ‘A[i – 1]’. In the end, return the total number of increments.

Algorithm:

• Just iterate over the array.
• If at any point, ‘A[i] < A[i – 1]’, then we need to increment ‘A[i]’ to make the array non decreasing. The number of increments needed is ‘A[i – 1] – A[i]’. The number of increments is needed to take ‘A[i]’ to at least ‘A[i – 1]’.
• Return the number of increments.

Time Complexity

O(N). Where ‘N’ is the length of the array.

We are just traversing the array once. Hence the overall complexity is O(N).

Space Complexity

O(1).

We are just creating a variable to store the number of increments. Hence the overall complexity is O(1).

long long int sunrise(vector<int> &a) {
    int maxm =INT_MIN; long long int count =0;int max = a[0];
    for(int i=1;i<a.size();i++){
        if(max>a[i])
            count+=max-a[i];
        else
            max=a[i]; 
    }
    return count;
}

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    where 'N' is the size of the array.
*/

#include <vector>
using namespace std;

long long int sunrise(vector<int> & a) {
    
	// Here 'ans' will store the number of increments.
    long long int ans = 0;

    for (int i = 1; i < a.size(); i++) {
    
	    // If the height of current building is less than the height of previous building then increase it.
        if (a[i] < a[i - 1]) {
            ans += (a[i - 1] - a[i]);
            a[i] = a[i - 1];
        }
    }

    return ans;
}

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    where 'N' is the size of the array.
*/

public class Solution {

	public static long sunrise(int[] a) {
		
		// Here 'ans' will store the number of increments.
		long ans = 0;
	
		for (int i = 1; i < a.length; i++) {
			
			// If the height of current building is less than the height of previous building then increase it.
			if (a[i] < a[i - 1]) {
				ans += (a[i - 1] - a[i]);
				a[i] = a[i - 1];
			}
		}
	
		return ans;
	}
}

"""
    Time Complexity: O(N)
    Space Complexity: O(1)

    where 'N' is the size of the array.
"""


def sunrise(a):

    # Here 'ans' will store the number of increments.
    ans = 0

    for i in range(1, len(a)):

        # If the height of current building is less than the height of previous building then increase it.
        if a[i] < a[i - 1]:
            ans += (a[i - 1] - a[i])
            a[i] = a[i - 1]

    return ans

Happy Learning – If you require any further information, feel free to contact me.