Generate maximum HH:MM from a list of 4 integers

Question

Note: Another question is the duplicate of this one. If I posted this question 6 months earlier than that one, then how can mine be a duplicate?

I have 4 non-negative integers a,b,c,d. All of them are less than or equal to 9. I have to return the maximum time that can be shown on the clock in 24-hour format.

For example: a=9, b=4, c=3, d=1, would yield 19:43

I have so far only been able to come up with brute-force approach which kind of tests all 24-possible combinations. Although this isn't too bad, I was wondering if there are more elegant approaches. All ideas better than brute force are welcome.

Note: It is not a homework question. I got this from an interview prep site but has no solutions there.

Answer 1

Generating all 24 permutations would work, but you don't have to do that. Your validation for the brute force method would require you to validate each digit, and you may as well build up the permutation as you validate each digit. Start with big numbers.

1. sort numbers in high -> low

2. iterate over each digit [i] and search through the list until you find the highest number that fits the requirements.

   [0] must be <=2

   [1] must be <=3 if [0]==2

   [2] must be <=5

   [3] can be anything

3. Remove that number from the list, and place it in position [i]

4. repeat for each digit

Each of those conditions could be expressed as lambda function in a list, making it easy to separate the search loop from the conditions.

Answer 2

The key is to sort the data and then apply these simple rules:

• At least one element has to be <= 2
• A second element has to be <= 5
• If there are only two elements meeting the first two rules then one of them must be < 2
• If the element selected for the first value is 2 then the element selected for the second value must be less than 4

The rules are easy to implement by using three counters:

• less_than_3 - this must always be at least 1
• less_than_6 - this must always be at least 2
• less_than_4 - if a == 2 then less_than_4 must be at least 2

Here's a solution in JavaScript that could be further refactored.

function find_the_time(data) {
  var arr = data.slice(), ans = {};
  var count_less_than_three = 0, count_less_than_four = 0, count_less_than_six = 0;

  console.log(arr);

  arr.sort(function(a,b) { return a - b; });

  if ((arr[0] > 2) || (arr[1] > 5)) {
    // Rule 1 - Hh:mm must be <= 2
    // Rule 2 - hh:Mm must be <= 5
    console.log('No solution');
    return -1;
  }

  for (var el of arr) {
    if (el < 3) {
      // count_less_than_three will be at least 1
      count_less_than_three++;
    }
    if (el < 4) {
      // count_less_than_four will be at least 1
      count_less_than_four++;
    }
    if (el < 6) {
      // count_less_than_six will be at least 2
      count_less_than_six++;
    }
  }

  if (count_less_than_three === count_less_than_six) {

    if (count_less_than_three == 2) {
      // Two elements have values less than 3
      // so the time must be earlier than 20:00
      // Rule 3 - Hh:mm must be <= 1
      if (arr[0] > 1) {
        console.log('No solution');
        return -1;
      } else {
        ans.c = arr.splice((count_less_than_three - 1), 1);
        ans.a = arr.splice((count_less_than_three - 2), 1);
        ans.b = arr.splice(1, 1);
        ans.d = arr.splice(0, 1);
      }
    } else {

      ans.a = arr.splice((count_less_than_three - 1), 1);
      ans.b = arr.splice((count_less_than_three - 2), 1);

      if (arr[1] < 6) {
        ans.c = arr.splice(1, 1);
        ans.d = arr.splice(0, 1);
      } else {
        ans.d = arr.splice(1, 1);
        ans.c = arr.splice(0, 1);
      }

    }

  } else {

    ans.a = arr.splice((count_less_than_three - 1), 1);

    if (ans.a < 2) {
      // b can have any value so select the largest available
      ans.b = arr.splice(2, 1);
    } else {
      // a == 2 so count_less_than_four comes into play
      // Rule 4 - hH:mm must be <= 3
      // Array size has been reduced so decrement count_less_than_four
      count_less_than_four--;
      ans.b = arr.splice((count_less_than_four - 1), 1);
    }

    if (arr[1] < 6) {
      ans.c = arr.splice(1, 1);
      ans.d = arr.splice(0, 1);
    } else {
      ans.d = arr.splice(1, 1);
      ans.c = arr.splice(0, 1);
    }

  }
  console.log('Answer: ' + ans.a + '' + ans.b + ':' + ans.c + '' + ans.d);
  return ans.a + '' + ans.b + ':' + ans.c + '' + ans.d;
}

var test_data = [
  [ 2, 1, 2, 1 ],
  [ 9, 5, 7, 1 ],
  [ 2, 2, 7, 6 ],
  [ 2, 6, 6, 1 ],
  [ 0, 5, 9, 8 ],
  [ 0, 6, 9, 8 ],
  [ 2, 5, 9, 3 ]
];

test_data.forEach(find_the_time);

Answer 3

You can change time to minutes. Then you can compare it.

//23:59 ==> 23*60+59 ==1439 min //(10a+b)*60+(10c+d)<=1439

This is my code.

String function(int[] numbers){      
        int num[] = numbers;
        int temp = 0;
        int cnt=0;
        int numA=0;
        int numB=0;
        int numC=0;
        int numD=0;

        for(int a=0;a<num.length; a++){
            for(int b=0;b<num.length; b++){
                for(int c=0;c<num.length; c++){
                    for(int d=0;d<num.length; d++){
                        if(a!=b && a!=c && a!=d
                                && b!=c && b!=d
                                        && c!=d){
                            if((10*num[c]+num[d])<60) {
                                int cal = (10 * num[a] + num[b]) * 60 + (10 * num[c] + num[d]);
                                Log.d("Joon1979", "Input Numbers [ " + num[a] + ", " + num[b] + ", " + num[c] + ", " + num[d] + " ]");
                                if (cal <= 1439) {
                                    cnt++;
                                    if (temp < cal) {
                                        temp = cal;
                                        numA = num[a];
                                        numB = num[b];
                                        numC = num[c];
                                        numD = num[d];
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        if(cnt==0){
            return "impossible";
        }else {
            return numA+""+numB+" : "+numC+""+numD;
        }
    }