Operaciones mínimas requeridas para hacer N incluso invirtiendo el prefijo de cualquier longitud

Dado un número entero N , la tarea es encontrar el número mínimo de operaciones requeridas para hacer que N sea par, de modo que en una sola operación se pueda invertir el prefijo de cualquier longitud. Si no es posible hacer que N sea un número par, imprima -1.

Ejemplos:

Entrada: N = 376502
Salida: 0
Explicación: 
– N ya es divisible por 2, por lo que es un número par, por lo que el número total de intercambios de prefijos será 0.

Entrada: N = 36543
Salida: 2
Explicación: 
– N no es un número par, por lo que para que sea parejo primero intercambie el prefijo de longitud 2. Ahora N =63543
– Ahora intercambie el prefijo de longitud 5 y N =34536.

Acercarse:

Puede haber 2 casos.

• N es un número par
• N es un número impar .

Ahora,  

• Si N es un número par, el número mínimo de pasos para que N sea un número par será 0.
• Si N es un número impar, puede haber 3 casos.
  1. N no contiene ningún dígito par. En este caso, es imposible hacer que N sea un número par, por lo que la respuesta será -1.
  2. N contiene dígitos pares y el primer dígito de N es par. En este caso, podemos intercambiar el número entero, por lo que el número mínimo de pasos para hacer que N sea un número par será 1.
  3. N contiene dígitos pares y el primer dígito de N no es par. En este caso, primero podemos intercambiar el prefijo hasta cualquier dígito par y luego intercambiar el número entero, por lo que el número mínimo de pasos para hacer que N sea un número par será 2.

Siga los pasos a continuación para resolver el problema:

• Inicialice la string s[] como la representación de string de N.
• Inicialice la variable ans como -1 y len como la longitud de la string s[].
• Si (s[len-1] – ‘0’)%2==0 el conjunto responde como 0.
• De lo contrario, realice las siguientes tareas:
  • Si el primer carácter de la string s[] es par , establezca ans como 1.
  • Itere sobre el rango [0, len) usando la variable i y realice las siguientes tareas:
    • Si s[i] es par, establezca ans como 2 y rompa.
• Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.

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

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum number
// of steps required to make N an even number
void MinSteps(int N)
{
 
    // Converting N into string
    string s = to_string(N);
 
    int ans = -1;
 
    // Number of digits in N
    int len = s.size();
 
    // If the number is even
    if ((s[len - 1] - '0') % 2 == 0) {
        ans = 0;
    }
    else {
 
        // If the first digit is even
        if ((s[0] - '0') % 2 == 0) {
            ans = 1;
        }
        else {
 
            // Checking if s contains
            // any even digits
            for (int i = 0; i < len; i++) {
                if ((s[i] - '0') % 2 == 0) {
                    ans = 2;
                    break;
                }
            }
        }
    }
 
    // Printing the minimum number
    // of steps to make N an even number
    cout << ans << "\n";
}
 
// Driver Code
int main()
{
    int N;
    N = 36543;
 
    MinSteps(N);
}

// Java code for the above approach
import java.util.*;
class GFG
{
 
  // Function to find minimum number
  // of steps required to make N an even number
  static void MinSteps(int N)
  {
 
    // Converting N into String
    String s = String.valueOf(N);
    int ans = -1;
 
    // Number of digits in N
    int len = s.length();
 
    // If the number is even
    if ((s.charAt(len - 1) - '0') % 2 == 0) {
      ans = 0;
    }
    else {
 
      // If the first digit is even
      if ((s.charAt(0) - '0') % 2 == 0) {
        ans = 1;
      }
      else {
 
        // Checking if s contains
        // any even digits
        for (int i = 0; i < len; i++) {
          if ((s.charAt(i) - '0') % 2 == 0) {
            ans = 2;
            break;
          }
        }
      }
    }
 
    // Printing the minimum number
    // of steps to make N an even number
    System.out.print(ans+ "\n");
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N;
    N = 36543;
 
    MinSteps(N);
  }
}
 
// This code is contributed by 29AjayKumar

# python3 code for the above approach
 
# Function to find minimum number
# of steps required to make N an even number
def MinSteps(N):
 
    # Converting N into string
    s = str(N)
    ans = -1
 
    # Number of digits in N
    le = len(s)
 
    # If the number is even
    if ((ord(s[le - 1]) - ord('0')) % 2 == 0):
        ans = 0
 
    else:
 
        # If the first digit is even
        if ((ord(s[0]) - ord('0')) % 2 == 0):
            ans = 1
 
        else:
 
            # Checking if s contains
            # any even digits
            for i in range(0, le):
                if ((ord(s[i]) - ord('0')) % 2 == 0):
                    ans = 2
                    break
 
    # Printing the minimum number
    # of steps to make N an even number
    print(ans)
 
# Driver Code
if __name__ == "__main__":
 
    N = 36543
 
    MinSteps(N)
 
# This code is contributed by rakeshsahni

// C# code for the above approach
using System;
class GFG
{
 
  // Function to find minimum number
  // of steps required to make N an even number
  static void MinSteps(int N)
  {
 
    // Converting N into String
    String s = Convert.ToString(N);
    int ans = -1;
 
    // Number of digits in N
    int len = s.Length;
 
    // If the number is even
    if ((s[len - 1] - '0') % 2 == 0)
    {
      ans = 0;
    }
    else
    {
 
      // If the first digit is even
      if ((s[0] - '0') % 2 == 0)
      {
        ans = 1;
      }
      else
      {
 
        // Checking if s contains
        // any even digits
        for (int i = 0; i < len; i++)
        {
          if ((s[i] - '0') % 2 == 0)
          {
            ans = 2;
            break;
          }
        }
      }
    }
 
    // Printing the minimum number
    // of steps to make N an even number
    Console.Write(ans + "\n");
  }
 
  // Driver Code
  public static void Main()
  {
    int N;
    N = 36543;
 
    MinSteps(N);
  }
}
 
// This code is contributed by Saurabh Jaiswal

<script>
 
// JavaScript code for the above approach
 
// Function to find minimum number
// of steps required to make N an even number
const MinSteps = (N) => {
     
    // Converting N into string
    let s = N.toString();
 
    let ans = -1;
 
    // Number of digits in N
    let len = s.length;
 
    // If the number is even
    if ((s.charCodeAt(len - 1) -
       '0'.charCodeAt(0)) % 2 == 0)
    {
        ans = 0;
    }
    else
    {
         
        // If the first digit is even
        if ((s.charCodeAt(0) -
           '0'.charCodeAt(0)) % 2 == 0)
        {
            ans = 1;
        }
        else
        {
             
            // Checking if s contains
            // any even digits
            for(let i = 0; i < len; i++)
            {
                if ((s.charCodeAt(i) -
                   '0'.charCodeAt(0)) % 2 == 0)
                {
                    ans = 2;
                    break;
                }
            }
        }
    }
 
    // Printing the minimum number
    // of steps to make N an even number
    document.write(`${ans}<br/>`);
}
 
// Driver Code
let N = 36543;
 
MinSteps(N);
 
// This code is contributed by rakeshsahni
 
</script>

2

Complejidad de tiempo: O(len), donde len es la longitud de la string.
Espacio Auxiliar: O(len)