Número mínimo de operaciones para convertir una array A en una array B agregando un número entero a un subarreglo

Dados dos arreglos A[] y B[] de longitud N , la tarea es encontrar el número mínimo de operaciones en las que el arreglo A se puede convertir en el arreglo B donde cada operación consiste en agregar un entero K a un subarreglo de L a r

Ejemplos: 

Entrada: A[] = {3, 7, 1, 4, 1, 2}, B[] = {3, 7, 3, 6, 3, 2} 
Salida: 1 
Explicación: 
En el ejemplo anterior, solo una operación se requiere para convertir de A a B: L = 3, R = 5 y K = 2 
Array después de la siguiente operación: 
Índice 0: A[0] = 3, B[0] = 3 
Índice 1: A[1] = 7, B[1] = 7 
Índice 2: A[2] = 1 + 2 = 3, B[2] = 3 
Índice 3: A[3] = 4 + 2 = 6, B[3] = 6 
Índice 4 : A[4] = 1 + 2 = 3, B[4] = 3 
Índice 5: A[5] = 2, B[5] = 2

Entrada: A[] = {1, 1, 1, 1, 1}, B[] = {1, 2, 1, 3, 1} 
Salida: 2 
Explicación: 
En el ejemplo anterior, solo se requiere una operación para convertir de A a B – 
Operación 1: Sumar 1 a L = 2 a R = 2 
Operación 2: Sumar 2 a L = 4 a R = 4 
 

Enfoque: La idea es contar los elementos consecutivos, en la array A, que tienen una diferencia igual con el elemento correspondiente en la array B.

• Encuentre la diferencia del elemento correspondiente de la array A y B:

Difference = A[i] - B[i]

• Si la diferencia de los elementos correspondientes es igual a 0, continúe buscando el siguiente índice.
• De lo contrario, aumente el índice hasta que la diferencia entre los elementos consecutivos no sea igual a la diferencia anterior de los elementos consecutivos.
• Incremente el conteo en 1, hasta que todos los índices se iteren con la misma diferencia.
• Al final, devuelva el recuento como el número mínimo de operaciones.

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

// C++ implementation to find the
// minimum number of operations in
// which the array A can be converted
// to another array B
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// number of operations in which
// array A can be converted to array B
void checkArray(int a[], int b[], int n)
{
    int operations = 0;
    int i = 0;
     
    // Loop to iterate over the array
    while (i < n) {
         
        // if both elements are equal
        // then move to next element
        if (a[i] - b[i] == 0) {
            i++;
            continue;
        }
 
        // Calculate the difference
        // between two elements
        int diff = a[i] - b[i];
        i++;
 
        // loop while the next pair of
        // elements have same difference
        while (i < n &&
           a[i] - b[i] == diff) {
            i++;
        }
 
        // Increase the number of
        // operations by 1
        operations++;
    }
 
    // Print the number of
    // operations required
    cout << operations << "\n";
}
 
// Driver Code
int main()
{
    int a[] = { 3, 7, 1, 4, 1, 2 };
    int b[] = { 3, 7, 3, 6, 3, 2 };
    int size = sizeof(a) / sizeof(a[0]);
 
    checkArray(a, b, size);
 
    return 0;
}

// Java implementation to find the
// minimum number of operations in
// which the array A can be converted
// to another array B
class GFG {
 
    // Function to find the minimum
    // number of operations in which
    // array A can be converted to array B
    static void checkArray(int a[], int b[], int n)
    {
        int operations = 0;
        int i = 0;
         
        // Loop to iterate over the array
        while (i < n) {
             
            // if both elements are equal
            // then move to next element
            if (a[i] - b[i] == 0) {
                i++;
                continue;
            }
     
            // Calculate the difference
            // between two elements
            int diff = a[i] - b[i];
            i++;
     
            // loop while the next pair of
            // elements have same difference
            while (i < n &&
               a[i] - b[i] == diff) {
                i++;
            }
     
            // Increase the number of
            // operations by 1
            operations++;
        }
     
        // Print the number of
        // operations required
        System.out.println(operations);
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int a[] = { 3, 7, 1, 4, 1, 2 };
        int b[] = { 3, 7, 3, 6, 3, 2 };
        int size = a.length;
     
        checkArray(a, b, size);
    }
}
 
// This code is contributed by AnkitRai01

// C# implementation to find the
// minimum number of operations in
// which the array A can be converted
// to another array B
using System;
 
class GFG {
 
    // Function to find the minimum
    // number of operations in which
    // array A can be converted to array B
    static void checkArray(int []a, int []b, int n)
    {
        int operations = 0;
        int i = 0;
         
        // Loop to iterate over the array
        while (i < n) {
             
            // if both elements are equal
            // then move to next element
            if (a[i] - b[i] == 0) {
                i++;
                continue;
            }
     
            // Calculate the difference
            // between two elements
            int diff = a[i] - b[i];
            i++;
     
            // loop while the next pair of
            // elements have same difference
            while (i < n &&
               a[i] - b[i] == diff) {
                i++;
            }
     
            // Increase the number of
            // operations by 1
            operations++;
        }
     
        // Print the number of
        // operations required
        Console.WriteLine(operations);
    }
     
    // Driver Code
    public static void Main (string[] args)
    {
        int []a = { 3, 7, 1, 4, 1, 2 };
        int []b = { 3, 7, 3, 6, 3, 2 };
        int size = a.Length;
     
        checkArray(a, b, size);
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation to find the
# minimum number of operations in
# which the array A can be converted
# to another array B
 
# Function to find the minimum
# number of operations in which
# array A can be converted to array B
def checkArray(a, b, n) :
 
    operations = 0;
    i = 0;
     
    # Loop to iterate over the array
    while (i < n) :
         
        # if both elements are equal
        # then move to next element
        if (a[i] - b[i] == 0) :
            i += 1;
            continue;
 
        # Calculate the difference
        # between two elements
        diff = a[i] - b[i];
        i += 1;
 
        # loop while the next pair of
        # elements have same difference
        while (i < n and a[i] - b[i] == diff) :
            i += 1;
 
        # Increase the number of
        # operations by 1
        operations += 1;
     
    # Print the number of
    # operations required
    print(operations);
 
# Driver Code
if __name__ == "__main__" :
 
    a = [ 3, 7, 1, 4, 1, 2 ];
    b = [ 3, 7, 3, 6, 3, 2 ];
    size = len(a);
 
    checkArray(a, b, size);
 
# This code is contributed by AnkitRai01

<script>
// javascript implementation to find the
// minimum number of operations in
// which the array A can be converted
// to another array B   
// Function to find the minimum
    // number of operations in which
    // array A can be converted to array B
    function checkArray(a , b , n) {
        var operations = 0;
        var i = 0;
 
        // Loop to iterate over the array
        while (i < n) {
 
            // if both elements are equal
            // then move to next element
            if (a[i] - b[i] == 0) {
                i++;
                continue;
            }
 
            // Calculate the difference
            // between two elements
            var diff = a[i] - b[i];
            i++;
 
            // loop while the next pair of
            // elements have same difference
            while (i < n && a[i] - b[i] == diff) {
                i++;
            }
 
            // Increase the number of
            // operations by 1
            operations++;
        }
 
        // Print the number of
        // operations required
        document.write(operations);
    }
 
    // Driver Code
     
        var a = [ 3, 7, 1, 4, 1, 2 ];
        var b = [ 3, 7, 3, 6, 3, 2 ];
        var size = a.length;
 
        checkArray(a, b, size);
 
// This code contributed by Rajput-Ji
</script>

Análisis de rendimiento: 

• Complejidad de tiempo: como en el enfoque anterior, solo hay un ciclo que toma el tiempo O (N) en el peor de los casos. Por lo tanto, la Complejidad del Tiempo será O(N) .
• Complejidad del espacio auxiliar: como en el enfoque anterior, no se utiliza espacio adicional. Por lo tanto, la complejidad del espacio auxiliar será O(1) .