Se requieren incrementos mínimos de 1 o K para convertir una string en otra string dada

Posted on by Rudeus Greyrat

Dadas dos strings X e Y , ambas compuestas por N letras mayúsculas y un número entero K , la tarea es encontrar el recuento mínimo de incrementos cíclicos de cualquier carácter en la string X por 1 o K necesarios para convertir la string X en una string Y.

Incrementos cíclicos: Incrementar el carácter ‘Z’ en 1 o K comienza desde el carácter ‘A’ .

Ejemplos:

Entrada: X = “ABCT”, Y = “PBDI”, K = 13
Salida: 7
Explicación: 
Convierta el carácter A a P. Los incrementos requeridos son 13 (A a N), 1 (N a O), 1 (O a PAGS). Por lo tanto, la cuenta total es 3.
El carácter B permanece sin cambios. Por lo tanto, el conteo total sigue siendo 3.
Convierta el carácter C a D. Los incrementos requeridos son 1 (C a D). Por lo tanto, el conteo total es 4.
Convierta el carácter T a I. Los incrementos requeridos son de 13 (T a G), 1 (G a H), 1 (H a I). Por lo tanto, la cuenta total es 7.

Entrada: X = “ABCD”, Y = “ABCD”, K = 6
Salida: 0

Enfoque: siga los pasos a continuación para resolver este problema:

  • Inicialice una variable, digamos count , para almacenar el incremento mínimo requerido para convertir la string X en la string Y .
  • Atraviese la string X y para cada carácter en la string X , hay tres casos siguientes:
    • Cuando los caracteres en ambas strings X e Y sean iguales, continúe .
    • Cuando los caracteres en la string Y son mayores que la string X , agregue el valor (Y[i] – X[i])/K y (Y[i] – X[i]) módulo K al conteo .
    • Cuando los caracteres en la string X son mayores que la string Y , reste el carácter X[i] de 90 y reste 64 de Y[i] para calcular la diferencia cíclica y luego agregue la diferencia módulo K y diferencia/K al conteo .
  • Después de completar los pasos anteriores, imprima el conteo como el número mínimo de incrementos requeridos.

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

C++

// CPP program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to count minimum increments
// by 1 or K required to convert X to Y
void countOperations(
  string X, string Y, int K)
{
 
  int count = 0;
 
  // Traverse the string X
  for (int i = 0; i < X.length(); i++)
  {
 
    int c = 0;
 
    // Case 1
    if (X[i] == Y[i])
      continue;
 
    // Case 2
    else if (X[i] < Y[i])
    {
 
      // Add the difference/K to
      // the count
      if ((Y[i] - X[i]) >= K) {
        c = (Y[i] - X[i]) / K;
      }
 
      // Add the difference%K to
      // the count
      c += (Y[i] - X[i]) % K;
    }
 
    // Case 3
    else {
      int t = 90 - X[i];
      t += Y[i] - 65 + 1;
 
      // Add the difference/K to
      // the count
      if (t >= K)
        c = t / K;
 
      // Add the difference%K to
      // the count
      c += (t % K);
    }
    count += c;
  }
 
  // Print the answer
  cout << count << endl;
}
 
// Driver Code
int main()
{
  string X = "ABCT", Y = "PBDI";
  int K = 6;
  countOperations(X, Y, K);
}
 
// This code is contributed by ipg2016107.

Java

// Java program for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to count minimum increments
    // by 1 or K required to convert X to Y
    public static void countOperations(
        String X, String Y, int K)
    {
        // Convert String to character array
        char ch1[] = X.toCharArray();
        char ch2[] = Y.toCharArray();
        int count = 0;
 
        // Traverse the string X
        for (int i = 0; i < X.length(); i++) {
 
            int c = 0;
 
            // Case 1
            if (ch1[i] == ch2[i])
                continue;
 
            // Case 2
            else if (ch1[i] < ch2[i]) {
 
                // Add the difference/K to
                // the count
                if (((int)ch2[i]
                     - (int)ch1[i])
                    >= K) {
                    c = ((int)ch2[i]
                         - (int)ch1[i])
                        / K;
                }
 
                // Add the difference%K to
                // the count
                c += ((int)ch2[i]
                      - (int)ch1[i])
                     % K;
            }
 
            // Case 3
            else {
                int t = 90 - (int)ch1[i];
                t += (int)ch2[i] - 65 + 1;
 
                // Add the difference/K to
                // the count
                if (t >= K)
                    c = t / K;
 
                // Add the difference%K to
                // the count
                c += (t % K);
            }
 
            count += c;
        }
 
        // Print the answer
        System.out.print(count);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String X = "ABCT", Y = "PBDI";
        int K = 6;
        countOperations(X, Y, K);
    }
}

