Minimum operations to make two numbers equal
Given two numbers n and m, the task is to find the minimum number of operations required to make them equal if the following operations can be performed on them.
- During the first operation, any of the two numbers can be increased by one.
- During the second operation, any of the two numbers can be increased by two.
- During the third operation, any of the two numbers can be increased by three and so on.
Examples:
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
Approach:
The approach used to solve the problem is the sum of N terms in an AP.
It is given by the formula
S(n) = (n*(n+1))/2
So, the task is to find the difference between those two numbers and see if the difference can be achieved by adding first n elements. Therefore,
S(n) = max(m,n) - min(m,n)
On substituting this value of sum in the first equation;
we get the number of elements n given by
n=(-1+sqrt(1+8*S(n)))/2
If this n is a perfect integer, then it is our final answer.
Else, we increment our target value to reach by 1 and continue.
Below is the implementation of the above approach:
C++
// 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
// 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
# 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#
// 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 |
Javascript
<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
Time Complexity: O(sqrt(n))
Auxiliary Space: O(1)
Contact Us