Display maximum military time from given four integers

Question

I encountered this question in one of the interview challenges.

The question was that given four integers, display the maximum time possible in 24 hour format HH:MM. For example, if you are give A = 1, B = 9, C = 9, D = 2 then output should be 19:29. Max time can be 23:59 and min time can be 00:00. If it is not possible to construct 24 hour time then return error. For example, given A = 1, B = 9, C = 7, D = 9 an error should be returned since minimum time represented by these integers is 17:99 which is invalid.

My initial approach has been to find all the 24 integer permutations of given number and then eliminate all of them which are greater than 2400. After this, eliminate all the integers that have more than 59 in their last two digits. That is, 5 in the ten's place and 9 in the unit's place. After this filtering, return the highest integer left in our result set.

This approach is feasible here since we have to just calculate 24 permutations and even less combinations since duplicates will be removed. But I feel this to be a brute force approach. Is there any other idea which does not require us to generate all permutations?

Also as an extension to this problem, in case if we are asked to extend the time to seconds or milliseconds given total of 6 digits or 8 digits respectively, then my approach would be costly. Lets assume the max allowed run time complexity can be O(nlogn) and thus allowing us sorting. Also, how to check for the edge cases that I mentioned above?

Thanks.

EDIT: Below is the code for the answer suggested in the comments.

//Input arraylist contains the four integers
public static String maxTime(ArrayList<Integer> list){
    int first = -1;
    int second = -1;
    int third = -1;
    int fourth = -1;

    for (int a : list) {
        if (a <= 2 && a > first) {
            first = a;
        }
    }
    list.remove(Integer.valueOf(first));

    for (int a : list) {
        if (first == 2 && a <= 3 && a > second) {
            second = a;
        }
    }
    if (second == -1) {
        for (int a : list) {
            if (a > second) {
                second = a;
            }
        }
    }
    list.remove(Integer.valueOf(second));

    for (int a : list) {
        if (a <= 5 && a > third) {
            third = a;
        }
    }
    list.remove(Integer.valueOf(third));

    fourth = list.get(0);

    StringBuilder sb = new StringBuilder(5);
    sb.append(first);
    sb.append(second);
    sb.append(':');
    sb.append(third);
    sb.append(fourth);

    return sb.toString();
}

I have already gone through that question link but it doesn't have any satisfactory answers. Please have a look at it. — qrius, Jan 16 '17 at 21:49
The linked question has a good answer. I had a look at it. Just implement it. If you have a problem with it, post your code and ask a specific question on what the issue is. — trincot, Jan 16 '17 at 22:39
Implemented it. Still doesn't give desired output. Apparently, the edge case for checking validity of input that I mentioned in my question was incorrect. So even the edge case in the answer pointed to is missing. Have updated my question with the code. — qrius, Jan 17 '17 at 00:09

score 0 · Answer 1 · answered Feb 01 '17 at 23:28

My Solution :)

function getMaxTime(a,b,c,d) {

let nums = Array.from(arguments).sort();

function getMaxNum (num, arr) {    
  let index ;
   arr.map(function(el, i){     

        if( el <= num ) { index = i }                  
  });

  return index 
} 

function extractVal (index, arr) {
   if(index) { return arr.splice(index, 1) }
}


//first condition

  if ( getMaxNum(2, nums) <= 2 ){
     let value1 =  extractVal(getMaxNum(2, nums), nums);        

      if (value1 == 2){
       if (getMaxNum(3, nums) <= 3){

         let value2 = extractVal(getMaxNum(3, nums), nums)         
         let value3 = extractVal(getMaxNum(5, nums), nums)     
         let value4 = extractVal(getMaxNum(9, nums), nums)
         console.log(value1, value2, value3, value4)
       }else{
          console.log( 'Cannot build an time hour from 2' )
       }

    }else{
      let value2 =  extractVal(getMaxNum(9, nums), nums)
      let value3 =  extractVal(getMaxNum(5, nums), nums)   
      let value4 =  extractVal(getMaxNum(9, nums), nums)

      console.log(value1, value2, value3, value4)
    }

  }else{
    console.log( 'Cannot build an time hour' )
  }

}

getMaxTime(0,0,3,5)

score 0 · Answer 2 · answered Dec 26 '17 at 19:33

With my friend we have thinking about this problem few hours and IMO the best solution is iterate from i = 2359, divide i number to separate digits, sort and finally check if is equal to sorted array of input numbers. Additionally if i%100 == 0 subtract 41 from i to avoid numbers where minutes are greater than 60. Complete, tested implementation is below:

public String solution(int A, int B, int C, int D) {

    int[] inputNumbers = { A, B, C, D };
    Arrays.sort(inputNumbers);

    for (int i = 2359; i >= 0; i--) {

        if (i % 100 == 0 && i != 0) {
            i -= 41;
        }
        StringBuilder potentialTimeNumbers = new StringBuilder(i + "");

        for (int k = potentialTimeNumbers.length(); k < 4; k++) {
            potentialTimeNumbers.insert(0, "0");
        }

        int[] iNumbers = Stream.of(potentialTimeNumbers.toString().split("")).
                mapToInt(Integer::parseInt).toArray();
        Arrays.sort(iNumbers);

        if (Arrays.equals(inputNumbers, iNumbers)) {
            return potentialTimeNumbers.insert(2, ":").toString();
        }

    }
    return "NOT VALID";
}

Display maximum military time from given four integers

2 Answers2