Tiempo máximo tal que la diferencia absoluta entre la hora y el minuto se encuentra en un rango dado

Dado un valor de tiempo de 24 horas , en algunos números hay signos de interrogación (‘?’) y dos números enteros L y R. El signo de interrogación se puede reemplazar con cualquier número. La tarea es encontrar el tiempo máximo tal que la diferencia absoluta entre el valor de la hora y el valor de los minutos se encuentre en el intervalo [ L, R ]. Si no existe ningún valor posible de tiempo, imprima -1 .

Ejemplos:

Entrada: tiempo = “2?:03”, L = 5, R = 18 
Salida: 21:03 
Explicación: Dado que la diferencia es 21 – 3 = 18 y el valor de tiempo 21:03 es el valor más grande posible cuya diferencia se encuentra en el rango [5, 18]

Entrada: tiempo = “??:??”, L = 60, R = 69 
Salida: -1 
Explicación: Dado que la máxima diferencia posible entre el valor de la hora y el valor de los minutos es 59, no es posible ningún valor de tiempo. 
 

Enfoque: 
ejecutaremos dos bucles anidados, uno para representar el valor de ‘hora’ de 23 a 0 y otro para representar el valor de ‘minuto’ de 59 a 0. Seguimos disminuyendo el valor de ‘hora’ y ‘minuto’ hasta que obtengamos el tiempo deseado valor.  

1. Dado que se desea el valor de tiempo máximo, disminuimos el valor de ‘hora’ de 23 a 0 y, de manera similar, el valor de ‘minuto’ de 59 a 0.
2. Después de disminuir el valor de ‘hora’ y ‘minuto’, debemos verificar si el valor de ‘hora’ y ‘minuto’ es válido o no.
3. El cambio en el valor de ‘hora’ y ‘minuto’ solo se permite en aquellas posiciones que tienen ‘?’. Los cambios en otras posiciones invalidarán el valor del tiempo. Para asegurar esto, llamaremos a la función isValid().
4. Continúe disminuyendo el valor de ‘hora’ y ‘minuto’ hasta encontrar un tiempo válido cuya diferencia se encuentre en el rango [ L, R ].
5. Si no se encuentra una hora válida, imprima «-1».

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function checks whether
// given time is correct
bool isValid(char a1, char a2,
             string str, int flag)
{
 
    char v1, v2;
    // To check minute value of time
    if (flag == 0) {
        v1 = str[4];
        v2 = str[3];
    }
    else {
        // To check hour value of time
        v1 = str[1];
        v2 = str[0];
    }
 
    // Changes in value is not allowed
    // at position where '?' is not
    // present
    if (v1 != a1 && v1 != '?')
        return false;
    if (v2 != a2 && v2 != '?')
        return false;
 
    return true;
}
 
// Function checks whether
// the absolute difference
// between hour and minute
// value is within [L, R]
bool inRange(int hh,
             int mm, int L, int R)
{
    int a = abs(hh - mm);
 
    // Checks if the difference is outside
    // the give range
    if (a < L || a > R)
        return false;
 
    return true;
}
 
// Displays time in proper
// 24-hour format
void displayTime(int hh, int mm)
{
    if (hh > 10)
        cout << hh << ":";
    else if (hh < 10)
        cout << "0" << hh << ":";
 
    if (mm > 10)
        cout << mm << endl;
    else if (mm < 10)
        cout << "0" << mm << endl;
}
 
// Function find the desired
// value of time whose difference
// lies in the range [L, R]
void maximumTimeWithDifferenceInRange(
    string str,
    int L, int R)
{
    int i, j;
    int h1, h2, m1, m2;
 
    // Decrease hour value from 23 to 0
    for (i = 23; i >= 0; i--) {
        h1 = i % 10;
        h2 = i / 10;
 
        // Check if the hour value is valid
        // if not valid then no need to change
        // minute value, since time will still
        // remain in valid, to check hour value
        // flag is set to 1.
        if (!isValid(h1 + '0', h2 + '0', str, 1)) {
            continue;
        }
 
        // Decrease minute value from 59 to 0
        for (j = 59; j >= 0; j--) {
            m1 = j % 10;
            m2 = j / 10;
 
            // Check if the minute value is valid,
            // if not valid then skip the current
            // iteration, to check 'minute' value
            // flag is set to 0.
            if (!isValid(m1 + '0', m2 + '0', str, 0)) {
                continue;
            }
 
            if (inRange(i, j, L, R)) {
                displayTime(i, j);
                return;
            }
        }
    }
    if (inRange(i, j, L, R))
        displayTime(i, j);
    else
        cout << "-1" << endl;
}
 
