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 numbersbool 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 codeint 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 numbersdef 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 codel = 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 numbersfunction 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 Codeint 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 rangeclass 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)
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!