Given four integers A, B, C and D. The task is to find the count of integers in the range [A, B] that are not divisible by C and D .
Examples:
Input: A = 4, B = 9, C = 2, D = 3
Output: 2
5 and 7 are such integers.Input: A = 10, B = 50, C = 4, D = 6
Output: 28
Approach: First include all the integers in the range in the required answer i.e. B – A + 1. Then remove all the numbers which are divisible by C and D and finally add all the numbers which are divisible by both C and D.
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 count of // integers from the range [a, b] that // are not divisible by c and d int countNums( int a, int b, int c, int d) { // Numbers which are divisible by c int x = b / c - (a - 1) / c; // Numbers which are divisible by d int y = b / d - (a - 1) / d; // Find lowest common factor of c and d int k = (c * d) / __gcd(c, d); // Numbers which are divisible by both c and d int z = b / k - (a - 1) / k; // Return the required answer return b - a + 1 - x - y + z; } // Driver code int main() { int a = 10, b = 50, c = 4, d = 6; cout << countNums(a, b, c, d); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the count of // integers from the range [a, b] that // are not divisible by c and d static int countNums( int a, int b, int c, int d) { // Numbers which are divisible by c int x = b / c - (a - 1 ) / c; // Numbers which are divisible by d int y = b / d - (a - 1 ) / d; // Find lowest common factor of c and d int k = (c * d) / __gcd(c, d); // Numbers which are divisible by both c and d int z = b / k - (a - 1 ) / k; // Return the required answer return b - a + 1 - x - y + z; } static int __gcd( int a, int b) { if (b == 0 ) return a; return __gcd(b, a % b); } // Driver code public static void main(String []args) { int a = 10 , b = 50 , c = 4 , d = 6 ; System.out.println(countNums(a, b, c, d)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach from math import gcd # Function to return the count of # integers from the range [a, b] that # are not divisible by c and d def countNums(a, b, c, d) : # Numbers which are divisible by c x = b / / c - (a - 1 ) / / c; # Numbers which are divisible by d y = b / / d - (a - 1 ) / / d; # Find lowest common factor of c and d k = (c * d) / / gcd(c, d); # Numbers which are divisible # by both c and d z = b / / k - (a - 1 ) / / k; # Return the required answer return (b - a + 1 - x - y + z); # Driver code if __name__ = = "__main__" : a = 10 ; b = 50 ; c = 4 ; d = 6 ; print (countNums(a, b, c, d)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the count of // integers from the range [a, b] that // are not divisible by c and d static int countNums( int a, int b, int c, int d) { // Numbers which are divisible by c int x = b / c - (a - 1) / c; // Numbers which are divisible by d int y = b / d - (a - 1) / d; // Find lowest common factor of c and d int k = (c * d) / __gcd(c, d); // Numbers which are divisible by both c and d int z = b / k - (a - 1) / k; // Return the required answer return b - a + 1 - x - y + z; } static int __gcd( int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Driver code public static void Main(String []args) { int a = 10, b = 50, c = 4, d = 6; Console.WriteLine(countNums(a, b, c, d)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of the approach // Function to return the count of // integers from the range [a, b] that // are not divisible by c and d function countNums(a, b, c, d) { // Numbers which are divisible by c let x = parseInt(b / c) - parseInt((a - 1) / c); // Numbers which are divisible by d let y = parseInt(b / d) - parseInt((a - 1) / d); // Find lowest common factor of c and d let k = parseInt((c * d) / __gcd(c, d)); // Numbers which are divisible by both c and d let z = parseInt(b / k) - parseInt((a - 1) / k); // Return the required answer return b - a + 1 - x - y + z; } function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); } // Driver code let a = 10, b = 50, c = 4, d = 6; document.write(countNums(a, b, c, d)); </script> |
28
Time Complexity: O(log(min(c, d)), where c and d are the given inputs.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!