Find the max date and time from given set of digits in java

user_10825043 0
Viewed 135

The problem states that there are some random digits given as input and we have to find the maximum date and time in the format MM/DD HH:MM. Ex:

Input is: 2,2,3,1,3,3,3,5,6,2,0

Output is: 12/30 23:56

I tried the brute force method where each digit is combined with every other digit to form a 2 digit number and so on. But the whole program had around 8 or 9 for loops. Is there a more efficient way to do this??

Edit1: If no possible month or date or time can be formed then the output must be 0. There is no auto insertion of 0s i.e. if you want to form a month 09 then 0 has to be in input and there cannot be repetition of digits.

datetime java
2 Answers

If you need a largest date, I can think of something like that (in preudocode):

Turn the input digits into a MultiSet // e.g. https://www.geeksforgeeks.org/multiset-interface-guava-java/
for i = 12 to 1 // find the biggest possible month
  try to find if the digits of i are in the multi set. if they are, init the month value & remove them from the multi set.
for d = 31 to 1 // get the biggest possible day
  same
for h = 23 to 1 // get the biggest possible hour
  same
for m = 59 to 1 // get the biggest possible minute
  same
user_54588270

How about this:

 - Calculate the maximum month (in order - 12, 11, 10, 09...).
  - on the remaining digits, search for a *valid* solution.
  - if no valid solution is found, decrease the month to the next highest option.
  - repeat until the maximum month with a valid solution is found.

Repeat on each segment in descending order.

The logic is based on 2 facts:

  1. It is better to be higher in a high-value segment than in all the lower ones (02/01 00:00 is better than 01/31 23:59).
  2. Searching for a valid solution is much faster than searching for the maximum one (you can start from constraints, for example).
user_29247840
Related