Tiempo máximo en formato HH:MM:SS que se puede representar con seis dígitos dados

Dada una array arr[] que consta solo de seis dígitos enteros, la tarea es devolver el tiempo máximo en un formato de 24 horas que se puede representar utilizando los dígitos de la array dada.

Nota: La hora mínima en formato de 24 horas es 00:00:00 y la hora máxima es 23:59:59. Si no se puede formar una hora válida, imprima -1.

Ejemplos:

Entrada: arr[] = {0, 2, 1, 9, 3, 2}
Salida: 23:29:10
Explicación:
El tiempo máximo de formato de 24 horas que se puede formar usando los dígitos de la array es 23:29:10

Entrada: arr[] = {6, 2, 6, 7, 5, 6}
Salida: -1

Enfoque: siga los pasos a continuación para resolver el problema:

• Cree un Hashmap y almacene la frecuencia de los dígitos en la array dada.
• Iterar desde el tiempo máximo 23:59:59 hasta el tiempo mínimo 00:00:00
• Para cada vez, verifique si todos los dígitos están en Hashmap o no.
• Imprima la primera vez que se cumple la condición anterior. Si no se encuentra ningún tiempo que satisfaga la condición, imprima «-1».

A continuación se muestra la implementación del enfoque anterior:

// 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 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

# 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# 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

23:29:10

Complejidad de tiempo: O(60*60*60) 
Espacio auxiliar: O(1)