Python3

# Python program for the above approach
 
# Function to count minimum increments
# by 1 or K required to convert X to Y
def countOperations(X, Y, K):
    count = 0
     
    # Traverse the string X
    for i in range(len(X)):
        c = 0
         
        # Case 1
        if (X[i] == Y[i]):
            continue
 
        # Case 2
        elif (X[i] < Y[i]):
           
            # Add the difference/K to
            # the count
            if ((ord(Y[i]) - ord(X[i])) >= K):
                c = (ord(Y[i]) - ord(X[i])) // K
                 
            # Add the difference%K to
            # the count
            c += (ord(Y[i]) - ord(X[i])) % K
             
        # Case 3
        else:
            t = 90 - ord(X[i])
            t += ord(Y[i]) - 65 + 1
             
            # Add the difference/K to
            # the count
            if (t >= K):
                c = t // K
                 
            # Add the difference%K to
            # the count
            c += (t % K)
        count += c
         
    # Print the answer
    print(count)
 
# Driver Code
X = "ABCT"
Y = "PBDI"
K = 6
countOperations(X, Y, K)
 
# This code is contributed by aditya7409.

C#

// C# program for the above approach
using System;
class GFG
{
 
  // Function to count minimum increments
  // by 1 or K required to convert X to Y
  static void countOperations(
    string X, string Y, int K)
  {
    // Convert String to character array
    char[] ch1 = X.ToCharArray();
    char[] ch2 = Y.ToCharArray();
    int count = 0;
 
    // Traverse the string X
    for (int i = 0; i < X.Length; i++) {
 
      int c = 0;
 
      // Case 1
      if (ch1[i] == ch2[i])
        continue;
 
      // Case 2
      else if (ch1[i] < ch2[i]) {
 
        // Add the difference/K to
        // the count
        if (((int)ch2[i]
             - (int)ch1[i])
            >= K) {
          c = ((int)ch2[i]
               - (int)ch1[i])
            / K;
        }
 
        // Add the difference%K to
        // the count
        c += ((int)ch2[i]
              - (int)ch1[i])
          % K;
      }
 
      // Case 3
      else {
        int t = 90 - (int)ch1[i];
        t += (int)ch2[i] - 65 + 1;
 
        // Add the difference/K to
        // the count
        if (t >= K)
          c = t / K;
 
        // Add the difference%K to
        // the count
        c += (t % K);
      }
 
      count += c;
    }
 
    // Print the answer
    Console.WriteLine(count);
  }
 
  // Driver code
  static void Main()
  {
    string X = "ABCT", Y = "PBDI";
    int K = 6;
    countOperations(X, Y, K);
  }
}
 
// This code is contributed by susmitakundugoaldanga.

Javascript

<script>
      // JavaScript program for the above approach
      // Function to count minimum increments
      // by 1 or K required to convert X to Y
      function countOperations(X, Y, K)
      {
        var count = 0;
 
        // Traverse the string X
        for (var i = 0; i < X.length; i++)
        {
          var c = 0;
 
          // Case 1
          if (X[i] === Y[i]) continue;
           
          // Case 2
          else if (X[i].charCodeAt(0) < Y[i].charCodeAt(0))
          {
           
            // Add the difference/K to
            // the count
            if (Y[i].charCodeAt(0) - X[i].charCodeAt(0) >= K)
            {
              c = (Y[i].charCodeAt(0) - X[i].charCodeAt(0)) / K;
            }
 
            // Add the difference%K to
            // the count
            c += (Y[i].charCodeAt(0) - X[i].charCodeAt(0)) % K;
          }
 
          // Case 3
          else {
            var t = 90 - X[i].charCodeAt(0);
            t += Y[i].charCodeAt(0) - 65 + 1;
 
            // Add the difference/K to
            // the count
            if (t >= K) {
              c = parseInt(t / K);
            }
 
            // Add the difference%K to
            // the count
            c += parseInt(t % K);
          }
          count = parseInt(count + c);
        }
 
        // Print the answer
        document.write(count + "<br>");
      }
 
      // Driver Code
      var X = "ABCT",
        Y = "PBDI";
      var K = 6;
      countOperations(X, Y, K);
       
      // This code is contributed by rdtank.
    </script>
Producción: 

11

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por krish_45 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *