Given three positive integers N, A, and B, the task is to check if it is possible to obtain N by adding or subtracting A and B multiple times.
Examples:
Input: N = 11, A = 2, B = 5
Output: YES
Explanation: 11 = 5 + 5 + 5 – 2 -2Input: N = 11, A = 2, B = 4
Output: NO
Explanation: Not possible to obtain 11 from 2 and 4 only.
Approach:
Follow the steps below to solve the problem:
- The task is to check if it is possible to add or subtract A and B multiple times and obtain N as the end result.
- Hence, in terms of linear equation, it can be written as:
Ax + By = N,
where x and y represent the number of times A and B are added or subtracted. Negative x represents A is subtracted x times and similarly, negative y represents B is subtracted y times - Now, the aim is to find the integral solutions for the above equation. Here, it is quite valid to use Extended Euclid Algorithm which says that the solutions exist if and only if N % gcd(a, b) is 0.
Below is the implementation of the above approach:
C++
// C++ Program to check if // a number can be obtained // by repetitive addition // or subtraction of two numbers #include <bits/stdc++.h> using namespace std; // Function to check and return if // it is possible to obtain N by // repetitive addition or subtraction // of A and B bool isPossible(int N, int a, int b) { // Calculate GCD of A and B int g = __gcd(a, b); // Condition to check // if N can be obtained if (N % g == 0) return true; else return false; } // Driver Code int main() { int N = 11, a = 2; int b = 5; if (isPossible(N, a, b)) cout << "YES"; else cout << "NO"; } |
Java
// Java program to check if // a number can be obtained // by repetitive addition // or subtraction of two numbers class GFG{ // Recursive function to return // gcd of a and b public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to check and return if // it is possible to obtain N by // repetitive addition or subtraction // of A and B public static boolean isPossible(int N, int a, int b) { // Calculate GCD of A and B int g = gcd(a, b); // Condition to check // if N can be obtained if (N % g == 0) return true; else return false; } // Driver code public static void main(String[] args) { int N = 11, a = 2; int b = 5; if (isPossible(N, a, b)) System.out.print("YES"); else System.out.print("NO"); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to check if # a number can be obtained # by repetitive addition # or subtraction of two numbers # Recursive function to return # gcd of a and b def gcd(a, b): if (b == 0): return a return gcd(b, a % b) # Function to check and return if # it is possible to obtain N by # repetitive addition or subtraction # of A and B def isPossible(N, a, b): # Calculate GCD of A and B g = gcd(a, b) # Condition to check # if N can be obtained if (N % g == 0): return True else: return False # Driver code N = 11a = 2b = 5if (isPossible(N, a, b) != False): print("YES") else: print("NO") # This code is contributed by code_hunt |
C#
// C# program to check if // a number can be obtained // by repetitive addition // or subtraction of two numbers using System;class GFG{ // Recursive function to return // gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to check and return if // it is possible to obtain N by // repetitive addition or subtraction // of A and B static bool isPossible(int N, int a, int b) { // Calculate GCD of A and B int g = gcd(a, b); // Condition to check // if N can be obtained if (N % g == 0) return true; else return false; } // Driver codepublic static void Main(){ int N = 11, a = 2; int b = 5; if (isPossible(N, a, b)) Console.Write("YES"); else Console.Write("NO"); }}// This code is contributed by chitranayal |
Javascript
<script>// Javascript program to check if // a number can be obtained // by repetitive addition // or subtraction of two numbers // Recursive function to return // gcd of a and b function gcd(a, b){ if (b == 0) return a; return gcd(b, a % b); }// Function to check and return if // it is possible to obtain N by // repetitive addition or subtraction // of A and B function isPossible(N, a, b) { // Calculate GCD of A and B var g = gcd(a, b); // Condition to check // if N can be obtained if (N % g == 0) return true; else return false;}// Driver codevar N = 11, a = 2; var b = 5; if (isPossible(N, a, b)) document.write("YES");else document.write("NO"); // This code is contributed by Ankita saini </script> |
Output:
YES
Time Complexity: O(log(min(A, B))
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!
