Given N types of money denomination in a country as an array arr[]. A person and the shopkeeper can choose notes of each denomination any number of times. The task is to check whether the exchange is possible when the person wants to buy a product worth P from the shop.
Examples:
Input: arr[] = {6, 9}, P = 3
Output: Yes
The person can pay 9 and get 6 in return.
Input: arr[] = {6, 9}, P = 4
Output: No
Approach: In order for the exchange to be possible, P must be divisible by the GCD of all the denominations. So, find the gcd of the array elements and check whether P is divisible by it or not.
Below is the implementation of the approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if// the exchange is possiblebool isPossible(int arr[], int n, int p){ // Find the GCD of the array elements int gcd = 0; for (int i = 0; i < n; i++) gcd = __gcd(gcd, arr[i]); // If the exchange is possible if (p % gcd == 0) return true; return false;}// Driver codeint main(){ int arr[] = { 6, 9 }; int n = sizeof(arr) / sizeof(int); int p = 3; if (isPossible(arr, n, p)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approach 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 that returns true if // the exchange is possible static boolean isPossible(int []arr, int n, int p) { // Find the GCD of the array elements int gcd = 0; for (int i = 0; i < n; i++) gcd = __gcd(gcd, arr[i]); // If the exchange is possible if (p % gcd == 0) return true; return false; } // Driver code public static void main (String[] args) { int arr[] = { 6, 9 }; int n = arr.length; int p = 3; if (isPossible(arr, n, p)) System.out.println("Yes"); else System.out.println("No"); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach from math import gcd as __gcd# Function that returns true if # the exchange is possible def isPossible(arr, n, p) : # Find the GCD of the array elements gcd = 0; for i in range(n) : gcd = __gcd(gcd, arr[i]); # If the exchange is possible if (p % gcd == 0) : return True; return False;# Driver code if __name__ == "__main__" : arr = [ 6, 9 ]; n = len(arr); p = 3; if (isPossible(arr, n, p)) : print("Yes"); else : print("No"); # This code is contributed by kanugargng |
C#
// C# implementation of the approach 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 that returns true if // the exchange is possible static bool isPossible(int []arr, int n, int p) { // Find the GCD of the array elements int gcd = 0; for (int i = 0; i < n; i++) gcd = __gcd(gcd, arr[i]); // If the exchange is possible if (p % gcd == 0) return true; return false; } // Driver code public static void Main (String[] args) { int []arr = { 6, 9 }; int n = arr.Length; int p = 3; if (isPossible(arr, n, p)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } }// This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation of the approach // Recursive function to // return gcd of a and b function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); } // Function that returns true if // the exchange is possible function isPossible(arr, n, p) { // Find the GCD of the array elements let gcd = 0; for (let i = 0; i < n; i++) gcd = __gcd(gcd, arr[i]); // If the exchange is possible if (p % gcd == 0) return true; return false; } let arr = [ 6, 9 ]; let n = arr.length; let p = 3; if (isPossible(arr, n, p)) document.write("Yes"); else document.write("No"); </script> |
Output:
Yes
Time Complexity: O(n * min(a, b)), where a and b are two parameters of _gcd
Auxiliary Space: O(min(a, b))
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!