// Driver code
int main()
{
    // Input time
    string timeValue = "??:??";
 
    // Difference range
    int L = 20, R = 39;
    maximumTimeWithDifferenceInRange(
        timeValue,
        L, R);
    return 0;
}

// Java program for
// the above approach
import java.util.*;
class GFG {
   
// Function checks whether
// given time is correct
static boolean isValid(char a1, char a2,
                       String str, int flag)
{
  char v1, v2;
   
  // To check minute value of time
  if (flag == 0)
  {
    v1 = str.charAt(4);
    v2 = str.charAt(3);
  }
  else
  {
    // To check hour value of time
    v1 = str.charAt(1);
    v2 = str.charAt(0);
  }
 
  // Changes in value is not allowed
  // at position where '?' is not
  // present
  if (v1 != a1 && v1 != '?')
    return false;
  if (v2 != a2 && v2 != '?')
    return false;
 
  return true;
}
 
// Function checks whether
// the absolute difference
// between hour and minute
// value is within [L, R]
static boolean inRange(int hh, int mm,
                       int L, int R)
{
  int a = Math.abs(hh - mm);
 
  // Checks if the difference
  // is outside the give range
  if (a < L || a > R)
    return false;
 
  return true;
}
 
// Displays time in proper
// 24-hour format
static void displayTime(int hh, int mm)
{
  if (hh > 10)
    System.out.print(hh + ":");
  else if (hh < 10)
    System.out.print("0" + hh + ":");
 
  if (mm > 10)
    System.out.println(mm);
  else if (mm < 10)
    System.out.println("0" + mm);
}
 
// Function find the desired
// value of time whose difference
// lies in the range [L, R]
static void maximumTimeWithDifferenceInRange(String str,
                                             int L,
                                             int R)
{
  int i = 0, j = 0;
  int h1, h2, m1, m2;
 
  // Decrease hour value
  // from 23 to 0
  for (i = 23; i >= 0; i--)
  {
    h1 = i % 10;
    h2 = i / 10;
 
    // Check if the hour value
    // is valid if not valid
    // then no need to change
    // minute value, since time
    // will still remain in valid,
    // to check hour value
    // flag is set to 1.
    if (!isValid((char)h1,
                 (char)h2, str, 1))
    {
      continue;
    }
 
    // Decrease minute value
    // from 59 to 0
    for (j = 59; j >= 0; j--)
    {
      m1 = j % 10;
      m2 = j / 10;
 
      // Check if the minute value
      // is valid, if not valid
      // then skip the current
      // iteration, to check
      // 'minute' value
      // flag is set to 0.
      if (!isValid((char)m1,
                   (char)m2, str, 0))
      {
        continue;
      }
 
      if (inRange(i, j, L, R))
      {
        displayTime(i, j);
        return;
      }
    }
  }
  if (inRange(i, j, L, R))
    displayTime(i, j);
  else
    System.out.println("-1");
}
 
// Driver code
public static void main(String[] args)
{
  // Input time
  String timeValue = "??:??";
 
  // Difference range
  int L = 20, R = 39;
  maximumTimeWithDifferenceInRange(timeValue, L, R);
}
}
 
// This code is contributed by Chitranayal

# Python3 program for the above approach
 
