Find maximum possible time HH:MM by permuting four given digits

Question

I recently took a coding test for a promotion at work. This was one of the tasks I really struggled with and was wondering what is the best way to do this. I used a load of if and if else, not the cleanest solution but got the job done.

The question I was asked was:

Format 4 numbers into a 24-hour time (00:00), finding the maximum (latest) time possible, taking into account that the max hours would be 23 and the max minutes would be 59. If not possible, return NOT POSSIBLE.

So for example:

6, 5, 2, 0 would be 20:56

3, 9, 5, 0 would be 09:53

7, 6, 3, 8 would be NOT POSSIBLE

The example function that had to return the time or string looked like this, A, B, C, D being a different number from the comma-separated list above:

function generate(A, B, C, D) {
    // Your code here
} 

How would people tackle this?

Answer 1

Here is a non brute force solution that I came up with. Check out the comments in the code to see how it works. If any of it is unclear I can help clarify.

function generate(A, B, C, D) {
    vals = [A, B, C, D];
    counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    for (i = 0; i < vals.length; i++) {
        for (j = vals[i]; j < counts.length; j++) counts[j]++;
    }
    // counts is now populated with the number of values less than or equal to the index it belongs to
    // so counts[2] is the total number of 0's, 1's and 2's
    if (counts[2] === 0) return 'NOT POSSIBLE';
    // if there are no 0's and 1's, then it must start with 2
    mustStartWith2 = counts[1] === 0;
    if (mustStartWith2 && counts[3] === 1) return 'NOT POSSIBLE';
    // We want a count of the number of free digits that are 5 or less (for the minute digit)
    numbersAvailableForMinute = counts[5] - (mustStartWith2 ? 2 : 1); 
    if (numbersAvailableForMinute === 0) return 'NOT POSSIBLE';
    // we now know that it is a valid time
    time = [0, 0, 0, 0];
    // we also know if it starts with 2
    startsWith2 = mustStartWith2 || (numbersAvailableForMinute >= 2 && counts[2] > counts[1]);
    // knowing the starting digit, we know the maximum value for each digit
    maxs = startsWith2 ? [2, 3, 5, 9] : [1, 9, 5, 9];
    for (i = 0; i < maxs.length; i++) {
        // find the first occurrence in counts that has the same count as the maximum
        time[i] = counts.indexOf(counts[maxs[i]]);
        // update counts after the value was removed
        for (j = time[i]; j < counts.length; j++) counts[j]--;
    }
    // create the time
    return time[0]+""+time[1]+":"+time[2]+""+time[3];
}

Answer 2

Added executable snippet and some test cases

function generate(A, B, C, D) {
  var combinations = []
  arguments = Array.from(arguments)
  for (var i = 0; i < 4; i++) {
    for (var j = 0; j < 4; j++) {
      if (i !== j) {
        var num = +(arguments[i] + '' + arguments[j])
        if (num <= 59 && combinations.indexOf(num) === -1)
          combinations.push(num)
      }
    }
  }
  combinations.sort((a, b) => a - b);
  var hours = combinations.filter(hour => hour <= 23);

  for (var i = hours.length - 1; i >= 0; i--) {
    for (var j = combinations.length - 1; j >= 0; j--) {
      if (computeMax(hours[i], combinations[j], arguments))
        return hours[i] + ':' + combinations[j]
    }
  }
  return 'not possible'
}

function computeMax(maxHour, maxMinute, args) {
  var minute = String(maxMinute)
  var hour = String(maxHour)
  for (var k = 0; k < minute.length; k++)
    if (hour.indexOf(minute[k]) > -1 && args.indexOf(+minute[k]) === args.lastIndexOf(+minute[k]))
      return false
  return true
}
console.log('generate(1,7,2,7)', generate(1,7,2,7))
console.log('generate(6,5,2,0)', generate(6,5,2,0))
console.log('generate(3,9,5,0)', generate(3,9,5,0))
console.log('generate(7,6,3,8)', generate(7,6,3,8))
console.log('generate(0,1,2,3)', generate(0,1,2,3))
console.log('generate(1,1,1,2)', generate(1,1,1,2))
console.log('generate(1,1,1,1)', generate(1,1,1,1))
console.log('generate(5,6,7,8)', generate(5,6,7,8))
console.log('generate(2,9,3,1)', generate(2,9,3,1))

Answer 3

Reasoning about this got a lot easier once I clued in to the fact that you can treat the problem as "generate a number less than 24, and a number less than 60" instead of trying to work with individual digits.

This goes through the number pairs in the set, finds the biggest valid hour that can be made from that pair of digits, then finds the biggest valid minute that can be made from the leftovers.

var generate = function(a, b, c, d) {
  var biggest = function(a, b, max) {
    // returns largest of 'ab' or 'ba' which is below max, or false.
    // I'm sure there's a more concise way to do this, but:
    var x = '' + a + b;
    var y = '' + b + a;
    if (max > x && max > y) {
      var tmp = Math.max(x,y);
      return (tmp < 10) ? "0"+tmp : tmp;
    }
    if (max > x) return x;
    if (max > y) return y;
    return false;
  }

  var output = false;

  var input = [].slice.call(arguments);
  for (var i = 0; i < arguments.length; i++) {
    for (var j = i + 1; j < arguments.length; j++) {
      // for every pair of numbers in the input:
      var hour = biggest(input[i], input[j], 24); // What's the biggest valid hour we can make of that pair?
      if (hour) {
        // do the leftovers make a valid minute?
        var tmp = input.slice(); // copy the input
        tmp.splice(j, 1);
        tmp.splice(i, 1);
        var minute = biggest(tmp[0], tmp[1], 60);
        if (hour && minute) {
          // keep this one if it's bigger than what we had before:
          var nval = hour + ':' + minute;
          if (!output || nval > output) output = nval;
        }
      }
    }
  }
  return output || 'NOT POSSIBLE';
}

/* --------------- Start correctness test --------------------- */
  var tests = ['0000', '1212', '1234', '2359', '2360','2362','2366', '1415', '1112', '1277', '9999', '0101'];
console.log('---');
for (var i = 0; i < tests.length; i++) {
  console.log(
    tests[i],
    generate.apply(this, tests[i].split(''))
  )
}



/* --------------- Start Speed Test --------------------- */

let startTime = Math.floor(Date.now());
let times = 10000; //how many generate call you want?
let timesHolder = times;

while (times--) {
  let A = randNum();
  let B = randNum();
  let C = randNum();
  let D = randNum();
  generate(A, B, C, D);
  if (times == 0) {
    let totalTime = Math.floor(Date.now()) - startTime;
    let msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
    console.log(msg);
    // alert(msg);
  }
}

function randNum() {
  return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}

/* --------------- END Speed Test --------------------- */

Answer 4

An approach using a precomputed string, containing all possible permutations.

function generate(A,B,C,D){
  var isValidTime = /^(?:[01]\d|2[0-3]):(?:[0-5]\d)$/;
  var pattern = "0123012 0132013 0213021 0231023 0312031 0321032".replace(/\d/g, i => arguments[+i]);
  var max = "";
  for(var i=pattern.length-4; i--; ){
    var time = pattern.substr(i,2) + ":" + pattern.substr(i+2,2);
    if(time > max && isValidTime.test(time)) 
      max = time;
  }
  return max || "NOT POSSIBLE";
}

[
  [6,5,0,2],
  [3,9,5,0],
  [7,6,3,8]
].forEach(arr => console.log(arr + ' -> ' + generate(...arr)));

.as-console-wrapper{top:0;max-height:100%!important}

but we can improve on that, by using the regex to find only valid times:

function generate(A,B,C,D){ 
  var pattern = "0123012 0132013 0213021 0231023 0312031 0321032".replace(/\d/g, i => arguments[+i]);
  console.log(pattern);
  var matchValidTime = /([01]\d|2[0-3])([0-5]\d)/g, m, max = "";
  while(m = matchValidTime.exec(pattern)){
    var time = m[1] + ":" + m[2];
    if(time > max) max = time;
    console.log("index: %o  time: %o  max: %o", m.index, time, max);
    matchValidTime.lastIndex = m.index+1; //to find intersecting matches
  }
  return max || "NOT POSSIBLE";
}

   [
  [1,2,3,4],
  //[6,5,0,2],
  //[3,9,5,0],
  //[7,6,3,8]
].forEach(arr => console.log(arr + ' -> ' + generate(...arr)));

.as-console-wrapper{top:0;max-height:100%!important}

Answer 5

The idea:

• Find all combinations array (24 total)
• filter out all invalid combinations (time format)
• find the time value
• output the array with the max time value

Solution:

First allCom will return all combination of the 4 number (total 24 combinations)

Then for the 24 array (combinations) call .forEach go through each array check if it is a valid time format. If it is valid time format then calculate the time value with

If the time is AB:CD then the value:

A = A * 10 hours = A * 10 * 3600s = A * 36000s

B = B * 1 hour = B * 3600s

C = C * 10s

D = D

Total value = A*36000 + B*3600 + C*10 + D

Now you got the value of the current array, compare with the saved Max, replace the max if this value is bigger.

At the end of the loop determine if a max found or it is not valid.

generate(6, 5, 2, 0);
generate(3, 9, 5, 0);
generate(7, 6, 3, 8);
generate(1, 7, 2, 7);
generate(1, 1, 1, 2);

// return all combination of 4 number (24 combination total)
function allCom(inputArray) {
  var result = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {
      return [item].concat(perm);
    }) || item);
  }, []);
  return result;
}

// core function to determine the max comb
function generate(A, B, C, D) {
  let input = [A, B, C, D];
  let allComb = allCom(input);
  let max = '';
  let maxA = [];

  allComb.forEach(function(comb, index, arr) {
    if (validCom(comb)) {
      let temp = calValue(comb);
      maxA = temp > max ? comb : maxA;
      max = temp > max ? temp : max;
    }
    if (index == allComb.length - 1) {
      if (max) {
        return console.log('For ' + JSON.stringify(input) + ' found max comb: ' + maxA[0] + maxA[1] + ':' + maxA[2] + maxA[3]);
      }
      return console.log('Sorry ' + JSON.stringify(input) + ' is not valid');
    }
  });
}

// check if this array is valid time format, ex [1,2,9,0] false, [2,2,5,5] true
function validCom(ar) {
  if (ar[0] <= 2 && ((ar[0] == 2 && ar[1] < 4) || (ar[0] != 2 && ar[1] <= 9)) && ar[2] <= 5 && ar[3] <= 9) {
    return true;
  }
  return false;
}

// calculate the total value of this comb array
function calValue(ar) {
  return +ar[0] * 36000 + +ar[1] * 3600 + +ar[2] * 10 + +ar[0];
}


$('button').on('click', function(e) {
    let inp = $('select');
    generate(inp[0].value, inp[1].value, inp[2].value, inp[3].value);
});


var s = $('<select />');
for(i=0;i<10;i++) {
    $('<option />', {value: i, text: i}).appendTo(s);
}
s.clone().appendTo('#myform');
s.clone().appendTo('#myform');
s.clone().appendTo('#myform');
s.clone().appendTo('#myform');

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<form id="myform">
</form>
<br>
<button type="button">Submit</button>

---

I also invite people to put this code to test the running speed of their algorithm. (used some code from @Diego ZoracKy to make this, thanks!). Have Fun!!!

/* --------------- Start Speed Test --------------------- */
let startTime = Math.floor(Date.now());
let times = 10000; //how many generate call you want?
let timesHolder = times;

while (times--) {
  let A = randNum();
  let B = randNum();
  let C = randNum();
  let D = randNum();
  generate(A, B, C, D);
  if (times == 0) {
    let totalTime = Math.floor(Date.now()) - startTime;
    let msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
    console.log(msg);
    alert(msg);
  }
}

function randNum() {
  return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}
/* --------------- END Speed Test --------------------- */

/* --------------- Start Speed Test --------------------- */
let startTime = Math.floor(Date.now());
let times = 10000; //how many generate call you want?
let timesHolder = times;

while (times--) {
  let A = randNum();
  let B = randNum();
  let C = randNum();
  let D = randNum();
  generate(A, B, C, D);
  if (times == 0) {
    let totalTime = Math.floor(Date.now()) - startTime;
    let msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
    console.log(msg);
    alert(msg);
  }
}

function randNum() {
  return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}
/* --------------- END Speed Test --------------------- */

// return all combination of 4 number (24 combination total)
function allCom(inputArray) {
  var result = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {
      return [item].concat(perm);
    }) || item);
  }, []);
  return result;
}

