Find the earliest valid digital 24 hr format time , that can be possible with given 6 digits

Question

Recently, I took an example on the task of finding the earliest valid digital 24 hr format time that can be possible with given 6 digits, and if not possible to return empty.

example , 1 8 3 2 6 4

12:36:48

I have written the code, but it fails with too much time taken to run the tests. Yes, I agree my code filled with complete if else statements, not at all good, is their any good solution for this?

My code :

public String solution(int A, int B, int C, int D, int E, int F) {
        List<Integer> nums = new ArrayList<>();
        nums.add(A);
        nums.add(B);
        nums.add(C);
        nums.add(D);
        nums.add(E);
        nums.add(F);
        String earlyTime = "NOT POSSIBLE";

        Collections.sort(nums);

        if(nums.get(0)==0 && nums.get(1)==0 && nums.get(2)==0){
            earlyTime = nums.get(0)+""+nums.get(3)+":"+nums.get(1)+""+nums.get(4)+":"+nums.get(2)+""+nums.get(5);
        }
        else if(nums.get(0) <= 2 && nums.get(0) > -1){

            if(nums.get(1) <=3 && nums.get(1) > -1){

                if(nums.get(2) <= 5 && nums.get(2) > -1){

                    if(nums.get(3) <= 9 && nums.get(3) > -1){

                        if(nums.get(4) <= 5 && nums.get(4) > -1){

                            if(nums.get(5) <= 9 && nums.get(5) > -1){
                                 earlyTime = nums.get(0)+""+nums.get(1)+":"+nums.get(2)+""+nums.get(3)+":"+nums.get(4)+""+nums.get(5);
                            }

                        }
                        else if(nums.get(4) > 5){
                            int tmp = nums.get(3);
                            nums.set(3, nums.get(4));
                            nums.set(4, tmp);

                            if(Integer.parseInt(nums.get(4)+""+nums.get(5)) < 59 && Integer.parseInt(nums.get(4)+""+nums.get(5)) > -1){
                                earlyTime = nums.get(0)+""+nums.get(1)+":"+nums.get(2)+""+nums.get(3)+":"+nums.get(4)+""+nums.get(5);
                            }
                        }
                    }

                }
            }

        }else{
            return "NOT POSSIBLE";
        }
        return earlyTime;
}

Add your code to your question. We can help you correct it. But we do not supply ready code. — RealSkeptic, Feb 12 '18 at 16:41
You can find ideas for improving the algorithm from a similar question asked here: [Find maximum possible time HH:MM by permuting four given digits](https://stackoverflow.com/questions/44664491/find-maximum-possible-time-hhmm-by-permuting-four-given-digits). — Mick Mnemonic, Feb 12 '18 at 16:46
`Integer.parseInt(nums.get(4)+""+nums.get(5))` this makes the code slow. Try `nums.get(4) * 10 + nums.get(5)`. Also I dont see why you always check if the number is > -1, that should automatically be the case, a digit cannot be negative. — maraca, Feb 12 '18 at 17:33
Creating a normal array would be faster too instead of using an ArrayList. If a digit can be negative, then it is sufficient to check index 0 after sorting. — maraca, Feb 12 '18 at 17:39
I guess I now understand the question, after someone voted my answer down without comment. :) — user unknown, Feb 13 '18 at 18:45

score 2 · Answer 1 · answered Feb 12 '18 at 19:55

I have an approach in mind, After taking into consideration some input examples, I came up with this algorithm.

Let's split the 6 numbers into two categories high_number and low_number.

high_number :- Number which are in the range [6,9]

low_number :- Number which are in the range [0,5]

Algorithm:-

Step 1:- Now iterate once over this 6 digits, check whether each digit is either `high_number` or `low_number` and store them in the array called `high_number_array` and `low_number_array` respectively.

Step 2:- Sort both the above array `high_number_array` and `low_number_array`.

