Count numbers up to C that can be reduced to 0 by adding or subtracting A or B
Given three non-negative integers A, B, and C, the task is to count the numbers in the range [1, C] that can be reduced to 0 by adding or subtracting A or B.
Examples:
Input: A = 2, B = 4, C = 7
Output: 3
Explanation: The numbers from the range [1, 7] that can be reduced to 0 by given operations are:
- For element 2: The number can be modified as 2 â 2 = 0.
- For element 4: The number can be modified as 4 â 2 â 2 = 0.
- For element 6: The number can be modified as 6 â 4 â 2 = 0.
Therefore, the total count is 3.
Input: A = 2, B = 3, C = 5
Output: 5
Approach: The given problem can be solved based on the following observations:
- Consider X and Y number of addition or subtraction of A and B are performed respectively.
- After applying the operations on any number N, it becomes Ax + By. Therefore, by Extended Euclidean Algorithm, it can be said that there exist integer coefficients x and y such that Ax + By = GCD(A, B).
- Therefore, N must be a multiple of GCD(A, B), say G. Now the problem is reduced to finding the number of multiples of G which are in the range [1, C] which is floor (C / G).
Follow the below steps to solve the problem:
- Find the GCD of A and B and store it in a variable, say G.
- Now, the count of numbers over the range [1, C] is the multiples of G having values at most C which is given by floor(C/G).
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate GCD of the // two numbers a and b long long gcd( long long a, long long b) { // Base Case if (b == 0) return a; // Recursively find the GCD return gcd(b, a % b); } // Function to count the numbers up // to C that can be reduced to 0 by // adding or subtracting A or B void countDistinctNumbers( long long A, long long B, long long C) { // Stores GCD of A and B long long g = gcd(A, B); // Stores the count of multiples // of g in the range (0, C] long long count = C / g; // Print the result cout << count; } // Driver Code int main() { long long A = 2, B = 3, C = 5; countDistinctNumbers(A, B, C); return 0; } |
Java
// Java program for the above approach class GFG{ // Function to calculate GCD of the // two numbers a and b static long gcd( long a, long b) { // Base Case if (b == 0 ) return a; // Recursively find the GCD return gcd(b, a % b); } // Function to count the numbers up // to C that can be reduced to 0 by // adding or subtracting A or B static void countDistinctNumbers( long A, long B, long C) { // Stores GCD of A and B long g = gcd(A, B); // Stores the count of multiples // of g in the range (0, C] long count = C / g; // Print the result System.out.println(count); } // Driver Code public static void main(String[] args) { long A = 2 , B = 3 , C = 5 ; countDistinctNumbers(A, B, C); } } // This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach # Function to calculate GCD of the # two numbers a and b def gcd(a, b): # Base Case if (b = = 0 ): return a # Recursively find the GCD return gcd(b, a % b) # Function to count the numbers up # to C that can be reduced to 0 by # adding or subtracting A or B def countDistinctNumbers(A, B, C): # Stores GCD of A and B g = gcd(A, B) # Stores the count of multiples # of g in the range (0, C] count = C / / g # Print the result print (count) # Driver code A = 2 B = 3 C = 5 countDistinctNumbers(A, B, C) # This code is contributed by abhinavjain194 |
C#
// C# program for the above approach using System; class GFG{ // Function to calculate GCD of the // two numbers a and b static long gcd( long a, long b) { // Base Case if (b == 0) return a; // Recursively find the GCD return gcd(b, a % b); } // Function to count the numbers up // to C that can be reduced to 0 by // adding or subtracting A or B static void countDistinctNumbers( long A, long B, long C) { // Stores GCD of A and B long g = gcd(A, B); // Stores the count of multiples // of g in the range (0, C] long count = C / g; // Print the result Console.Write(count); } // Driver Code static void Main() { long A = 2, B = 3, C = 5; countDistinctNumbers(A, B, C); } } // This code is contributed by abhinavjain194 |
Javascript
<script> // Javascript program for the above approach // Function to calculate GCD of the // two numbers a and b function gcd(a, b) { // Base Case if (b == 0) return a; // Recursively find the GCD return gcd(b, a % b); } // Function to count the numbers up // to C that can be reduced to 0 by // adding or subtracting A or B function countDistinctNumbers(A, B, C) { // Stores GCD of A and B var g = gcd(A, B); // Stores the count of multiples // of g in the range (0, C] var count = C / g; // Print the result document.write(count); } // Driver Code var A = 2, B = 3, C = 5; countDistinctNumbers(A, B, C); // This code is contributed by ipg2016107. </script> |
Output:
5
Time Complexity: O(log(min(A, B)))
Auxiliary Space: O(1)