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

by

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];
}

More Related Contents:

  1. How do I check if an array includes a value in JavaScript?
  2. Cartesian product of multiple arrays in JavaScript
  3. Finding All Combinations (Cartesian product) of JavaScript array values
  4. How does this recursion work?
  5. How to draw sky chart? [closed]
  6. Improving performance of click detection on a staggered column isometric grid
  7. How do I sort an array of objects based on the ordering of another array?
  8. Efficient way to insert a number into a sorted array of numbers?
  9. Fastest way to flatten / un-flatten nested JavaScript objects
  10. Recursively print all permutations of a string (Javascript)
  11. Where is my implementation of rot13 in JavaScript going wrong?
  12. Bresenham algorithm in Javascript
  13. Permutations without recursive function call
  14. Packing different sized circles into rectangle – d3.js
  15. Using Canvas to animate a sorting algorithm in JS
  16. Check if polygon is inside a polygon
  17. Remove duplicate objects from an array using javascript
  18. Get the item that appears the most times in an array
  19. Solving TicTacToe with minimax algorithm in Javascript
  20. Compare Strings Javascript Return %of Likely
  21. How to find horizon line efficiently in a high-altitude photo?
  22. Number.sign() in javascript
  23. 3D point rotation algorithm
  24. Creating an array consisting of the largest values of each sub-array does not work as expected
  25. Given an array, how to generate all combinations of subset size k?
  26. Two-sum Leetcode explanation, Hashmap, Javascript
  27. Diamond-square algorithm not working (rewrite code from JS to JAVA)
  28. Visualization of calendar events. Algorithm to layout events with maximum width
  29. Using an imported module inside Google App Script
  30. Algorithm of JavaScript “sort()” Function

Leave a Comment