Given three integers X, Y, and Z. the task is to find the minimum distance between any two multiples of the given integers.
Note: Common multiples are not considered.
Examples:
Input: X = 5, Y = 2, Z = 3
Output: 1
Explanation: The multiples if arranged in sorted order are 0, 2, 3, 4, 5, 6, 8. . .
Out of which the minimum possible difference is 1 between 2 and 3.Input: X = 3, Y = 6, Z = 12
Output: 3
Approach: To solve the problem follow the below idea:
- Difference between the multiples of two numbers A and B is actually the multiples of GCD(A, B).
- To calculate the minimum possible difference between the multiple of any two numbers, calculate the GCD of those two numbers.
Follow the given steps to solve the problem:
- Calculate the greatest common divisor(GCD) between every pair of numbers.
- Return the minimum value by comparing the values calculated in the above step.
Below is the implementation for the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the minimum// possible difference between any two numbersint minimumdifference(int H1, int H2, int H3){ int ans = 0; int d1, d2, d3; // Calculating GCD between different // pairs of numbers d3 = __gcd(H1, H3); d1 = __gcd(H1, H2); d2 = __gcd(H2, H3); // Taking minimum of all GCD's ans = min(d1, d2); ans = min(d3, ans); return ans;}// Driver codeint main(){ int X = 5, Y = 2, Z = 3; // Function call cout << minimumdifference(X, Y, Z); return 0;} |
Java
// JAVA program for the above approachimport java.io.*;class GFG { // Function to calculate gcd of two numbers public static int gcd(int a, int b) { return b==0 ? a : gcd(b, a%b); } // Function to calculate the minimum // possible difference between any two numbers static int minimumdifference(int H1,int H2,int H3) { int ans=0; int d1, d2, d3; // Calculating GCD between different // pairs of numbers d3 = gcd(H1, H3); d1 = gcd(H1, H2); d2 = gcd(H2, H3); // Taking minimum of all GCD's ans = Math.min(d1, d2); ans = Math.min(d3, ans); return ans; } // Driver code public static void main (String[] args) { int X = 5, Y = 2, Z = 3; // function call System.out.println(minimumdifference(X, Y, Z)); }}// This code is written by Ujjwal Kumar Bhardwaj |
Python3
# python 3 code to implement the above approachdef __gcd(x, y): while(y): x, y = y, x % y return abs(x) # Function to calculate the minimum# possible difference between any two numbersdef minimumdifference(H1, H2, H3) : ans = 0 d1,d2,d3 = 0,0,0 # Calculating GCD between different # pairs of numbers d3 = __gcd(H1, H3) d1 = __gcd(H1, H2) d2 = __gcd(H2, H3) # Taking minimum of all GCD's ans = min(d1, d2) ans = min(d3, ans) return ans# Driver Codeif __name__ == "__main__" : X,Y,Z = 5,2,3 # Function call print(minimumdifference(X, Y, Z))#this code is contributed by aditya942003patil |
C#
// C# program for above approach:using System;class GFG { // Function to calculate gcd of two numbers public static int gcd(int a, int b) { return b==0 ? a : gcd(b, a%b); } // Function to calculate the minimum // possible difference between any two numbers static int minimumdifference(int H1,int H2,int H3) { int ans=0; int d1, d2, d3; // Calculating GCD between different // pairs of numbers d3 = gcd(H1, H3); d1 = gcd(H1, H2); d2 = gcd(H2, H3); // Taking minimum of all GCD's ans = Math.Min(d1, d2); ans = Math.Min(d3, ans); return ans; } // Driver Codepublic static void Main(){ int X = 5, Y = 2, Z = 3; // function call Console.Write(minimumdifference(X, Y, Z));}}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript program for above approach // Function for __gcd const __gcd = (a, b) => { if (!b) return a; return __gcd(b, a % b); } // Function to calculate the minimum // possible difference between any two numbers const minimumdifference = (H1, H2, H3) => { let ans = 0; let d1, d2, d3; // Calculating GCD between different // pairs of numbers d3 = __gcd(H1, H3); d1 = __gcd(H1, H2); d2 = __gcd(H2, H3); // Taking minimum of all GCD's ans = Math.min(d1, d2); ans = Math.min(d3, ans); return ans; } // Driver code let X = 5, Y = 2, Z = 3; // Function call document.write(minimumdifference(X, Y, Z));// This code is contributed by rakeshsahni</script> |
Output
1
Time Complexity: O(max(logX, logY, logZ))
Auxiliary Space: O(1)
Share your thoughts in the comments