// core function to determine the max comb
function generate(A, B, C, D) {
  let input = [A, B, C, D];
  let allComb = allCom(input);
  let max = '';
  let maxA = [];

  allComb.forEach(function(comb, index, arr) {
    if (validCom(comb)) {
      let temp = calValue(comb);
      maxA = temp > max ? comb : maxA;
      max = temp > max ? temp : max;
    }
    if (index == allComb.length - 1) {
      if (max) {
        return 'For ' + JSON.stringify(input) + ' found max comb: ' + maxA[0] + maxA[1] + ':' + maxA[2] + maxA[3];
      }
      return 'Sorry ' + JSON.stringify(input) + ' is not valid';
    }
  });
}

// check if this array is valid time format, ex [1,2,9,0] false, [2,2,5,5] true
function validCom(ar) {
  if (ar[0] <= 2 && ((ar[0] == 2 && ar[1] < 4) || (ar[0] != 2 && ar[1] <= 9)) && ar[2] <= 5 && ar[3] <= 9) {
    return true;
  }
  return false;
}

// calculate the total value of this comb array
function calValue(ar) {
  return +ar[0] * 36000 + +ar[1] * 3600 + +ar[2] * 10 + +ar[0];
}

Answer 6

I'd use JavaScript's Date object to determine if a particular time was valid, by parsing the string as an ISO datetime string (like 1970-01-01T62:87) and then testing !isNaN( aDateInstance.getTime() ) and comparing the Date instance with the earlier saved largest Date instance (if applicable):

// permutator() borrowed from https://stackoverflow.com/a/20871714
function permutator( inputArr ) {
  var results = [];

  function permute( arr, memo ) {
    var cur, memo = memo || [];

    for( var i = 0; i < arr.length; i++ ) {
      cur = arr.splice( i, 1 );
      if( arr.length === 0 ) {
        results.push( memo.concat( cur ) );
      }
      permute( arr.slice(), memo.concat( cur ) );
      arr.splice( i, 0, cur[ 0 ] );
    }

    return results;
  }

  return permute( inputArr );
}

function generate( A, B, C, D ) {
  var r = null;
  permutator( [ A, B, C, D ] ).forEach( function( p ) {
    var d = new Date( '1970-01-01T' + p[ 0 ] + '' + p[ 1 ] + ':' + p[ 2 ] + '' + p[ 3 ] );
    if( !isNaN( d.getTime() ) && d > r ) {
      r = d;
    }
  } );

  var h, m;
  return r ? ( ( h = r.getHours() ) < 10 ? '0' + h : h ) + ':' + ( ( m = r.getMinutes() ) < 10 ? '0' + m : m ) : 'NOT POSSIBLE';
}

Answer 7

function pickN(arr, clause){
 const index = arr.findIndex(clause);
 if(index >= 0){
  return arr.splice(index, 1)[0];
 }
}

function getMaxTime(args, tryN1 = 2){
 let paramsArray = Array.from(args).sort((a , b) => a < b);

 let n1 = pickN(paramsArray, n => n <= tryN1);
 let n2 = pickN(paramsArray, n => n1 === 2 ? n <= 3 : n);
 let n3 = pickN(paramsArray, n => n <= 5);
 let n4 = paramsArray.pop();

 if([n1,n2,n3,n4].some(n => typeof(n) === `undefined`)){
  return tryN1 > 0 && getMaxTime(args, --tryN1);
 }

 return `${n1}${n2}:${n3}${n4}`;
}

function generate(A, B, C, D) {
 let maxTime = getMaxTime(arguments);
 if(maxTime){
  return maxTime;
 }

 return `NOT POSSIBLE`;
}


////////////////////////
// TESTING MANY TIMES //
////////////////////////
let times = 100;
while(times--){
 let paramA = randomNumbers();
 let paramB = randomNumbers();
 let paramC = randomNumbers();
 let paramD = randomNumbers();
 let result = generate(paramA, paramB, paramC, paramD);

 console.log(`${paramA},${paramB},${paramC},${paramD} = ${result}`);
}

function randomNumbers(){
 return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}

Answer 8

This is what I came up with. Hardly elegant, I might try to tidy it make it a bit more efficient. I have a feeling a brute force approach would be the cleanest and most efficient way to do it. This is a mess.

// w: highest value 2 or less
// UNLESS: 1 of b, c, or d are less than 3 while the other two are greater than 7
// x: highest value
// UNLESS: last was 2 then highest value less than 2
// y: highest value less than 5
// z: highest remaining value

function findhighestwhere(array, condition) {
  let res = null
  let val = -1
  let i = 0
  for (let x of array) {
    if (x !== null && condition(x) && x > val) {
      res = i
      val = x
    }
    i++
  }
  // console.log(`Test index: ${res} \n Test value: ${val}`)
  return res
}

function generate(a,b,c,d) {
  // console.log(`Testing: ${a}${b}${c}${d}`)
  let array = [a,b,c,d]
  let wi = findhighestwhere(array, x => x <= 2)
  // That one pain in the conditional edge-case
  if ( array[wi] == 2 ) {
    // console.log(`Encountered First Position 2 Checking for Edge Case`)
    let i = 0
    let lowcount = 0
    let highcount = 0
    for (let x of array) {
      if ( i != wi && x <= 3 ) lowcount++
      if ( i != wi && x >= 6 ) highcount++
      i++
    }
    if ( lowcount == 1 && highcount == 2 ) {
      // console.log(`Edge Case Encountered`)
      wi = findhighestwhere(array, x => x <= 1)
    }
  }
  if ( wi === null ) return false
  let w = array[wi]
  // console.log(`W: ${w}`)
  array[wi] = null  
  if ( w == 2 ) {
    var xi = findhighestwhere(array, x => x <= 3)
  } else {
    var xi = findhighestwhere(array, x => true)
  }
  if ( xi === null ) return false
  let x = array[xi]
  // console.log(`X: ${x}`)
  array[xi] = null
  let yi = findhighestwhere(array, x => x <= 5)
  if ( yi === null ) return false
  let y = array[yi]
  // console.log(`Y: ${y}`)
  array[yi] = null
  let zi = findhighestwhere(array, x => true)
  if ( zi === null ) return false
  let z = array[zi]
  // console.log(`Z: ${z}`)
  array[zi] = null

  return `${w}${x}:${y}${z}`
}


console.log(`6520: ${generate(6,5,2,0)}`) // 6520: 20:56
console.log(`3950: ${generate(3,9,5,0)}`) // 3950: 09:53
console.log(`7638: ${generate(7,6,3,8)}`) // 7638: false
console.log(`1727: ${generate(1,7,2,7)}`) // 1727: 17:27

