Given two even numbers A, and B, the task is to find the minimum number of operations required to make both numbers equal if it is possible else print -1. In a single operation, the last digit of either number A or B can be added to itself i.e.,
- Either A = (A + (A % 10))
- or B = (B + (B % 10))
Examples:
Input: A = 4, B = 12
Output: -1
Explanation: We can not make 4 and 12 equal so answer is -1.Input: A = 2 , B = 8
Output: 2.
Explanation: 2 -> 4 -> 8, so minimum 2 steps is required to make them equal.Input: A = 6, B = 12 .
Output: 1.
Explanation: 6 + 6 = 12 and 12 so by 1 step we can make elements equal.
Approach: To solve the problem follow the below observation:
Observation:
- There is an observation that if last digit is 0 then we can not increase that number . So if last digit of the either number is 0 then the numbers should be equal else answer is -1 .
- The last digit of the even numbers contain 2, 4, 6, 8 . We will see the change if last digit is added 2->4->8->6->2 ->4->8->6->2 . . .
- So the pattern is repeating and in every cycle the increase in the number is 2+4+8+6=20 .
- Now if two number will be equal then last digit of the numbers must be equal .
- Now we can make last digit of the two numbers either equal to 2 or 4 or 6 or 8 and check if the difference between two numbers modulo 20 is equal to 0 or not .
- If modulo is 0 then possible to make them equal else not because if difference%20 = 0 then we can increase the smaller number by any multiple of 20 to make it equal to greater even number .
- To find the minimum number of steps we will make last digit of both numbers equal to the last digit of the greater number and find the number of steps to make them equal .
Follow the steps to solve the problem:
- If last digit of any number is 0.
- if the numbers are the same then the answer is 0.
- else the number is -1 as the numbers can’t be made equal.
- Store the minimum and maximum of A and B in different variables.
- Make the last digit of the smaller number equal to the greater number and count the steps.
- If the difference is not a multiple of 20 return -1 as the answer.
- Calculate the steps in the loop by using formula (((c – d) / 20) * 4).
- Return the sum of steps and loopSteps as the final answer.
Below is the implementation of the above approach :
C++14
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to count minimum stepsint ispossible(int A, int B){ // If any number has 0 as last Digit if (A % 10 == 0 || B % 10 == 0) { // If the number are not equal // they can never be made equal if (A != B) { return -1; } else { return 0; } } // Storing the minimum of A and B int c = min(A, B); // Storing the maximum of A and B int d = max(A, B); // Steps to make the last digit equal int steps = 0; // To make the last digit same int lastDigit = d % 10; while (c % 10 != lastDigit) { c += (c % 10); steps++; } if ((d - c) % 20 != 0) { // If cycle is not formed // after same last digit return -1; } // Steps in the loop int loopSteps = (((d - c) / 20) * 4); int ans = steps + loopSteps; return ans;}// Driver Codeint main(){ // Given Inputs int A = 2, B = 8; // Function Call cout << ispossible(A, B); return 0;} |
Java
// Java code for the above approachimport java.io.*;class GFG { // Driver Code public static void main(String[] args) { // Given Inputs int A = 2, B = 8; // Function Call System.out.println(ispossible(A, B)); } // Function to count minimum steps static int ispossible(int A, int B) { // If any number has 0 as last Digit if (A % 10 == 0 || B % 10 == 0) { // If the number are not equal // they can never be made equal if (A != B) { return -1; } else { return 0; } } // Storing the minimum of A and B int c = min(A, B); // Storing the maximum of A and B int d = max(A, B); // Steps to make the last digit equal int steps = 0; // To make the last digit same int lastDigit = d % 10; while (c % 10 != lastDigit) { c += (c % 10); steps++; } if ((d - c) % 20 != 0) { // If cycle is not formed // after same last digit return -1; } // Steps in the loop int loopSteps = (((d - c) / 20) * 4); int ans = steps + loopSteps; return ans; } // function to find maximum element static int max(int a, int b) { if (a > b) return a; return b; } // function to find minimum element static int min(int a, int b) { if (a < b) return a; return b; }}// This code is contributed by ajaymakvana. |
Python3
# Python3 code for the above approach# Function to count minimum stepsdef ispossible(A, B) : # If any number has 0 as last Digit if (A % 10 == 0 or B % 10 == 0) : # If the number are not equal # they can never be made equal if (A != B) : return -1; else : return 0; # Storing the minimum of A and B c = min(A, B); # Storing the maximum of A and B d = max(A, B); # Steps to make the last digit equal steps = 0; # To make the last digit same lastDigit = d % 10; while (c % 10 != lastDigit) : c += (c % 10); steps += 1; if ((d - c) % 20 != 0) : # If cycle is not formed # after same last digit return -1; # Steps in the loop loopSteps = (((d - c) / 20) * 4); ans = steps + loopSteps; return ans;# Driver Codeif __name__ == "__main__" : # Given Inputs A = 2; B = 8; # Function Call print(ispossible(A, B)); # This code is contributed by AnkThon |
C#
// C# program for above approachusing System;class GFG{// Function to count minimum steps static int ispossible(int A, int B) { // If any number has 0 as last Digit if (A % 10 == 0 || B % 10 == 0) { // If the number are not equal // they can never be made equal if (A != B) { return -1; } else { return 0; } } // Storing the minimum of A and B int c = min(A, B); // Storing the maximum of A and B int d = max(A, B); // Steps to make the last digit equal int steps = 0; // To make the last digit same int lastDigit = d % 10; while (c % 10 != lastDigit) { c += (c % 10); steps++; } if ((d - c) % 20 != 0) { // If cycle is not formed // after same last digit return -1; } // Steps in the loop int loopSteps = (((d - c) / 20) * 4); int ans = steps + loopSteps; return ans; } // function to find maximum element static int max(int a, int b) { if (a > b) return a; return b; } // function to find minimum element static int min(int a, int b) { if (a < b) return a; return b; }// Driver Codepublic static void Main(){ // Given Inputs int A = 2, B = 8; // Function Call Console.Write(ispossible(A, B));}}// This code is contributed by code_hunt. |
Javascript
<script>// JavaScript code for the above approach// Function to count minimum steps function ispossible(A, B) { // If any number has 0 as last Digit if (A % 10 == 0 || B % 10 == 0) { // If the number are not equal // they can never be made equal if (A != B) { return -1; } else { return 0; } } // Storing the minimum of A and B let c = min(A, B); // Storing the maximum of A and B let d = max(A, B); // Steps to make the last digit equal let steps = 0; // To make the last digit same let lastDigit = d % 10; while (c % 10 != lastDigit) { c += (c % 10); steps++; } if ((d - c) % 20 != 0) { // If cycle is not formed // after same last digit return -1; } // Steps in the loop let loopSteps = (((d - c) / 20) * 4); let ans = steps + loopSteps; return ans; } // function to find maximum element function max(a, b) { if (a > b) return a; return b; } // function to find minimum element function min(a, b) { if (a < b) return a; return b; }// Driver Code // Given Inputs let A = 2, B = 8; // Function Call document.write(ispossible(A, B)); // This code is contributed by sanjoy_62.</script> |
Output
2
Time complexity: O(1), as we will perform at most 3 steps in the while loop.
Auxiliary Space: O(1), since we did not use any extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