# Function checks whether
# given time is correct
def isValid(a1, a2, strr, flag):
 
    v1, v2 = 0, 0
     
    # To check minute value of time
    if (flag == 0):
        v1 = strr[4]
        v2 = strr[3]
    else:
         
        # To check hour value of time
        v1 = strr[1]
        v2 = strr[0]
 
    # Changes in value is not allowed
    # at position where '?' is not
    # present
    if (v1 != a1 and v1 != '?'):
        return False
    if (v2 != a2 and v2 != '?'):
        return False
 
    return True
 
# Function checks whether
# the absolute difference
# between hour and minute
# value is within [L, R]
def inRange(hh, mm, L, R):
    a = abs(hh - mm)
 
    # Checks if the difference is
    # outside the give range
    if (a < L or a > R):
        return False
 
    return True
 
# Displays time in proper
# 24-hour format
def displayTime(hh, mm):
 
    if (hh > 10):
        print(hh, end = ":")
    elif (hh < 10):
        print("0", hh, end = ":")
 
    if (mm > 10):
        print(mm)
    elif (mm < 10):
        print("0", mm)
 
# Function find the desired
# value of time whose difference
# lies in the range [L, R]
def maximumTimeWithDifferenceInRange(strr, L, R):
     
    i, j = 0, 0
    h1, h2, m1, m2 = 0, 0, 0, 0
 
    # Decrease hour value from 23 to 0
    for i in range(23, -1, -1):
        h1 = i % 10
        h2 = i // 10
 
        # Check if the hour value is valid
        # if not valid then no need to change
        # minute value, since time will still
        # remain in valid, to check hour value
        # flag is set to 1.
        if (not isValid(chr(h1), chr(h2), strr, 1)):
            continue
 
        # Decrease minute value from 59 to 0
        for j in range(59, -1, -1):
            m1 = j % 10
            m2 = j // 10
 
            # Check if the minute value is valid,
            # if not valid then skip the current
            # iteration, to check 'minute' value
            # flag is set to 0.
            if (not isValid(chr(m1), chr(m2),
                            strr, 0)):
                continue
 
            if (inRange(i, j, L, R)):
                displayTime(i, j)
                return
 
                 
    if (inRange(i, j, L, R)):
        displayTime(i, j)
    else:
        print(-1)
 
# Driver code
 
# Input time
timeValue = "??:??"
 
# Difference range
L = 20
R = 39
     
maximumTimeWithDifferenceInRange(timeValue, L, R)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
 
class GFG{
     
// Function checks whether
// given time is correct
static bool isValid(char a1, char a2,
                    string str, int flag)
{
    char v1, v2;
     
    // To check minute value of time
    if (flag == 0)
    {
        v1 = str[4];
        v2 = str[3];
    }
    else
    {
         
        // To check hour value of time
        v1 = str[1];
        v2 = str[0];
    }
     
    // Changes in value is not allowed
    // at position where '?' is not
    // present
    if (v1 != a1 && v1 != '?')
    {
        return false;
    }
    if (v2 != a2 && v2 != '?')
    {
        return false;
    }
    return true;
}
 
// Function checks whether
// the absolute difference
// between hour and minute
// value is within [L, R]
static bool inRange(int hh, int mm,
                    int L, int R)
{
    int a = Math.Abs(hh - mm);
     
    // Checks if the difference
    // is outside the give range
    if (a < L || a > R)
    {
        return false;
    }
    return true;
}
 
// Displays time in proper
// 24-hour format
static void displayTime(int hh, int mm)
{
    if (hh > 10)
    {
        Console.Write(hh + ":");
    }
    else if (hh < 10)
    {
        Console.Write("0" + hh + ":");
    }
    if (mm > 10)
    {
        Console.Write(mm);
    }
    else if (mm < 10)
    {
        Console.Write("0" + mm);
    }
}
 
// Function find the desired
// value of time whose difference
// lies in the range [L, R]
static void maximumTimeWithDifferenceInRange(
    string str, int L, int R)
{
    int i = 0, j = 0;
    int h1, h2, m1, m2;
     
    // Decrease hour value
    // from 23 to 0
    for(i = 23; i >= 0; i--)
    {
        h1 = i % 10;
        h2 = i / 10;
         
        // Check if the hour value
        // is valid if not valid
        // then no need to change
        // minute value, since time
        // will still remain in valid,
        // to check hour value
        // flag is set to 1.   
        if (!isValid((char)h1, (char)h2, str, 1))
        {
            continue;
        }
         
        // Decrease minute value
        // from 59 to 0
        for(j = 59; j >= 0; j--)
        {
            m1 = j % 10;
            m2 = j / 10;
             
            // Check if the minute value
            // is valid, if not valid
            // then skip the current
            // iteration, to check
            // 'minute' value
            // flag is set to 0.
            if (!isValid((char)m1, (char)m2, str, 0))
            {
                continue;
            }
            if (inRange(i, j, L, R))
            {
                displayTime(i, j);
                return;
            }
        }
    }
    if (inRange(i, j, L, R))
    {
        displayTime(i, j);
    }
    else
    {
        Console.WriteLine("-1");
    }
}
 
// Driver code
static public void Main()
{
     
    // Input time
    string timeValue = "??:??";
     
    // Difference range
    int L = 20, R = 39;
     
    maximumTimeWithDifferenceInRange(timeValue, L, R);
}
}
 
