Given an array arr[] consisting of six integer digits only, the task is to return the maximum time in a 24-hour format that can be represented using the digits from the given array.
Note: The minimum time in 24-hour format is 00:00:00, and the maximum is 23:59:59. If a valid time cannot be formed, then print -1.
Examples:
Input: arr[] = {0, 2, 1, 9, 3, 2}
Output: 23:29:10
Explanation:
Maximum 24-Hour Format Time that can be formed using the digits of the array is 23:29:10Input: arr[] = {6, 2, 6, 7, 5, 6}
Output: -1
Approach: Follow the steps below to solve the problem:
- Create a Hashmap and store the frequency of digits in the given array.
- Iterate from maximum time 23:59:59 to the minimum time 00:00:00
- For every time, check if all the digits are in the Hashmap or not.
- Print the first time for which the above condition is found to be holding true. If no time is found to be satisfying the condition, print “-1”.
Below is the implementation of the above approach:
C++
// C++ Program of the// above approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum// possible time in 24-Hours format// that can be represented by array elementsstring largestTimeFromDigits(vector<int>& A){ // Stores the frequency // of the array elements map<int, int> mp1, mp2; for (auto x : A) { mp1[x]++; } mp2 = mp1; // Maximum possible time int hr = 23, m = 59, s = 59; // Iterate to minimum possible time while (hr >= 0) { int h0 = hr / 10, h1 = hr % 10; int m0 = m / 10, m1 = m % 10; int s0 = s / 10, s1 = s % 10; int p = 0; vector<int> arr{ h0, h1, m0, m1, s0, s1 }; // Conditions to reduce the // the time iteratively for (auto& it : arr) { if (mp1[it] > 0) { mp1[it]--; } else { p = 1; } } // If all required digits // are present in the Map if (p == 0) { string s = ""; s = to_string(h0) + to_string(h1); s += ':' + to_string(m0) + to_string(m1); s += ':' + to_string(s0) + to_string(s1); return s; } // Retrieve Original Count mp1 = mp2; // If seconds is reduced to 0 if (s == 0) { s = 59; m--; } // If minutes is reduced to 0 else if (m < 0) { m = 59; hr--; } if (s > 0) { s--; } } return "-1";}// Driver Codeint main(){ vector<int> v = { 0, 2, 1, 9, 3, 2 }; cout << largestTimeFromDigits(v);} |
Java
// Java Program of the// above approachimport java.util.*;class GFG{// Function to return the maximum// possible time in 24-Hours format// that can be represented by array elementsstatic String largestTimeFromDigits(int []A){ // Stores the frequency // of the array elements HashMap<Integer, Integer> mp1 = new HashMap<Integer, Integer>(); HashMap<Integer, Integer> mp2 = new HashMap<Integer, Integer>(); for (int x : A) { if(mp1.containsKey(x)) mp1.put(x, mp1.get(x) + 1); else mp1.put(x, 1); } mp2 = (HashMap<Integer, Integer>) mp1.clone(); // Maximum possible time int hr = 23, m = 59, s = 59; // Iterate to minimum // possible time while (hr >= 0) { int h0 = hr / 10, h1 = hr % 10; int m0 = m / 10, m1 = m % 10; int s0 = s / 10, s1 = s % 10; int p = 0; int []arr = {h0, h1, m0, m1, s0, s1}; // Conditions to reduce the // the time iteratively for (int it : arr) { if (mp1.containsKey(it) && mp1.get(it) > 0) { mp1.put(it, mp1.get(it) - 1); } else { p = 1; } } // If all required digits // are present in the Map if (p == 0) { String st = ""; st = String.valueOf(h0) + String.valueOf(h1); st += ':' + String.valueOf(m0) + String.valueOf(m1); st += ':' + String.valueOf(s0) + String.valueOf(s1); return st; } // Retrieve Original Count mp1 = (HashMap<Integer, Integer>) mp2.clone(); // If seconds is reduced to 0 if (s == 0) { s = 59; m--; } // If minutes is reduced to 0 else if (m < 0) { m = 59; hr--; } if (s > 0) { s--; } } return "-1";}// Driver Codepublic static void main(String[] args){ int []v = {0, 2, 1, 9, 3, 2}; System.out.print(largestTimeFromDigits(v));}}// This code contributed by Princi Singh |
Python3
# Python 3 Program of the# above approach# Function to return the # maximum possible time in # 24-Hours format that can # be represented by array elementsdef largestTimeFromDigits(A): # Stores the frequency # of the array elements mp1 = {} mp2 = {} for x in A: mp1[x] = mp1.get(x, 0) + 1 mp2 = mp1.copy() # Maximum possible time hr = 23 m = 59 s = 59 # Iterate to minimum # possible time while(hr >= 0): h0 = hr//10 h1 = hr % 10 m0 = m//10 m1 = m%10 s0 = s//10 s1 = s%10 p = 0 arr = [h0, h1, m0, m1, s0, s1] # Conditions to reduce the # the time iteratively for it in arr: if (it in mp1 and mp1.get(it) > 0): mp1[it] = mp1.get(it) - 1 else: p = 1 # If all required digits # are present in the Map if (p == 0): s = "" s = (str(h0) + str(h1)) s += (':' + str(m0) + str(m1)) s += (':' + str(s0) + str(s1)) return s # Retrieve Original Count mp1 = mp2.copy() # If seconds is # reduced to 0 if (s == 0): s = 59 m -= 1 # If minutes is # reduced to 0 elif (m < 0): m = 59 hr -= 1 if (s > 0): s -= 1 return "-1"# Driver Codeif __name__ == '__main__': v = [0, 2, 1, 9, 3, 2] print(largestTimeFromDigits(v)) # This code is contributed by ipg2016107 |
C#
// C# Program of the// above approachusing System;using System.Collections.Generic;class GFG{// Function to return the maximum// possible time in 24-Hours format// that can be represented by array elementsstatic String largestTimeFromDigits(int []A){ // Stores the frequency // of the array elements Dictionary<int, int> mp1 = new Dictionary<int, int>(); Dictionary<int, int> mp2 = new Dictionary<int, int>(); foreach (int x in A) { if(mp1.ContainsKey(x)) mp1[x] = mp1[x] + 1; else mp1.Add(x, 1); } mp2 = new Dictionary<int, int>(mp1); // Maximum possible time int hr = 23, m = 59, s = 59; // Iterate to minimum // possible time while (hr >= 0) { int h0 = hr / 10, h1 = hr % 10; int m0 = m / 10, m1 = m % 10; int s0 = s / 10, s1 = s % 10; int p = 0; int []arr = {h0, h1, m0, m1, s0, s1}; // Conditions to reduce the // the time iteratively foreach (int it in arr) { if (mp1.ContainsKey(it) && mp1[it] > 0) { mp1[it]= mp1[it] - 1; } else { p = 1; } } // If all required digits // are present in the Map if (p == 0) { String st = ""; st = String.Join("", h0) + String.Join("", h1); st += ':' + String.Join("", m0) + String.Join("", m1); st += ':' + String.Join("", s0) + String.Join("", s1); return st; } // Retrieve Original Count mp1 = new Dictionary<int, int>(mp2); // If seconds is reduced to 0 if (s == 0) { s = 59; m--; } // If minutes is reduced to 0 else if (m < 0) { m = 59; hr--; } if (s > 0) { s--; } } return "-1";}// Driver Codepublic static void Main(String[] args){ int []v = {0, 2, 1, 9, 3, 2}; Console.Write(largestTimeFromDigits(v));}}// This code is contributed by shikhasingrajput |
Javascript
<script>class GFG{ // Function to return the maximum // possible time in 24-Hours format // that can be represented by array elements static largestTimeFromDigits(A) { // Stores the frequency // of the array elements var mp1 = new Map(); var mp2 = new Map(); for ( const x of A) { if (mp1.has(x)) { mp1.set(x,mp1.get(x) + 1); } else { mp1.set(x,1); }} mp2 = new Map(mp1); // Maximum possible time var hr = 23; var m = 59; var s = 59; // Iterate to minimum // possible time while (hr >= 0) { var h0 = parseInt(hr / 10); var h1 = hr % 10; var m0 = parseInt(m / 10); var m1 = m % 10; var s0 = parseInt(s / 10); var s1 = s % 10; var p = 0; var arr = [h0, h1, m0, m1, s0, s1]; // Conditions to reduce the // the time iteratively for ( const it of arr) { if (mp1.has(it) && mp1.get(it) > 0) { mp1.set(it,mp1.get(it) - 1); } else { p = 1; }} // If all required digits // are present in the Map if (p == 0) { var st = ""; st = new String(h0).toString() + new String(h1).toString(); st += ':' + new String(m0).toString() + new String(m1).toString(); st += ':' + new String(s0).toString() + new String(s1).toString(); return st; } // Retrieve Original Count mp1 = new Map(mp2); // If seconds is reduced to 0 if (s == 0) { s = 59; m--; } else if (m < 0) { m = 59; hr--; } if (s > 0) { s--; } } return "-1"; } // Driver Code static main(args) { var v = [0, 2, 1, 9, 3, 2]; document.write(GFG.largestTimeFromDigits(v)); }}GFG.main([]);</script> |
Output:
23:29:10
Time Complexity: O(60*60*60)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
