Maximum time in HH:MM:SS format that can be represented by given six digits

0 0 7 minutes read

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:10

Input: 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 elements
string 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 Code
int main()
{
    vector<int> v = { 0, 2, 1, 9, 3, 2 };
    cout << largestTimeFromDigits(v);
}

Java

// Java Program of the
// above approach
import java.util.*;
class GFG{
 
// Function to return the maximum
// possible time in 24-Hours format
// that can be represented by array elements
static 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 Code
public 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 elements
def 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 Code
if __name__ == '__main__':
   
    v =  [0, 2, 1, 9, 3, 2]
    print(largestTimeFromDigits(v))
     
# This code is contributed by ipg2016107

C#

// C# Program of the
// above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to return the maximum
// possible time in 24-Hours format
// that can be represented by array elements
static 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 Code
public 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 zambiatek!