Maximize the missing values ​​within a given time period, in the format HH:MM

Represents the given string of length five as a time in HH:MM format. The string may contain some "?" and we have to replace them with any number so that the result is a valid time and probably the largest possible time. Furthermore, the given string numbers will be valid and the ":" will appear at the exact position of the string. We will use brute force methods first and then use efficient methods.

ExampleExample

Enter 1

Given string: 12:5?
Output: 12:59

The Chinese translation of

Explanation

is:

Explanation

We only have one spot to fill and the maximum time we can get is 12:59.

Enter 2

Given string: ?0:?9
Output: 20:59

The Chinese translation of

Explanation

is:

Explanation

We have two empty slots here, first we will focus on the hour part, we have three choices 0, 1 and 2 to fill it. For the minutes part we have choices from 0 to 5, to maximize we can fill in 5.

method

We've looked at examples, now let's look at the different types of situations we might face −

• We have two parts of the string, the hour part and the minute part.

• The hour part ranges from 0 to 23, and the minute part ranges from 0 to 59.

• There are more situations in the hour part−

• ‘x?’ where x can be 0, 1 and 2. For 0, we can choose 0 as the best choice, for 1, we can choose 9 as the best choice, and for 2, we can choose 3 as the best choice.

• '?x', where x can range from 0 to 9. If x is in the range of 0 to 3, we can replace it with 2, otherwise 1 will be the best.

• ‘??’ Since we need to maximize, we replace it with 23.

• Meeting minutes, some further cases −

• ‘x?’ where x can be in the range of 0 to 5. 9 would be our best choice to replace '?'.

• ‘?x’ where x can be in the range of 0 to 9. 5 would be our best choice to replace '?'.

• "??" because we have to maximize, and then we replace it with 59.

Let’s take a look at the code that implements the above steps -

The Chinese translation of

Example

is:

Example

#include <iostream>
using namespace std;
// function to replace hours
string replaceHours(string s){
   if(s[0] == '?' && s[1] == '?'){
      //Both hour characters are '?'
      // replace with the maximum hour we can achieve 
      s[0] = '2';
      s[1] = '3';
   }
   else if(s[0] == '?'){
      // if the second number of hours is in the range 0 to 3
      // replace by 2
      if(s[1] < 4){
         s[0] = '2';
      }
      else{
         s[0] = '1'; // otherwise replace by one 
      }
   }
   else if(s[1] == '?'){
      // if the first character is '2' we can go only upto 3
      if(s[0] == '2'){
         s[1] = '3';
      }
      else{
         s[1] = '9'; // else we can go for 9 
      }
   }
   return s;
}
// function to replace minutes
string replaceMinutes(string s){
   if(s[3] == '?' && s[4] == '?'){
      // both minutes characters are '?'
      // replace with maximum minutes we can acheive 
      s[3] = '5';
      s[4] = '9';
   }
   else if(s[3] == '?'){
      // we can maximum get 5 here 
      s[3] = '5';
   }
   else if(s[4] == '?'){
      // we can get maximum 9 here
      s[4] = '9';
   }
   return s;
}
int main(){
   string str = "2?:3?"; // given string 
   // calling the function for updation of the minutes 
   str = replaceMinutes(str);
   // calling to the function for updation of the hours
   str = replaceHours(str);
   // printing the final answer
   cout<<"The maximum time we can get by replacing ? is: "<< str<<endl;
   return 0;
}

Output

The maximum time we can get by replacing ? is: 23:39

Time and space complexity

The time complexity of the above code is O(1) or constant because we are not using any loops or recursive calls, just checking the if-else condition

The space complexity of the above code is O(1) because we are not using any extra space. Also, for this function, the size of the string we pass is always a fixed 5.

Note: In order to make the code more beautiful or readable, you can use switch statements. They will not affect time or space complexity and will make reading more efficient.

Also, backtracking and rechecking is a solution, but this will check every case and is not efficient to implement here.

in conclusion

In this tutorial, we were given a string representing time in 24-hour format. There are some "?" in the string that need to be replaced to obtain the maximum valid time, and the characters in the string are guaranteed to always point to the valid time. We used an if-else condition and two functions to replace the "?" with the appropriate case. Since we are not using any loops or recursive functions, the time and space complexity of the above code is constant.

The above is the detailed content of Maximize the missing values ​​within a given time period, in the format HH:MM. For more information, please follow other related articles on the PHP Chinese website!