// This code is contributed by avanitrachhadiya2155

<script>
// Javascript program for
// the above approach
 
// Function checks whether
// given time is correct
function isValid(a1, a2, str, flag)
{
    let v1, v2;
    
  // To check minute value of time
  if (flag == 0)
  {
    v1 = str[4];
    v2 = str[3];
  }
  else
  {
    // To check hour value of time
    v1 = str[1];
    v2 = str[0];
  }
  
  // Changes in value is not allowed
  // at position where '?' is not
  // present
  if (v1 != a1 && v1 != '?')
    return false;
  if (v2 != a2 && v2 != '?')
    return false;
  
  return true;
}
 
// Function checks whether
// the absolute difference
// between hour and minute
// value is within [L, R]
function inRange(hh,mm,L,R)
{
    let a = Math.abs(hh - mm);
  
  // Checks if the difference
  // is outside the give range
  if (a < L || a > R)
    return false;
  
  return true;
}
 
// Displays time in proper
// 24-hour format
function displayTime(hh,mm)
{
    if (hh > 10)
    document.write(hh + ":");
  else if (hh < 10)
    document.write("0" + hh + ":");
  
  if (mm > 10)
    document.write(mm+"<br>");
  else if (mm < 10)
    document.write("0" + mm+"<br>");
}
 
// Function find the desired
// value of time whose difference
// lies in the range [L, R]   
function maximumTimeWithDifferenceInRange(str,L,R)
{
    let i = 0, j = 0;
  let h1, h2, m1, m2;
  
  // Decrease hour value
  // from 23 to 0
  for (i = 23; i >= 0; i--)
  {
    h1 = i % 10;
    h2 = Math.floor(i / 10);
  
    // Check if the hour value
    // is valid if not valid
    // then no need to change
    // minute value, since time
    // will still remain in valid,
    // to check hour value
    // flag is set to 1.
    if (!isValid(String.fromCharCode(h1),String.fromCharCode(h2), str, 1))
    {
      continue;
    }
  
    // Decrease minute value
    // from 59 to 0
    for (j = 59; j >= 0; j--)
    {
      m1 = j % 10;
      m2 = Math.floor(j / 10);
  
      // Check if the minute value
      // is valid, if not valid
      // then skip the current
      // iteration, to check
      // 'minute' value
      // flag is set to 0.
      if (!isValid(String.fromCharCode(m1),
                   String.fromCharCode(m2), str, 0))
      {
        continue;
      }
  
      if (inRange(i, j, L, R))
      {
        displayTime(i, j);
        return;
      }
    }
  }
  if (inRange(i, j, L, R))
    displayTime(i, j);
  else
    document.write("-1<br>");
}
 
// Driver code
// Input time
  let timeValue = "??:??";
  
  // Difference range
  let L = 20, R = 39;
  maximumTimeWithDifferenceInRange(timeValue, L, R);
 
// This code is contributed by unknown2108
</script>

23:59

Tiempo Complejidad: O(1)  
Espacio Auxiliar: O(1)