Step 3:- There will be three cases here.
 (i) HC = size of high_number_array , LC = size of low_number_array
 (ii) Case HC > LC { not possible to make a valid time } 
 (iii) Case HC == LC { pick alternately from low_number_array and high_number_array and we will get a valid smallest time.
 (iv) Case HC < LC {if HC == 0 or HC == 1 then combine low_number_array and high_number_array } 
 (v) Case HC < LC { if HC == 2, then after combining both arrays, swap 4th and 5th digit.

Try testing this algorithm with a bunch of exampels and u will get the data.

Hope this helps!

Now there are three major cases that

My initial thought was the same, but with input (2, 4, 5, 9, 5, 9 ),(2, 5, 5, 9, 5, 9) this solution fail, not sure how this got up-votes without checking — edwin, Jul 23 '18 at 10:29
@edwin for your information, I wasn't trying to code the exact solution. I just wanted to show an approach if it is possible to have avalid 24hr format time. In case there is a possibility to have a valid 24hr clock, then the user can try the above approach. I have covered all the corner cases like you. Also I feel up-votes are not always about the correct solution. — zenwraight, Jul 23 '18 at 18:37

score 1 · Answer 2 · answered Feb 12 '18 at 20:10

You can just fill up the largest (potentially conflicting) digits first. There are only 3 possible configurations as you can see in the code below:

public String solve(int A, int B, int C, int D, int E, int F) {
  int[] d = {A, B, C, D, E, F};
  Arrays.sort(d);
  if (d[4] < 6) { // 2nd largest digit is smaller 6, we can just fill up
    if (10 * d[0] + d[1] < 24)
      return "" + d[0] + d[1] + ":" + d[2] + d[3] + ":" + d[4] + d[5];
    else
      return "impossible";
  } else if (d[3] < 6) { // 3rd largest digit is smaller 6, put 2nd largest in 4th position
    if (10 * d[0] + d[1] < 24)
      return "" + d[0] + d[1] + ":" + d[2] + d[4] + ":" + d[3] + d[5];
    else
      return "impossible";
  } else if (d[2] < 6) { // 4th largest digit is smaller 6, put 3rd largest in 2nd position
    if (10 * d[0] + d[3] < 24)
      return "" + d[0] + d[3] + ":" + d[1] + d[4] + ":" + d[2] + d[5];
    else
      return "impossible";
  } else {
      return "impossible";
  }
}

score 1 · Answer 3 · answered Aug 11 '18 at 18:12

private String solution(int i, int j, int k, int l, int m, int n) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(i);
        list.add(j);
        list.add(k);
        list.add(l);
        list.add(m);
        list.add(n);
        Collections.sort(list);

        // first two needs to form HH

        // hence HH = list [0] and list[1]

        if (list.get(3) > 5) { // place where 1 needs to be swaped with 3rd
            int temp = list.get(1);
            list.set(1, list.get(3));
            list.set(3, temp);
        }
        System.out.println(list);
        String HH = "" + list.get(0) + list.get(1);

        if (Integer.parseInt(HH) > 23) {
            return "NOT POSSIBLE";
        }
        // now check phisiblility of SS after MM
        if ((list.get(2) * 10 + list.get(3)) < 60 && (list.get(4) * 10 + list.get(5)) < 60) {

        } else if ((list.get(2) * 10 + list.get(3)) < 60 && (list.get(4) * 10 + list.get(5)) > 59) {
            // swap //3 and 4
            System.out.println(list);
            int temp = list.get(3);
            list.set(3, list.get(4));
            list.set(4, temp);
            System.out.println(list);
        } else {
            return "NOT POSSIBLE";
        }
        return HH + ":" + list.get(2) + list.get(3) + ":" + list.get(4) + list.get(5);

    }

Please provide some explanation for your code (aside from inline comments). Thanks. — ggorlen, Aug 11 '18 at 18:32

edwin · Answer 4 · 2019-06-13T11:17:59.480

Here in this problem, I borrow some concept from answer, This is the base logic of my solution

Need minimum of 2 integers in range [0,3] to make a valid hour

Need minimum of 3 integers [0,5] to make valid seconds,min,hour

Maximum two integers [0,9) can only present.

import java.util.stream.IntStream;
import java.util.Arrays;

public class Demo {

    public static void main(String[] args) {
        System.out.println(solution(1, 8, 2, 3, 6, 4));
        System.out.println(solution(0, 0, 0, 7, 8, 9));
        System.out.println(solution(2, 4, 5, 9, 5, 9));
        System.out.println(solution(2, 5, 5, 9, 5, 9));
        System.out.println(solution(6, 5, 4, 3, 2, 1));
        System.out.println(solution(8, 1, 2, 4, 3, 6));
        System.out.println(solution(9, 2, 8, 6, 7, 0));
        System.out.println(solution(0, 0, 0, 0, 0, 0));
        System.out.println(solution(0, 0, 0, 0, 0, 1));
        System.out.println(solution(2, 3, 5, 9, 5, 9));
        System.out.println(solution(0, 0, 2, 4, 0, 0));
        System.out.println(solution(4, 4, 4, 5, 9, 9));
        System.out.println(solution(4, -1, 4, 5, 9, 9));

    }

    public static String solution(int A,int B, int C,int D,int E,int F) {
    //We need minimum of 2 integers in range [0,3] to make a valid hour 
    //We need minimum of 3 integers [0,5] to make valid seconds,min,hour

    //Sort the number in ASC order 
    int[] nums= IntStream.of(A,B,C,D,E,F).filter(n -> n>=0).sorted().toArray();

    if(nums.length !=6)
        return "NOT POSSIBLE";

    int[] splittedTime= new int[] {nums[0]*10+nums[1],nums[2]*10+nums[3],nums[4]*10+nums[5]};
    //splittedTime[0]=hour:splittedTime[1]=minutes:splittedTime[2]=seconds

    if(!validateHour(splittedTime[0]))
        //This means among given 6 integers , 5 integers are > 3, so can't make up a valid hour under 24
        return "NOT POSSIBLE";

    if(!validateMinute(splittedTime[1])) {
        // this means among given 6 integers, 4 integers are greater than > 5, so can't make up valid minutes, seconds 
        return "NOT POSSIBLE";
    }

    if(!validateSecond(splittedTime[2])) {
        if(nums[3]<6) {
            //swapping maximum from minute with, minimum from second 
            int swapMin=nums[4];
            int swapSecond=nums[3];
            nums[3]=swapMin;
            nums[4]=swapSecond;
            //Can directly assign no need to keep it in temp variable
        }else if(nums[3]>6) {
            // Kind of circular swapping between hour, minute and second
            int[] firstHalf = Arrays.copyOfRange(nums, 0, nums.length/2);
            int[] secondHalf = Arrays.copyOfRange(nums, nums.length/2, nums.length);
            nums=IntStream.of(firstHalf[0], secondHalf[0], firstHalf[1], secondHalf[1], firstHalf[2], secondHalf[2]).toArray();
        }

        }

    }

    return String.format ("%1$d%2$d:%3$d%4$d:%5$d%6$d", nums[0], nums[1], nums[2], nums[3], nums[4], nums[5]);
}

    public static boolean validateHour(int hour) {
        return hour<24;
    }

    public static boolean validateMinute(int minute) {
        return minute<60;
    }

    public static boolean validateSecond(int second) {
        return second<60;
    }

}

This solution works, but not sure about performance.

This works with a good performance . Thanks to this answer, same code with a slight modification

 public String solve(int A, int B, int C, int D, int E, int F) {
    int[] d = IntStream.of(A, B, C, D, E, F).filter(n -> n >= 0).sorted().toArray();

          if (d[4] < 6) { // 2nd largest digit is smaller 6, we can just fill up
            if (10 * d[0] + d[1] < 24)
              return "" + d[0] + d[1] + ":" + d[2] + d[3] + ":" + d[4] + d[5];
          } else if (d[3] < 6) { // 3rd largest digit is smaller 6, put 2nd largest in 4th position
            if (10 * d[0] + d[1] < 24)
              return "" + d[0] + d[1] + ":" + d[2] + d[4] + ":" + d[3] + d[5];
          } else if (d[2] < 6) { // 4th largest digit is smaller 6, put 3rd largest in 2nd position
            if (10 * d[0] + d[3] < 24)
              return "" + d[0] + d[3] + ":" + d[1] + d[4] + ":" + d[2] + d[5];
          } 
              return "NOT POSSIBLE";
    }

Find the earliest valid digital 24 hr format time , that can be possible with given 6 digits

4 Answers4