Maximum Days Without Darkness

Problem

Given an array arr[] of size N representing the size of candles which reduce by 1 unit each day. The room is illuminated using the given N candles. Find the maximum number of days the room is without darkness.

Examples:

Example 1:

Input: N = 3, arr[] = {1,1,2} 
Output: 2
Explanation: The candles' length reduce by 1 in 1 day. So, at the end of day 1: 
Sizes would be 0 0 1, So, at end of day 2: Sizes would be 0 0 0. This means the room was illuminated for 2 days.

Example 2:

Input: N = 5, arr[] = {2,3,4,2,1} 
Output: 4

Your task:

This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function maxDays() that takes array A[] and integer N as parameters and returns the desired output.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^6$

Solution

Python

def maxDays(self, arr, n):
    if n == 0:
        return 0
    max_initial_height = 0
    for height in arr:
        if height > max_initial_height:
            max_initial_height = height
    return max_initial_height

Java

long maxDays(long arr[], int n){
    if (n == 0) {
        return 0;
    }
    long maxInitialHeight = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxInitialHeight) {
            maxInitialHeight = arr[i];
        }
    }
    return maxInitialHeight;
}

C++

int maxDays(int arr[],int n){
    if (n == 0) {
        return 0;
    }
    long maxInitialHeight = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxInitialHeight) {
            maxInitialHeight = arr[i];
        }
    }
    return maxInitialHeight;          
}

C

int maxDays(int arr[], int n) {
    if (n == 0) {
        return 0;
    }
    long maxInitialHeight = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxInitialHeight) {
            maxInitialHeight = arr[i];
        }
    }
    return maxInitialHeight;          
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$