Find the light bulb with maximum glowing time
Given a string S consisting of N unique lowercase alphabets and an array arr[] of length N where character S[i] represents the bulb and arr[i] represents the time up to which the ith bulb glows, starting from the time arr[i β 1]. The task is to find the bulb with maximum glowing time. If there exists more than one bulb with the same maximum glowing time, print the lexicographically greater one.
Examples:
Input: S = βabcdβ, arr[] = {9, 29, 49, 50}
Output: c
Explanation:
βcβ at index 0 has a duration = 9.
βbβ at index 1 has a duration = arr[1] β arr[0] = 29 β 9 = 20
βcβ at index 2 has a duration = arr[2] β arr[1]= 49 β 29 = 20
βdβ at index 3 has a duration = arr[3] β arr[2]= 50 β 49 = 1
Two bulbs, βbβ and βcβ, have the maximum glowing time. Among those two, βcβ is lexicographically larger.Input: S = βspudaβ, arr[] = {12, 23, 36, 46, 62}
Output: a
Explanation:
βsβ at index 0 has a duration = 12.
βpβ at index 1 has a duration = arr[1] β arr[0] = 23-12 = 11.
βuβ at index 2 has a duration = arr[2] β arr[1] = 36-23 = 13.
βdβ at index 3 has a duration = arr[3] β arr[2] = 46-36 = 10.
βaβ at index 4 has a duration = arr[4] β arr[3] = 62-46 = 16.
Therefore, βaβ has maximum glowing time.
Approach: The idea is to traverse the array and for each array element, calculate arr[i] β arr[i β 1]. Then, print the lexicographically larger bulb having maximum glowing time. Follow the steps below to solve the problem:
- Initialize two variables, say maxDur and maxPos, to store the glowing time and the index of the bulb with maximum glowing time, respectively.
- Traverse the given array and perform the following steps:
- If the current time (arr[i] β arr[i β 1]) is smaller than maxCurr, update maxCurr as maxCurr = arr[i] β arr[i β 1].
- Otherwise, if it is equal to maxCurr, maxPos does not contain any valid index and S[maxPos] is lexicographically smaller than S[i], update maxPos as maxPos = i.
- After completing the above steps, print S[maxPos] as the required output.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the bulb // having maximum glow char longestLastingBulb( vector< int > onTime, string s) { char ans; int n = onTime.size(); // Initialize variables int maxDur = INT_MIN; int maxPos = INT_MIN; int currentDiff = 0; // Traverse the array consisting // of glowing time of the bulbs for ( int i = 0; i < n; i++) { // For 1st bulb if (i == 0) { currentDiff = onTime[i]; maxDur = currentDiff; maxPos = i; } else { // Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1]; // Update the maximum glow if (maxDur < currentDiff) { maxDur = currentDiff; maxPos = i; } // Find lexicographically // largest bulb else { if (maxDur == currentDiff) { char one = s[i]; char two = s[maxPos]; if (one > two) { maxDur = currentDiff; maxPos = i; } } } } } // Bulb with maximum time ans = s[maxPos]; // Return the resultant bulb return ans; } // Driver Code int main() { string S = "spuda" ; vector< int > arr = { 12, 23, 36, 46, 62 }; // Function call cout << longestLastingBulb(arr, S); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the bulb // having maximum glow static char longestLastingBulb( int []onTime, char []s) { char ans; int n = onTime.length; // Initialize variables int maxDur = Integer.MIN_VALUE; int maxPos = Integer.MIN_VALUE; int currentDiff = 0 ; // Traverse the array consisting // of glowing time of the bulbs for ( int i = 0 ; i < n; i++) { // For 1st bulb if (i == 0 ) { currentDiff = onTime[i]; maxDur = currentDiff; maxPos = i; } else { // Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1 ]; // Update the maximum glow if (maxDur < currentDiff) { maxDur = currentDiff; maxPos = i; } // Find lexicographically // largest bulb else { if (maxDur == currentDiff) { char one = s[i]; char two = s[maxPos]; if (one > two) { maxDur = currentDiff; maxPos = i; } } } } } // Bulb with maximum time ans = s[maxPos]; // Return the resultant bulb return ans; } // Driver Code public static void main(String[] args) { String S = "spuda" ; int []arr = { 12 , 23 , 36 , 46 , 62 }; // Function call System.out.print(longestLastingBulb(arr, S.toCharArray())); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach import sys INT_MIN = (sys.maxsize - 1 ) # Function to find the bulb # having maximum glow def longestLastingBulb(onTime, s): n = len (onTime) # Initialize variables maxDur = INT_MIN maxPos = INT_MIN currentDiff = 0 # Traverse the array consisting # of glowing time of the bulbs for i in range (n): # For 1st bulb if (i = = 0 ): currentDiff = onTime[i] maxDur = currentDiff maxPos = i else : # Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1 ] # Update the maximum glow if (maxDur < currentDiff): maxDur = currentDiff maxPos = i # Find lexicographically # largest bulb else : if (maxDur = = currentDiff): one = s[i] two = s[maxPos] if (one > two): maxDur = currentDiff maxPos = i # Bulb with maximum time ans = s[maxPos] # Return the resultant bulb return ans # Driver Code if __name__ = = "__main__" : S = "spuda" arr = [ 12 , 23 , 36 , 46 , 62 ] # Function call print (longestLastingBulb(arr, S)) # This code is contributed by AnkThon |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the bulb // having maximum glow static char longestLastingBulb( List< int > onTime, string s) { char ans; int n = onTime.Count; // Initialize variables int maxDur = Int32.MinValue; int maxPos = Int32.MinValue; int currentDiff = 0; // Traverse the array consisting // of glowing time of the bulbs for ( int i = 0; i < n; i++) { // For 1st bulb if (i == 0) { currentDiff = onTime[i]; maxDur = currentDiff; maxPos = i; } else { // Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1]; // Update the maximum glow if (maxDur < currentDiff) { maxDur = currentDiff; maxPos = i; } // Find lexicographically // largest bulb else { if (maxDur == currentDiff) { char one = s[i]; char two = s[maxPos]; if (one > two) { maxDur = currentDiff; maxPos = i; } } } } } // Bulb with maximum time ans = s[maxPos]; // Return the resultant bulb return ans; } static void Main() { string S = "spuda" ; List< int > arr = new List< int >( new int [] {12, 23, 36, 46, 62}); // Function call Console.Write(longestLastingBulb(arr, S)); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program for the above approach // Function to find the bulb // having maximum glow function longestLastingBulb(onTime, s) { let ans; let n = onTime.length; // Initialize variables let maxDur = Number.MIN_VALUE; let maxPos = Number.MIN_VALUE; let currentDiff = 0; // Traverse the array consisting // of glowing time of the bulbs for (let i = 0; i < n; i++) { // For 1st bulb if (i == 0) { currentDiff = onTime[i]; maxDur = currentDiff; maxPos = i; } else { // Calculate the glowing time currentDiff = onTime[i] - onTime[i - 1]; // Update the maximum glow if (maxDur < currentDiff) { maxDur = currentDiff; maxPos = i; } // Find lexicographically // largest bulb else { if (maxDur == currentDiff) { let one = s[i]; let two = s[maxPos]; if (one > two) { maxDur = currentDiff; maxPos = i; } } } } } // Bulb with maximum time ans = s[maxPos]; // Return the resultant bulb return ans; } // Driver code let S = "spuda" ; let arr = [ 12, 23, 36, 46, 62 ]; // Function call document.write(longestLastingBulb(arr, S)); // This code is contributed by divyesh072019 </script> |
a
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach :
The given code identifies the bulb with the longest duration of lighting in a string S made up of distinct lowercase alphabets and an array arr of length N, where arr[i] denotes the duration of glowing for the ith bulb, counting backward from arr[i-1]. The method used by the code entails repeatedly iterating through the array arr to determine each bulbβs lighting time by deducting the glowing time of the preceding bulb. The code maintains track of the bulb connected to the longest duration yet discovered. The code changes the related bulb and the maximum duration if the current bulbβs duration exceeds the maximum duration. The function adjusts the maximum duration if the current bulbβs duration is equal to that value.
Approach :
- Create a dictionary to store the bulbs and their corresponding durations.
- Traverse the array arr[] from left to right.
- For each element, add the corresponding bulb and duration to the dictionary.
- After completing the traversal, iterate through the dictionary to find the bulb with the maximum duration.
- In case of a tie, compare the keys (bulb names) to determine the lexicographically greater bulb.
Below is the implementation of the above approach:
C++
// c++ code implementation for above approache #include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; char longestLastingBulb( const vector< int >& arr, const string& S) { int max_duration = 0; char max_bulb = S[0]; map< int , char > durations; for ( int i = 0; i < S.size(); i++) { int duration = arr[i] - (i > 0 ? arr[i-1] : 0); if (duration > max_duration) { max_duration = duration; max_bulb = S[i]; durations.clear(); durations[max_duration] = max_bulb; } else if (duration == max_duration) { durations[max_duration] = max(S[i], max_bulb); } } return durations[max_duration]; } int main() { string S = "spuda" ; vector< int > arr = { 12, 23, 36, 46, 62 }; // Function call char result = longestLastingBulb(arr, S); // Output the result cout << result << endl; return 0; } |
Java
import java.util.HashMap; import java.util.Map; public class Main { // Method to find the bulb that lasts the longest public static char longestLastingBulb( int [] arr, String S) { int maxDuration = 0 ; char maxBulb = S.charAt( 0 ); Map<Integer, Character> durations = new HashMap<>(); for ( int i = 0 ; i < S.length(); i++) { int duration = arr[i] - (i > 0 ? arr[i - 1 ] : 0 ); if (duration > maxDuration) { maxDuration = duration; maxBulb = S.charAt(i); durations.clear(); durations.put(maxDuration, maxBulb); } else if (duration == maxDuration) { durations.put(maxDuration, ( char ) Math.max(S.charAt(i), maxBulb)); } } return durations.get(maxDuration); } public static void main(String[] args) { String S = "spuda" ; int [] arr = { 12 , 23 , 36 , 46 , 62 }; // Function call to find the bulb that lasts the longest char result = longestLastingBulb(arr, S); // Output the result System.out.println(result); } } |
Python3
def longest_lasting_bulb(arr, S): max_duration = 0 max_bulb = S[ 0 ] durations = {} for i in range ( len (S)): # Calculate the duration for the current bulb duration = arr[i] - (arr[i - 1 ] if i > 0 else 0 ) # Update the maximum duration and corresponding bulb if duration > max_duration: max_duration = duration max_bulb = S[i] durations.clear() durations[max_duration] = max_bulb elif duration = = max_duration: durations[max_duration] = max (S[i], max_bulb) return durations[max_duration] # Example usage S = "spuda" arr = [ 12 , 23 , 36 , 46 , 62 ] # Function call result = longest_lasting_bulb(arr, S) # Output the result print (result) |
C#
// C# code implementation for above approache using System; using System.Collections.Generic; class GFG { static char LongestLastingBulb(List< int > arr, string S) { int maxDuration = 0; char maxBulb = S[0]; Dictionary< int , char > durations = new Dictionary< int , char >(); for ( int i = 0; i < S.Length; i++) { int duration = arr[i] - (i > 0 ? arr[i - 1] : 0); if (duration > maxDuration) { maxDuration = duration; maxBulb = S[i]; durations.Clear(); durations[maxDuration] = maxBulb; } else if (duration == maxDuration) { durations[maxDuration] = ( char )Math.Max(S[i], maxBulb); } } return durations[maxDuration]; } static void Main() { string S = "spuda" ; List< int > arr = new List< int >{ 12, 23, 36, 46, 62 }; // Function call char result = LongestLastingBulb(arr, S); // Output the result Console.WriteLine(result); } } |
Javascript
function longestLastingBulb(arr, S) { // Initialize the maximum duration let maxDuration = 0; // Initialize the maximum duration bulb let maxBulb = S.charAt(0); // Map to store durations for bulbs const durations = new Map(); for (let i = 0; i < S.length; i++) { // Calculate duration for the current bulb const duration = arr[i] - (i > 0 ? arr[i - 1] : 0); if (duration > maxDuration) { // If a new maximum duration is found maxDuration = duration; maxBulb = S.charAt(i); // Clear the map to hold the new maximum durations.clear(); durations.set(maxDuration, maxBulb); } else if (duration === maxDuration) { // If duration equals the maximum, add or update it in the map durations.set(maxDuration, String.fromCharCode(Math.max(S.charCodeAt(i), maxBulb.charCodeAt(0)))); } } // Return the bulb with the maximum duration return durations.get(maxDuration); } const S = "spuda" ; const arr = [12, 23, 36, 46, 62]; // Call the function to find the longest lasting bulb const result = longestLastingBulb(arr, S); console.log(result); |
a
Time complexity : O(NlogN)
Auxilitary Space Complexity : O(N).