Given three integers A, B and C. You can add or subtract A, B, or 0 any number of times to form new values in the range 0 < final_value ? C. The task is to find the count of such distinct final values possible.
Examples :
Input : A = 2, B = 3, C = 10
Output:10
Possible values are :
0 + 3 – 2 =1
0 + 2 = 2
0 + 3 = 3
2 + 2 = 4
2 + 3 = 5
3 + 3 = 6
3+2+2=7
2+2+2+2=8
2+2+2+3=9
3+3+2+2=10Input : A = 10, B = 2, C = 10
Output: 5
Approach: The idea is to use the GCD g of A and B.
The above approach works Because every distinct possible value is xA+yB
- If A can be written as g×a, B can be written as g×b
- Then, A required final value can be written as xAg+yBg = (x*g*a + y*g*b) = g*(xa+yb)
- Since the maximum value possible is C, therefore C = g*(xa+yb).
- Hence count of possible such values = C/g, which is the required answer.
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 gcdint gcd(int A, int B){ if (B == 0) return A; else return gcd(B, A % B);}// Function to find number of possible final valuesint getDistinctValues(int A, int B, int C){ // Find the gcd of two numbers int g = gcd(A, B); // Calculate number of distinct values int num_values = C / g; // Return values return num_values;}// Driver Codeint main(){ int A = 2; int B = 3; int C = 10; cout << (getDistinctValues(A, B, C)); return 0;}// This code is contributed by subhammahato348 |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to calculate gcd static int gcd(int A, int B) { if (B == 0) return A; else return gcd(B, A % B); } // Function to find number of possible final values static int getDistinctValues(int A, int B, int C) { // Find the gcd of two numbers int g = gcd(A, B); // Calculate number of distinct values int num_values = C / g; // Return values return num_values; } // Driver Code public static void main(String[] args) { int A = 2; int B = 3; int C = 10; System.out.println(getDistinctValues(A, B, C)); }} |
Python3
# Python program for the above approach# Function to calculate gcddef gcd(A, B) : if (B == 0) : return A; else : return gcd(B, A % B);# Function to find number of possible final valuesdef getDistinctValues(A, B, C) : # Find the gcd of two numbers g = gcd(A, B); # Calculate number of distinct values num_values = C / g; # Return values return int(num_values);# Driver CodeA = 2;B = 3;C = 10;print(getDistinctValues(A, B, C));# This code is contributed by target_2. |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate gcd static int gcd(int A, int B) { if (B == 0) return A; else return gcd(B, A % B); } // Function to find number of possible final values static int getDistinctValues(int A, int B, int C) { // Find the gcd of two numbers int g = gcd(A, B); // Calculate number of distinct values int num_values = C / g; // Return values return num_values; } // Driver code static void Main() { int A = 2; int B = 3; int C = 10; Console.Write(getDistinctValues(A, B, C)); }}// This code is contributed by sanjoy_62. |
Javascript
<script>// JavaScript program for the above approach // Function to calculate gcd function gcd(A, B) { if (B == 0) return A; else return gcd(B, A % B); } // Function to find number of possible final values function getDistinctValues(A, B, C) { // Find the gcd of two numbers let g = gcd(A, B); // Calculate number of distinct values let num_values = C / g; // Return values return num_values; } // Driver Code let A = 2; let B = 3; let C = 10; document.write(getDistinctValues(A, B, C));</script> |
Output
10
Time Complexity : O(log(min(A, B))
Auxiliary Space: O(1)
Take a part in the ongoing discussion