Answer 9

UPDATED

Just try to find some way to improve the performance, the new idea is inspired by counting sort.

Simply count the number of each digit, then base on the following chain of dependencies, brute find the optimal possibilities. The answer would be one of those, highest priority first:

1. 2[max digit <= 3]:[max digit <= 5][*]
2. 1[*]:[max digit <= 5][*]
3. 0[*]:[max digit <= 5][*]

/* --------------- Start Speed Test --------------------- */
  var startTime = Math.floor(Date.now());
  var times = 10000; //how many generate call you want?
  var timesHolder = times;

  while (times--) {
    var A = randNum();
    var B = randNum();
    var C = randNum();
    var D = randNum();
    generate(A, B, C, D);
    if (times == 0) {
      var totalTime = Math.floor(Date.now()) - startTime;
      var msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
      console.log(msg);
      alert(msg);
    }
  }

  function randNum() {
    return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
  }
  /* --------------- END Speed Test --------------------- */
  
  function generate(A,B,C,D){
      var cnt = [0,0,0,0,0,0,0,0,0,0], ans = ['', ''];      
      cnt[A]++; cnt[B]++; cnt[C]++; cnt[D]++;
      
      function gen(part, max){
         for(var i=max; i>=0; i--) if(cnt[i]){
              ans[part] += i;
              cnt[i]--;
              return 1;
          }
          return 0;
      }
      function rollback(first){
          cnt[first]++;
          for(var i in ans[0]) cnt[ans[0][i]]++;
          for(var i in ans[1]) cnt[ans[1][i]]++;
          ans[0] = ans[1] = '';
      }
      /*** Main logic, based on the chain of dependencies ***/
      if(cnt[2]){
          cnt[2]--;
          if(!gen(0, 3) || !gen(1,5) || !gen(1,9)) rollback(2);
          else return '2' + ans[0] + ':' + ans[1];
      }
      if(cnt[1]){
          cnt[1]--;
          if(!gen(0, 9) || !gen(1,5) || !gen(1,9)) rollback(1);
          else return '1' + ans[0] + ':' + ans[1];
      }
      if(cnt[0]){
          cnt[0]--;
          if(!gen(0, 9) || !gen(1,5) || !gen(1,9)) rollback(0);
          else return '0' + ans[0] + ':' + ans[1];
      }
      return 'NOT POSSIBLE';
  }
  console.log(generate(1,7,2,7));
  console.log(generate(0,0,2,9));
  console.log(generate(6,5,2,0));
  console.log(generate(3,9,5,0));
  console.log(generate(7,6,3,8));
  console.log(generate(0,0,0,0));
  console.log(generate(9,9,9,9));
  console.log(generate(1,2,3,4));

Answer 10

I could do with tons of ifs and elses but i am pretty sure that's already been done. Instead i go with a different way.

• We get all permutations of the given 4 numbers. Here i use my rotationPerm algorithm. I guess it is one of the fastest ever in JS.
• Filter out the invalid times
• Chose the biggest from the remaining values
• Format as time.

function getMaxTime(...a){
  
  function perm(a){
    var r = [[a[0]]],
        t = [],
        s = [];
    if (a.length <= 1) return a;
    for (var i = 1, la = a.length; i < la; i++){
      for (var j = 0, lr = r.length; j < lr; j++){
        r[j].push(a[i]);
        t.push(r[j]);
        for(var k = 1, lrj = r[j].length; k < lrj; k++){
          for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj];
          t[t.length] = s;
          s = [];
        }
      }
      r = t;
      t = [];
    }
    return r;
  }
  
  function isValidTime(a){
    return 10*a[0]+a[1] < 24 && 10*a[2]+a[3] < 60;
  }
  
  var time = perm(a).filter(t => isValidTime(t))         // filter out the invalids
                    .map(t => t.reduce((p,c) => 10*p+c)) // convert them into 4 digit integer
                    .reduce((p,c) => p > c ? p : c, -1); // get the biggest
  return time >= 0 ? ("0" + ~~(time/100)).slice(-2) + ":" + time%100 : "No way..!";
}
console.log(getMaxTime(6, 5, 2, 0));
console.log(getMaxTime(3, 9, 5, 0));
console.log(getMaxTime(7, 6, 3, 8));

Answer 11

For places, AB:CD,

If at any point a condition cannot be fulfilled:
  return NOT POSSIBLE

If there are two numbers greater than 5:
  place the larger in B, smaller in D

for non-filled places from left to right:
  if B > 3:
    place a 1 in A
  else:
    place the largest number smaller than 3 in A

  if A is 2:
    place the largest number smaller than 4 in B
  else:
    place the largest number in B

  place the largest number smaller than 6 in C
  place the remaining number in D

Answer 12

Here's my attempt. Added inline comments with explanations.

// think of the result of the form {h1}{h2}:{ms}
function generate(a, b, c, d) {
  const digits = [a, b, c, d];

  // extract possible starting digits
  const possibleH1s = [2, 1, 0].filter(digit => digits.includes(digit));
  
  // check result, starting from the highest possible h1 digit
  // if digits doesn't contains any of [2,1,0], we're done
  for (const h1 of possibleH1s) {

    // extract the remaining digits after h1
    const withoutH1 = removeFrom(digits, h1);
    
    // determine all possible h2 digits based on the h1 digit
    const possibleH2s = h1 === 2
      ? [3,2,1,0]
      : [9,8,7,6,5,4,3,2,1,0];

    // find the highest possible h2 digit (works because array of possible digits above is in descending order)
    // if none exist, loop iteration is done
    const h2 = possibleH2s.find(d => withoutH1.includes(d));
    if (typeof h2 !== 'number') {
      continue;
    }
    
    // remove h2 so we can search for the remaining ms digits
    const [possibleMS1, possibleMS2] = removeFrom(withoutH1, h2);
    
    // build the two possible combinations for ms    
    const possibleMs = [
      Number(`${possibleMS1}${possibleMS2}`),
      Number(`${possibleMS2}${possibleMS1}`)
    ];
    
    // determine the min and max ms value
    const maxMs = Math.max(...possibleMs);
    const minMs = Math.min(...possibleMs);

    // find the largest valid ms value
    // if none exist, loop iteration is done
    const ms = maxMs < 60 ? maxMs : minMs < 60 ? minMs : undefined;
    if (typeof ms !== 'number') {
      continue;
    }

    // yay, time
    return `${h1}${h2}:${padWithZero(ms)}`;
  }
  
  return 'NOT POSSIBLE';
}

// returns a new array by removing a single element 
// that is equal to `val` from the given array
// (performs better than splice cause if doesn't do array shift)
function removeFrom(arr, val) {
  const newArr = [];
  for (let i = 0, l = arr.length, found = false; i < l; i++) {
    if (arr[i] !== val || found) {
      newArr.push(arr[i]);
    } else {
      found = true;
    }
  }
  return newArr;
}

function padWithZero(digit) {
  return digit < 10 ? `0${digit}` : `${digit}`;
}

/* --------------- Tests --------------------- */

const speedTest = (times = 10000) => {
  let counter = times;
  const start = performance.now();
  while (counter--) {
    const A = randNum();
    const B = randNum();
    const C = randNum();
    const D = randNum();
    generate(A, B, C, D);
    if (counter == 0) {
      const ms = performance.now() - start;
      console.log(`${times} times to run generate took ${ms} ms`);
    }
  }
}

const randNum = () => Math.floor(Math.random() * (9 - 0 + 1)) + 0;

const accuracyTest = () => {
  console.assert(generate(1,7,2,7) === '17:27');
  console.assert(generate(0,0,2,9) === '20:09');
  console.assert(generate(6,5,2,0) === '20:56');
  console.assert(generate(3,9,5,0) === '09:53');
  console.assert(generate(7,6,3,8) === 'NOT POSSIBLE');
  console.assert(generate(0,0,0,0) === '00:00');
  console.assert(generate(9,9,9,9) === 'NOT POSSIBLE');
  console.assert(generate(1,2,3,4) === '23:41');
  console.log('All good!');
}

speedTest();
accuracyTest();

Answer 13

With a small input and output space, using a look-up table is always an option; however, I found that in JavaScript the size of the table has a surprisingly large impact on the speed.

If we start by sorting the input to get a canonical version, so that 4,3,2,1 and 3,1,4,2 are both transformed into 1,2,3,4, there are less than 400 possibilities that lead to a valid result. But as soon as I added more than 200 entries to the look-up table, the speed dropped considerably (which is probably browser-dependent).

However, there are only five types of digits:

0,1    <- can be first digit of hours followed by any digit
2      <- can be first digit of hours followed by 0-3
3      <- can be second digit of hours after a 2 to form 23 hours
4,5    <- can be first digits of minutes
6-9    <- can only be second digit of hours or minutes

Within these types, the digits are interchangeable; the optimal permutation will be the same:

2,4,0,6  ->  20:46  (ACBD)
2,5,1,9  ->  21:59  (ACBD)

If you represent the digits by digit types "0" (0-1), "2", "3", "4" (4-5), and "6" (6-9), there are only 48 combinations that lead to a valid solution, each using one of 16 different permutations. Code with these smaller look-up tables turns out to be much faster:

function generate(A, B, C, D) {
    var swap; // sorting network
    if (A > B) { swap = A; A = B; B = swap; }
    if (C > D) { swap = C; C = D; D = swap; }
    if (A > C) { swap = A; A = C; C = swap; }
    if (B > D) { swap = B; B = D; D = swap; }
    if (B > C) { swap = B; B = C; C = swap; }

    var table = {"0000":15, "0002":15, "0003":14, "0004":14, "0006":14, "0022":15, 
                 "0023":14, "0024":13, "0026":12, "0033":11, "0034":11, "0036":11, 
                 "0044":11, "0046":11, "0066":10, "0222":15, "0223":14, "0224":13, 
                 "0226":12, "0233":11, "0234": 9, "0236": 8, "0244": 7, "0246": 6, 
                 "0266": 4, "0333": 5, "0334": 5, "0336": 5, "0344": 5, "0346": 5, 
                 "0366": 4, "0444": 5, "0446": 5, "0466": 4, "2222":15, "2223":14, 
                 "2224":13, "2226":12, "2233":11, "2234": 9, "2236": 8, "2244": 7, 
                 "2246": 6, "2333": 5, "2334": 3, "2336": 2, "2344": 1, "2346": 0};

    var type = ['0','0','2','3','4','4','6','6','6','6'];
    var key = type[A] + type[B] + type[C] + type[D];
    var permutation = table[key];
    if (permutation == undefined) return "NOT POSSIBLE";

    var digits = [[2,3,C,D], [2,3,D,C], [2,3,3,D], [2,3,D,3], 
                  [A,D,B,C], [A,D,C,B], [2,A,C,D], [2,A,D,C], 
                  [2,3,A,D], [2,3,D,A], [B,D,A,C], [B,D,C,A], 
                  [2,B,A,D], [2,B,D,A], [C,D,B,A], [D,C,B,A]];

    var time = digits[permutation];
    return "" + time[0] + time[1] + ':' + time[2] + time[3];
}

function rndDigit() { return Math.floor(Math.random() * 10); }
for (var tests = 0; tests < 11; tests++) {
    var d = [rndDigit(), rndDigit(), rndDigit(), rndDigit()];
    document.write(d + " &rarr; " + generate(d[0],d[1],d[2],d[3]) + "<BR>");
}

Answer 14

I think this method is called Brute Force. Took test samples from @Dummy's answer.

<script>
function generate(A, B, C, D) {
    var result = -1
    var v = [A, B, C, D]
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) if (j != i) {
            for (k = 0; k < 4; k++) if (k != j && k != i) {
                for (m = 0; m < 4; m++) if (m != k && m != j && m != i) {
                    if (v[i]*10 + v[j] < 24 && v[k]*10 + v[m] < 60) { //legal time
                        if (v[i]*1000 + v[j]*100 + v[k]*10 + v[m] > result) {
                            result = v[i]*1000 + v[j]*100 + v[k]*10 + v[m]
                        }
                    }
                }
            }
        }
    }
    return result >= 0? Math.floor(result/100) + ':' + result%100: 'NOT POSSIBLE'
} 

console.log('generate(1,7,2,7)', generate(1,7,2,7))
console.log('generate(6,5,2,0)', generate(6,5,2,0))
console.log('generate(3,9,5,0)', generate(3,9,5,0))
console.log('generate(7,6,3,8)', generate(7,6,3,8))
console.log('generate(0,1,2,3)', generate(0,1,2,3))
console.log('generate(1,1,1,2)', generate(1,1,1,2))
console.log('generate(1,1,1,1)', generate(1,1,1,1))
console.log('generate(5,6,7,8)', generate(5,6,7,8))
console.log('generate(2,9,3,1)', generate(2,9,3,1))
</script>

Answer 15

Well, starting from this suggestion about permutations in JavaScript, where, given an array of values get all possible unique permutations, I got this solution:

• Assuming you have all possible combinations with 4 digits,
• and assuming that a right hours value is in the range 00-23
• and assuming that a right minutes value is in the range 00-59

You can use this simple code to perform the action:

function maxTime(a, b, c, d) {
  var ps = Array.from(uniquePermutations([a, b, c, d]));
  while (maxHour = ps.pop()) {
    var timing = maxHour.join('').replace(/([0-9]{2})([0-9]{2})/, '$1:$2');

    if (/([0-1][0-9]|2[0-3])\:[0-5][0-9]/.test(timing)) {
      return timing;
    }
  }
  return false;
}

function swap(a, i, j) {
  const t = a[i];
  a[i] = a[j];
  a[j] = t;
}

function reverseSuffix(a, start) {
  if (start === 0) {
    a.reverse();
  } else {
    let left = start;
    let right = a.length - 1;

    while (left < right)
      swap(a, left++, right--);
  }
}

function nextPermutation(a) {
  // 1. find the largest index `i` such that a[i] < a[i + 1].
  // 2. find the largest `j` (> i) such that a[i] < a[j].
  // 3. swap a[i] with a[j].
  // 4. reverse the suffix of `a` starting at index (i + 1).
  //
  // For a more intuitive description of this algorithm, see:
  //   https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
  const reversedIndices = [...Array(a.length).keys()].reverse();

  // Step #1; (note: `.slice(1)` maybe not necessary in JS?)
  const i = reversedIndices.slice(1).find(i => a[i] < a[i + 1]);

  if (i === undefined) {
    a.reverse();
    return false;
  }

  // Steps #2-4
  const j = reversedIndices.find(j => a[i] < a[j]);
  swap(a, i, j);
  reverseSuffix(a, i + 1);
  return true;
}

function* uniquePermutations(a) {
  const b = a.slice().sort();

  do {
    yield b.slice();
  } while (nextPermutation(b));
}


function maxTime(a, b, c, d) {
  var ps = Array.from(uniquePermutations([a, b, c, d]));
  while (maxHour = ps.pop()) {
    var timing = maxHour.join('').replace(/([0-9]{2})([0-9]{2})/, '$1:$2');

    if (/([0-1][0-9]|2[0-3])\:[0-5][0-9]/.test(timing)) {
      return timing;

    }
  }
  return false;
}
console.log(maxTime(6, 5, 2, 0));
console.log(maxTime(3, 9, 5, 0));
console.log(maxTime(7, 6, 3, 8));

Answer 16

Hmmm..... I guess it's really simple if you break it into simpler problems: eg find all valid hours (00-23), for each of these valid hours use the remaining numbers to find valid minutes (00-59), combine and sort. In pseudo code something like the following

    valid_times = []
    function get_max(digits[]) {
                for each d1 in digits[]
            for each d2 in (digits[] except d1)
                res = is_valid_hour(d1, d2)
                if(res > 0) {
                    if(res == 2)
                        swap(d1, d2)
                    d3 = one of the rest in (digits except d1 and d2)
                    d4 = digit left in digits[]
                    res = is_valid_minute(d3, d4)
                    if(res > 0)
                        if(res == 2)
                            swap(d3, d4)
                        add (d1, d2, d3, d4) to valid_times;
                }
        sort(valid_times)
        print valid_times[0]
    }

    function is_valid_hour(a, b) {
        if (a*10+b<24)
            return 1

        if (b*10+a<24)
            return 2

        return 0;
    }

    function is_valid_minute(a, b) {
        if (a*10+b<60)
            return 1

        if (b*10+a<60)
            return 2

        return 0;
    }

Answer 17

It's not elegant or pretty, but it seems to do the trick!

const NOT_POSSIBLE = 'NOT POSSIBLE';

function generate(A, B, C, D) {
 var args = [A, B, C, D];
 var idx = -1;
 var out = NOT_POSSIBLE;
 var firstN, secondN;

 MAIN: {
  args.sort(NUMERIC_ASCENDING);
  // number has to start with 0, 1 or 2
  if (args[0] > 2) break MAIN;

  while (args[++idx] < 3) {}

  // take the higest 2, 1, or 0
  firstN = args[--idx];
  args = pop(args, idx);

  if (firstN === 2) {
   // make sure that the first number doesn't exceed 23 and
   // the second number 59
   if (args[0] > 3 || args[0] > 1 && args[1] > 5)
    break MAIN;
   // advance to the first number < 3 or the length
   idx = 0;
   while (args[++idx] < 3){}
  } else {
   // much simpler if we have a 0 or 1, take the biggest n remaining
   idx = args.length;
  }

  secondN = args[--idx];
  args = pop(args, idx);
  // if minutes number is too large, swap
  if (args[0] > 5) {
   out = '' + secondN + args[1] + ':' + firstN + args[0];
  } else {
   // if bottom number is low enough, swap for more minutes
   out = '' + firstN + secondN + (args[1] < 6 ? ':' + args[1] + args[0] : ':' + args[0] + args[1]);
  }
 }
 return out;
}

// numeric comparator for sort
function NUMERIC_ASCENDING(x, y) {
 return x > y ? 1 : y > x ? -1 : 0;
}

// specialized "array pop" I wrote out longhand that's very optimized; might be cheating =D
function pop(arr, target) {
 switch (arr.length) {
 case 3:
  switch (target) {
  case 0: return [arr[1], arr[2]];
  case 1: return [arr[0], arr[2]];
  default: return [arr[0], arr[1]];
  }
 case 4:
  switch (target) {
  case 0: return [arr[1], arr[2], arr[3]];
  case 1: return [arr[0], arr[2], arr[3]];
  case 2: return [arr[0], arr[1], arr[3]];
  default: return [arr[0], arr[1], arr[2]];
  }
 }
}

/* --------------- Start Speed Test --------------------- */
let startTime = Math.floor(Date.now());
let times = 10000;
let timesHolder = times;

while (times--) {
  let A = randNum();
  let B = randNum();
  let C = randNum();
  let D = randNum();
  generate(A, B, C, D);
  if (times == 0) {
    let totalTime = Math.floor(Date.now()) - startTime;
    let msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
    console.log(msg);
  }
}
function randNum() {
  return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}
