Home » C++ programs » C++ Most popular & searched programs

C++ program to print the maximum possible time using six of nine given single digits

The Objective is to form the maximum possible time (in HH:MM:SS and 12 hour format) using any six of nine given single digits (not necessarily distinct).
Submitted by Abhishek Jain, on August 05, 2017 [Last updated : February 26, 2023]

Printing the maximum possible time using six of nine given single digits

Given a set of nine single digits ((not necessarily distinct) say 0,0,1,3,4,6,7,8,9. It is possible to form many distinct times in a 12 hour time format HH:MM:SS, such as 10:36:40 or 01:39:46 by using each of the digits only once. The objective is to find the maximum possible valid time (00:00:01 to 12:00:00) that can be formed using some six of the nine digits exactly once. In this case, it is 10:49:38.

Example:

1) Set={0,1,3,4,2,1,5,8,0}
It will print-:  11:58:43

2) Set={0,9,6,9,7,8,9,6,3}
It will print-: Impossible Operation!

In this Program, I'm using the concept of COUNT ARRAY. To understand about count array please go through the link: C++ program to find the frequency of a character in a string using Count Array

C++ code to print the maximum possible time using six of nine given single digits

#include <iostream>
using namespace std;

//Applying the concept of count Array
int count[10] = { 0 };

//This function will return the maximum value from
//count array upto the given index n
int MAX(int n)
{
    int i;
    for (i = n; i >= 0; i--) {
        if (count[i] != 0) {
            count[i]--;
            return i;
        }
    }
    return -1;
}

//main program
int main()
{
    int x, i, y = 0;
    char A[8];
    for (i = 0; i < 9; i++) {
        cin >> x;
        if (x >= 0 && x <= 9)
            count[x]++;
        else {
            cout << "Wrong Input!Please Enter Again" << endl;
            i--;
        }
    }

    if (count[2] >= 1 && count[1] >= 1 && count[0] >= 4)
        cout << "12:00:00" << endl;
    else {
        //All works for char array A[]
        for (i = 0; i < 8 && y != 1; i++) {
            if (i % 3 == 2) {
                A[i] = ':';
            }
            else if (i % 3 == 0 && i > 0) {
                //Adding '0' to convert the value
                //into its character format
                A[i] = MAX(5) + '0';
            }
            else if (i % 3 == 1) {
                if (A[0] == 0 + '0' || i > 1) {
                    A[i] = MAX(9) + '0';
                }
                else {
                    A[i] = MAX(1) + '0';
                }
            }
            else if (i == 0)
                A[i] = MAX(1) + '0';
            if (A[i] == -1 + '0')
                y = 1;
        }
        if (y == 1) {
            cout << "Impossible Operation!" << endl;
        }
        else {
            for (i = 0; i < 8; i++)
                if (i % 3 == 2)
                    cout << A[i];
                else
                    cout << A[i] - '0';
            cout << endl;
        }
    }
    return 0;
}

Output

First run:
0 1 3 4 2 1 5 8 0 
11:58:43

Second run:
0 9 6 9 7 8 9 6 3 
Impossible Operation! 

---