Count integers in the range [A, B] that are not divisible by C and D
source link: https://www.geeksforgeeks.org/count-integers-in-the-range-a-b-that-are-not-divisible-by-c-and-d/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
- Difficulty Level : Basic
- Last Updated : 06 Nov, 2019
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:
- Python3
filter_none
edit
close
play_arrow
link
brightness_4
code
// 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; } 28
Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK