Operaciones mínimas para igualar dos números

Dados dos números n y m , la tarea es encontrar el número mínimo de operaciones requeridas para hacerlos iguales si se pueden realizar las siguientes operaciones sobre ellos. 
 

• Durante la primera operación, cualquiera de los dos números puede incrementarse en uno.
• Durante la segunda operación, cualquiera de los dos números puede incrementarse en dos.
• Durante la tercera operación, cualquiera de los dos números puede incrementarse en tres y así sucesivamente.

Ejemplos: 
 

Input : n = 1, m = 3
Output : 3
Explanation: 
Add 1 to n; n = 2
Add 2 to m; m = 5
Add 3 to n; n = 5
Both n and m are equal now
N of operations = 3

Input : n = 30, m = 20
Output : 4

Enfoque: 
El enfoque utilizado para resolver el problema es la suma de N términos en un AP. 
esta dada por la formula 
 

S(n) = (n*(n+1))/2

Entonces, la tarea es encontrar la diferencia entre esos dos números y ver si la diferencia se puede lograr agregando los primeros n elementos. Por lo tanto, 
 

S(n) = max(m,n) - min(m,n)

Al sustituir este valor de suma en la primera ecuación; 
obtenemos el número de elementos n dado por 
 

n=(-1+sqrt(1+8*S(n)))/2

Si este n es un entero perfecto, entonces es nuestra respuesta final. 
De lo contrario, incrementamos nuestro valor objetivo para alcanzar en 1 y continuamos. 
 

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum no of operations
int minOperations(int n, int m)
{
    int a = 0, k = 1;
 
    // find the maximum of two and store it in p
    int p = max(n, m);
 
    // increase it until it is achievable from
    // given n and m
    while (n != m) {
 
        // Here value added to n and m will be
        // S(n)=p-n+p-m;
        // check whether integer value of n exist
        // by the formula
        // n=(-1+sqrt(1+8*S(n)))/2
        float s = (float)(p - n + p - m);
        float q = (-1 + sqrt(8 * s + 1)) / 2;
        if (q - floor(q) == 0) {
            a = q;
            n = m;
        }
 
        p = p + 1;
    }
    return a;
}
 
// Driver code
int main()
{
    int n = 1, m = 3;
 
    // Function calling
    cout << minOperations(n, m);
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
 
// Function to find the minimum no of operations
static int minOperations(int n, int m)
{
    int a = 0, k = 1;
 
    // find the maximum of two and store it in p
    int p = Math.max(n, m);
 
    // increase it until it is achievable from
    // given n and m
    while (n != m)
    {
 
        // Here value added to n and m will be
        // S(n)=p-n+p-m;
        // check whether integer value of n exist
        // by the formula
        // n=(-1+Math.sqrt(1+8*S(n)))/2
        float s = (float)(p - n + p - m);
        float q = (float) ((-1 + Math.sqrt(8 * s + 1)) / 2);
        if (q - Math.floor(q) == 0)
        {
            a = (int) q;
            n = m;
        }
 
        p = p + 1;
    }
    return a;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 1, m = 3;
 
    // Function calling
    System.out.print(minOperations(n, m));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of
# the above approach
from math import sqrt, floor
 
# Function to find the minimum
# no. of operations
def minOperations( n, m) :
 
    a = 0; k = 1;
 
    # find the maximum of two and
    # store it in p
    p = max(n, m);
 
    # increase it until it is achievable
    # from given n and m
    while (n != m) :
 
        # Here value added to n and m will be
        # S(n)=p-n+p-m;
        # check whether integer value of n 
        # exist by the formula
        # n=(-1+sqrt(1+8*S(n)))/2
        s = float(p - n + p - m);
        q = (-1 + sqrt(8 * s + 1)) / 2;
        if (q - floor(q) == 0) :
            a = q;
            n = m;
 
        p = p + 1;
 
    return a;
 
# Driver code
if __name__ == "__main__" :
 
    n = 1; m = 3;
 
    # Function calling
    print(minOperations(n, m));
 
# This code is contributed by AnkitRai01

// C# implementation of the above approach
using System;
 
class GFG
{
     
    // Function to find the minimum no of operations
    static int minOperations(int n, int m)
    {
        int a = 0, k = 1;
     
        // find the maximum of two and store it in p
        int p = Math.Max(n, m);
     
        // increase it until it is achievable from
        // given n and m
        while (n != m)
        {
     
            // Here value added to n and m will be
            // S(n)=p-n+p-m;
            // check whether integer value of n exist
            // by the formula
            // n=(-1+Math.sqrt(1+8*S(n)))/2
            float s = (float)(p - n + p - m);
            float q = (float) ((-1 + Math.Sqrt(8 * s + 1)) / 2);
            if (q - Math.Floor(q) == 0)
            {
                a = (int) q;
                n = m;
            }
     
            p = p + 1;
        }
        return a;
    }
     
    // Driver code
    public static void Main()
    {
        int n = 1, m = 3;
     
        // Function calling
        Console.Write(minOperations(n, m));
    }
}
 
// This code is contributed by AnkitRai01

<script>
// javascript implementation of the above approach
 
    // Function to find the minimum no of operations
    function minOperations(n , m) {
        var a = 0, k = 1;
 
        // find the maximum of two and store it in p
        var p = Math.max(n, m);
 
        // increase it until it is achievable from
        // given n and m
        while (n != m)
        {
 
            // Here value added to n and m will be
            // S(n)=p-n+p-m;
            // check whether integer value of n exist
            // by the formula
            // n=(-1+Math.sqrt(1+8*S(n)))/2
            var s =  (p - n + p - m);
            var q =  ((-1 + Math.sqrt(8 * s + 1)) / 2);
            if (q - Math.floor(q) == 0)
            {
                a = parseInt( q);
                n = m;
            }
 
            p = p + 1;
        }
        return a;
    }
 
    // Driver code
        var n = 1, m = 3;
 
        // Function calling
        document.write(minOperations(n, m));
 
// This code is contributed by Rajput-Ji
</script>

3

Complejidad de tiempo: O(sqrt(n))

Espacio Auxiliar: O(1)