/* --------------- END Speed Test --------------------- */

Answer 18

My approach is to have array of available numbers (stack) and another with return value (ret). At first I put in ret invalid values "-1". Then I sort stack descending and loop trough to try to assign biggest possible number to return stack.

function swap(a, b, p1, p2) {
  var temp = a[p1];
  a[p1] = b[p2];
  b[p2] = temp;
}

function t(a, b, c, d) {
  var stack = [a, b, c, d];
  var ret   = [-1, -1, -1, -1];

  stack.sort().reverse();
  var change = true;
  var i = 0;
  // this while is assigning HOURS
  while(change === true || i < 4) {
    change = false;
    
    // Assigning at first position (Hh:mm), so number must be lower or equal to 2
    if(stack[i] <= 2 && ret[0] < stack[i]) {
      swap(ret, stack, 0, i);
      change = true;
      i = 0;
    } 
    // Assigning at second position (hH:mm), so number must be <= 4 if number 
    // at first position is 2, otherwise just make sure valid number 
    // (0 to 1) is assigned at first position
    else if(((ret[0] === 2 && stack[i] <= 4) || ret[0] < 2 && ret[0] >= 0) && ret[1] < stack[i]) {
      swap(ret, stack, 1, i);
      change = true;
      i = 0;
    }
    else i++;
  }
  
  stack.sort().reverse();
  change = true;
  i = 0;
  // This while is assigning minutes
  while(change === true || i < 4) {
    change = false;
    
    if(stack[i] <= 5 && ret[2] < stack[i]) {
      swap(ret, stack, 2, i);
      change = true;
      i = 0;
    } 
    else if(stack[i] <= 9 && ret[3] < stack[i]) {
      swap(ret, stack, 3, i);
      change = true;
      i = 0;
    }
    else i++;
  }
  
  // If return stack contains -1, invalid combination was entered
  return Math.min.apply(Math, ret) > -1
    ? ret[0] + "" + ret[1] + ":" + ret[2] + "" + ret[3]
    : "NOT POSSIBLE";
}

console.log(t(6, 5, 2, 0)); // 20:56
console.log(t(3, 9, 5, 0)); // 09:53
console.log(t(2, 5, 6, 8)); // NOT POSSIBLE

Answer 19

Really late for the party, but I think there a quite straightforward solution to the problem (slower and uglier than other solutions, though). Just iterate (no hardcoding, no permutations) through all integer values from 2359 to 0 and check if they contain provided digits:

Number.prototype.pad = function(size) {
    var s = String(this);
    while (s.length < (size || 2)) {s = "0" + s;}
    return s;
}

getHHMM = (val) => `${Math.floor(val / 100).pad(2)}:${(val % 100).pad(2)}`;

isValidDate = value => !isNaN(new Date(`1970-01-01T${getHHMM(value)}`).getTime());

isFit = function(a, b, c, d, value) {
    var valStr = value.pad(4).split("").sort().join("");
    var digStr = [a, b, c, d].sort().join("");
    return valStr === digStr;
}

generate = function(a, b, c, d) {
    for (var i = 2359; i >= 0; i--) {
        if (isFit(a, b, c, d, i) && isValidDate(i))
            return getHHMM(i);
    }
    return "NOT POSSIBLE";
}

Answer 20

This solution is in Swift 3.0.

func returnValue (_ value :inout Int, tempArray : [Int] , compareValue : Int) -> Int {

    for i in tempArray {

        if value <= i && i <= compareValue {
            value = i
        }
    }

    return value
}

func removeValue(_ value : Int, tempArr : inout [Int]) -> Bool {
    let index = tempArr.index(of: value)
    tempArr.remove(at: index ?? 0)
    return index != nil ? true : false
}

public func solution(_ A : Int, _ B : Int, _ C : Int, _ D : Int) -> String {

    var tempArray = [A, B, C, D]

    let mainArray = [A, B, C, D]

    var H1 : Int = -1, H2: Int = -1, M1 : Int = -1, M2 : Int = -1;

    H1 = returnValue(&H1, tempArray: tempArray, compareValue: 2)

    if !removeValue(H1, tempArr: &tempArray) {
        return "NOT POSSIBLE"
    }

    for value in tempArray {

        if H1 < 2 {
            if H2 <= value && value <= 9 {
                H2 = value
            }
        } else {
            if H2 <= value && value <= 3 {
                H2 = value
            }
        }
    }

    if !removeValue(H2, tempArr: &tempArray) {
        return "NOT POSSIBLE"
    }

    M1 = returnValue(&M1, tempArray: tempArray, compareValue: 5)


    if M1 >= 0 {

        if !removeValue(M1, tempArr: &tempArray) {
            return "NOT POSSIBLE"
        }
    } else if mainArray.contains(0) || mainArray.contains(1) {

        H1 = -1

        H1 = returnValue(&H1, tempArray: mainArray, compareValue: 1)

        for value in mainArray {

            if H1 < 2 {
                if H2 <= value && value <= 9 {
                    H2 = value
                }
            } else {
                if H2 <= value && value <= 3 {
                    H2 = value
                }
            }
        }


        tempArray.removeAll()

        for value in mainArray {
            tempArray.append(value)
        }


        var index = tempArray.index(of: H1)
        tempArray.remove(at: index!)

        index = tempArray.index(of: H2)
        tempArray.remove(at: index!)

        M1 = -1
        M1 = returnValue(&M1, tempArray: tempArray, compareValue: 5)

        if !removeValue(M1, tempArr: &tempArray) {
            return "NOT POSSIBLE"
        }

    } else {
        return "NOT POSSIBLE"
    }

    // Now last we have M2 = temp.last

    if let lastValue = tempArray.last {
        M2 = lastValue
    }

    if M2 < 0 {
        return "NOT POSSIBLE"
    }

    return "\(H1)\(H2):\(M1)\(M2)"
}


print(solution(1,7,2,7))
print(solution(0,0,2,9))
print(solution(6,5,2,0))
print(solution(3,9,5,0))
print(solution(7,6,3,8))
print(solution(0,0,0,0))
print(solution(9,9,9,9))
print(solution(1,2,3,4))

 17:27
 20:09
 20:56
 09:53
 NOT POSSIBLE
 00:00
 NOT POSSIBLE
 23:41

Answer 21

