Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 216
Malhire85 Avatar asked Jun 20 '17 23:06

Malhire85


People also ask

How many times can you form 4 digits?

There is 3 possible ways to fill the first place of four digit number. ∴ 60 four-digit numbers can be formed from the digits 2, 3, 5, 6, 7 and 9. Stay updated with the Mathematics questions & answers with Testbook. Know more about Permutations and Combinations and ace the concept of Circular Permutation.

How many 4 digit numbers can you make 1234?

using the digits 1234 without repetition four digit numbers can be formed there are 24 of such 4 digit numbers what is the average of this 24 number​


1 Answers

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]; } 
like image 73
Cameron Aavik Avatar answered Oct 14 '22 12:10

Cameron Aavik