Check if there is any pair in a given range with GCD is divisible by k
Given a range, we need to check if is their any pairs in the segment whose GCD is divisible by k.
Examples:
Input : l=4, r=6, k=2 Output : YES There are two numbers 4 and 6 whose GCD is 2 which is divisible by 2. Input : l=3 r=5 k=4 Output : NO There is no such pair whose gcd is divisible by 5.
Basically we need to count such numbers in range l to r such that they are divisible by k. Because if we choose any such two numbers then their gcd is also a multiple of k. Now if count of such numbers is greater than one then we can form pair, otherwise it’s impossible to form a pair (x, y) such that gcd(x, y) is divisible by k.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h> using namespace std; // function to count such possible numbers bool Check_is_possible( int l, int r, int k) { int count = 0; for ( int i = l; i <= r; i++) { // if i is divisible by k if (i % k == 0) count++; } // if count of such numbers // is greater than one return (count > 1); } // Driver code int main() { int l = 4, r = 12; int k = 5; if (Check_is_possible(l, r, k)) cout << "YES\n" ; else cout << "NO\n" ; return 0; } |
Java
// function to count such // possible numbers class GFG { public boolean Check_is_possible( int l, int r, int k) { int count = 0 ; for ( int i = l; i <= r; i++) { // if i is divisible by k if (i % k == 0 ) { count++; } } // if count of such numbers // is greater than one return (count > 1 ); } public static void main(String[] args) { GFG g = new GFG(); int l = 4 , r = 12 ; int k = 5 ; if (g.Check_is_possible(l, r, k)) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } // This code is contributed by RAJPUT-JI |
Python3
# function to count such possible numbers def Check_is_possible(l, r, k): count = 0 ; for i in range (l, r + 1 ): # if i is divisible by k if (i % k = = 0 ): count + = 1 ; # if count of such numbers # is greater than one return (count > 1 ); # Driver code l = 4 ; r = 12 ; k = 5 ; if (Check_is_possible(l, r, k)): print ( "YES" ); else : print ( "NO" ); # This code is contributed by mits |
C#
using System; // function to count such // possible numbers class GFG { public bool Check_is_possible( int l, int r, int k) { int count = 0; for ( int i = l; i <= r; i++) { // if i is divisible by k if (i % k == 0) count++; } // if count of such numbers // is greater than one return (count > 1); } // Driver code public static void Main() { GFG g = new GFG(); int l = 4, r = 12; int k = 5; if (g.Check_is_possible(l, r, k)) Console.WriteLine( "YES\n" ); else Console.WriteLine( "NO\n" ); } } // This code is contributed // by Soumik |
PHP
<?php // function to count such possible numbers function Check_is_possible( $l , $r , $k ) { $count = 0; for ( $i = $l ; $i <= $r ; $i ++) { // if i is divisible by k if ( $i % $k == 0) $count ++; } // if count of such numbers // is greater than one return ( $count > 1); } // Driver code $l = 4; $r = 12; $k = 5; if (Check_is_possible( $l , $r , $k )) echo "YES\n" ; else echo "NO\n" ; // This code is contributed // by Akanksha Rai ?> |
Javascript
<script> // function to count such // possible numbers function Check_is_possible(l , r , k) { var count = 0; for (i = l; i <= r; i++) { // if i is divisible by k if (i % k == 0) { count++; } } // if count of such numbers // is greater than one return (count > 1); } var l = 4, r = 12; var k = 5; if (Check_is_possible(l, r, k)) { document.write( "YES" ); } else { document.write( "NO" ); } // This code is contributed by todaysgaurav </script> |
Output:
YES
Time Complexity: O(r – l + 1)
Auxiliary Space: O(1), since no extra space has been taken.
An efficient solution is based on the efficient approach discussed here.
C++
// C++ program to count the numbers divisible // by k in a given range #include <bits/stdc++.h> using namespace std; // Returns count of numbers in [l r] that // are divisible by k. int Check_is_possible( int l, int r, int k) { int div_count = (r / k) - (l / k); // Add 1 explicitly as l is divisible by k if (l % k == 0) div_count++; // l is not divisible by k return (div_count > 1); } // Driver Code int main() { int l = 30, r = 70, k = 10; if (Check_is_possible(l, r, k)) cout << "YES\n" ; else cout << "NO\n" ; return 0; } |
Java
// Java program to count the numbers divisible // by k in a given range class GFG { // Returns count of numbers in [l r] that // are divisible by k. static boolean Check_is_possible( int l, int r, int k) { int div_count = (r / k) - (l / k); // Add 1 explicitly as l is divisible by k if (l % k == 0 ) { div_count++; } // l is not divisible by k return (div_count > 1 ); } // Driver Code public static void main(String[] args) { int l = 30 , r = 70 , k = 10 ; if (Check_is_possible(l, r, k)) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } // This code is contributed by RAJPUT-JI |
Python3
# Python3 program to count the numbers # divisible by k in a given range # Returns count of numbers in [l r] # that are divisible by k. def Check_is_possible(l, r, k): div_count = (r / / k) - (l / / k) # Add 1 explicitly as l is # divisible by k if l % k = = 0 : div_count + = 1 # l is not divisible by k return div_count > 1 # Driver Code if __name__ = = "__main__" : l, r, k = 30 , 70 , 10 if Check_is_possible(l, r, k) = = True : print ( "YES" ) else : print ( "NO" ) # This code is contributed # by Rituraj Jain |
C#
// C# program to count the numbers divisible // by k in a given range using System; public class GFG { // Returns count of numbers in [l r] that // are divisible by k. static bool Check_is_possible( int l, int r, int k) { int div_count = (r / k) - (l / k); // Add 1 explicitly as l is divisible by k if (l % k == 0) { div_count++; } // l is not divisible by k return (div_count > 1); } // Driver Code public static void Main() { int l = 30, r = 70, k = 10; if (Check_is_possible(l, r, k)) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } // This code is contributed by RAJPUT-JI |
PHP
<?php // PHP program to count the numbers // divisible by k in a given range // Returns count of numbers in [l r] // that are divisible by k. function Check_is_possible( $l , $r , $k ) { $div_count = (int)( $r / $k ) - (int)( $l / $k ); // Add 1 explicitly as l // is divisible by k if ( $l % $k == 0) $div_count ++; // l is not divisible by k return ( $div_count > 1); } // Driver Code $l = 30; $r = 70; $k = 10; if (Check_is_possible( $l , $r , $k )) echo "YES\n" ; else echo "NO\n" ; // This Code is contributed by mits ?> |
Javascript
<script> // Javascript program to count the numbers divisible // by k in a given range // Returns count of numbers in [l r] that // are divisible by k. function Check_is_possible(l , r , k) { var div_count = (r / k) - (l / k); // Add 1 explicitly as l is divisible by k if (l % k == 0) { div_count++; } // l is not divisible by k return (div_count > 1); } // Driver Code var l = 30, r = 70, k = 10; if (Check_is_possible(l, r, k)) { document.write( "YES" ); } else { document.write( "NO" ); } // This code contributed by Rajput-Ji </script> |
Output:
YES
Time Complexity: O(1)
Auxiliary Space: O(1)