I recently was working on the same problem (with 6 digits though) and came up with this non-brute solution:

  #include <iostream>
  #include <iomanip>

  int numbers[6] = { 0, 0, 0, 0, 0, 0 };
  int input[6] = { 1, 7, 3, 3, 4, 1 };

  void buildHistogram() {
      for (int i = 0; i < 6; ++i) {
          numbers[input[i]]++;
      }
  }

  int getMaxNotExceeding(int number) {
      for (int i = number; i >= 0; --i) {
          if (numbers[i] > 0) {
              numbers[i]--;
              return i;
          }
      }
      throw std::exception("CANNOT CREATE TIME");
  }

  int main() {
      try {
          buildHistogram();
          int hours = (getMaxNotExceeding(2) * 10);
          if (hours < 20) {
            hours += getMaxNotExceeding(9);
          } else {
            hours += getMaxNotExceeding(3);
          }
          int minutes = (getMaxNotExceeding(5) * 10) + getMaxNotExceeding(9);
          int seconds = (getMaxNotExceeding(5) * 10) + getMaxNotExceeding(9);

          if (seconds > 59 || minutes > 59 || hours > 23) {
              throw std::exception("CANNOT CREATE TIME");
          }
          std::cout.fill('0');
          std::cout << std::setw(2) << hours << ':' << std::setw(2) << minutes << ':' << std::setw(2) << seconds << std::endl;
      } catch(const std::exception& ex) {
          std::cout << ex.what() << std::endl;
      }
      return 0;
  }

Answer 22

function isValidNumbers(numbers){ 
    const limitations = {gt5:0, gt4:0, gt2:0}
    for (var key in numbers) {
        const val = numbers[key]
        //Only 0-9 are valid numbers
        if (val > 9) return false 
        //Only one number can be greater than 5
        if (val > 5 && ++ limitations.gt5 && limitations.gt5 > 1) return false
        //Only two numbers can be greater then 3
        //For example 24:44 is not valid 
        //Max possible time can be 23:59
        if (val > 3 && ++ limitations.gt4 && limitations.gt4 > 2) return false
        //Only 3 numbers can be greater then 2
        if (val > 2 && ++ limitations.gt2 && limitations.gt2 > 3) return false
    }
    return true;
}

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

function getMaxTime(a, b, c, d){
    if (!isValidNumbers(arguments)) return 'not possible'
    const sortedArr = sortArgs(...arguments)
    const has2 = sortedArr.indexOf(2);
    let hh = []
    let mm = []
    sortedArr.forEach(function(val) {
        if (val > 5) return has2 == -1 && !hh[1] ? hh[1] = val : mm[1] = val
        if (val > 3) return has2 == -1 && !hh[1] ? hh[1] = val : !mm[0] ? mm[0] = val : mm[1] = val
        if (val > 2) return !hh[1] ? hh[1] = val : !mm[0] ? mm[0] = val : mm[1] = val
        return !hh[0] ? hh[0] = val : !hh[1] ? hh[1] = val : !mm[0] ? mm[0] = val : mm[1] = val
    })  
    //return has2
    return `${hh[0]}${hh[1]}:${mm[0]}${mm[1]}`;
}
console.log(getMaxTime(1,2,3,4)) // "23:41"
console.log(getMaxTime(1,1,3,4)) // "14:31"
console.log(getMaxTime(6,4,2,4)) // "not possible"

Answer 23

public static string CreateTime()
        {
            int[] arr = { 5,5,6,6 };
            int hr_tense_max = 0;
            int hr_ones_max = 0;
            int min_tense_max = 0;
            int min_ones_max = 0;

            for (int i = 0; i < arr.Length; i++)
            {
                int value = arr[i];
                if (value <= 2 && value > hr_tense_max)
                {
                    hr_tense_max = value;
                    continue;
                }

                if (value <= 3 && value > hr_ones_max)
                {
                    hr_ones_max = value;
                    continue;
                }

                if (value <= 5 && value > min_tense_max)
                {
                    min_tense_max = value;
                    continue;
                }

                if (value <= 9 && value > min_ones_max)
                {
                    min_ones_max = value;
                    continue;
                }


            }
            if ((hr_tense_max * 10 + hr_ones_max) > 24 || (min_tense_max * 10 + min_ones_max) > 59) 
            { 
                return "Not Possible"; 
            }
            return $"{hr_tense_max}{hr_ones_max}:{min_tense_max}{min_ones_max}";
        }

Answer 24

Python:

def get_number_frequency(arr):
    from collections import Counter
    return dict(Counter(arr))

def check_val(mapped_val, val):
    if val in mapped_val:
        mapped_val[val] -= 1
        return True
    return False

def getMax_time(arr, n):
    time_value = ""
    flag = False
    mapped_val = get_number_frequency(arr)
    
    for i in range(2,-1,-1):
        if check_val(mapped_val, i):
            time_value += str(i)
            flag = True
            break
    if not flag:
        return ""
    flag = False
    
    if time_value[0] == 2:
        for i in range(3,-1,-1):
            if check_val(mapped_val, i):
                flag = True
                time_value += str(i)
            break
    else:
        for i in range(9, -1, -1):
            if check_val(mapped_val, i):
                flag = True
                time_value += str(i)
                break
    time_value += ":"
    if not flag:
        return ""
    flag = False
  
    for i in range(5,-1,-1):
        if check_val(mapped_val, i):
            flag = True
            time_value += str(i)
            break
   
    if not flag:
        return ""
    flag = False

    for i in range(9,-1,-1):
        if check_val(mapped_val, i):
            flag = True
            time_value += str(i)
            break


    return time_value

if __name__ == "__main__":   
    arr = [2,2,2,2] 
    n = len(arr)
    print(getMax_time(arr, n)) 

Answer 25

from itertools  import permutations
class Solution(object):
    def largestTimeFromDigits(self, A):
        arr = []
        for i in permutations(A,4):
            if int(str(i[0])+str(i[1])) < 24 and int(str(i[2])+ str(i[3])) < 60:
                arr.append(list(i))
        
        if arr:
            cnt = arr[0]
            for t in arr[1:]:
                if int(str(t[0])+str(t[1])) > int(str(cnt[0])+ str(cnt[1])):
                    cnt = t
                elif int(str(t[0])+str(t[1])) == int(str(cnt[0])+ str(cnt[1])):
                    if int(str(t[2])+str(t[3])) > int(str(cnt[2])+ str(cnt[3])):
                        cnt = t
            return str(cnt[0])+ str(cnt[1]) + ":" + str(cnt[2])+ str(cnt[3])  
        else:
            return ""