Given two integers p and q, the task is to find the smallest number K such that K % p = 0 and q % K = 0. If no such K is possible then print -1.
Examples:
Input: p = 2, q = 8
Output: 2
2 % 2 = 0 and 8 % 2 = 0
Input: p = 5, q = 14
Output: -1
Approach: In order for K to be possible, q must be divisible by p.
- If q % p = 0 then print p
- Else print -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the minimum // value K such that K % p = 0 // and q % k = 0 int getMinVal( int p, int q) { // If K is possible if (q % p == 0) return p; // No such K is possible return -1; } // Driver code int main() { int p = 24, q = 48; cout << getMinVal(p, q); return 0; } |
Java
// Java implementation of the approach import java.io.*; class GFG { // Function to return the minimum // value K such that K % p = 0 // and q % k = 0 static int getMinVal( int p, int q) { // If K is possible if (q % p == 0 ) return p; // No such K is possible return - 1 ; } // Driver code public static void main (String[] args) { int p = 24 , q = 48 ; System.out.println(getMinVal(p, q)); } } // This code is contributed by jit_t. |
Python3
# Python3 implementation of the approach # Function to return the minimum # value K such that K % p = 0 # and q % k = 0 def getMinVal(p, q): # If K is possible if q % p = = 0 : return p # No such K is possible return - 1 # Driver code p = 24 ; q = 48 print (getMinVal(p, q)) # This code is contributed # by Shrikant13 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the minimum // value K such that K % p = 0 // and q % k = 0 static int getMinVal( int p, int q) { // If K is possible if (q % p == 0) return p; // No such K is possible return -1; } // Driver code public static void Main () { int p = 24, q = 48; Console.WriteLine(getMinVal(p, q)); } } // This code is contributed // by Code_Mech. |
PHP
<?php // PHP implementation of the approach // Function to return the minimum // value K such that K % p = 0 // and q % k = 0 function getMinVal( $p , $q ) { // If K is possible if ( $q % $p == 0) return $p ; // No such K is possible return -1; } // Driver code $p = 24; $q = 48; echo getMinVal( $p , $q ); // This code is contributed by ajit. ?> |
Javascript
<script> // Javascript implementation of the above approach // Function to return the minimum // value K such that K % p = 0 // and q % k = 0 function getMinVal(p, q) { // If K is possible if (q % p == 0) return p; // No such K is possible return -1; } // driver program let p = 24, q = 48; document.write(getMinVal(p, q)); </script> |
24
Time Complexity: O(1)
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!