Check if there exists a subset with sum as 1 when each element is multiplied by an integer
Given an array arr[] of positive numbers. The task is to check if there exists any subset of any size such that after multiplying each element of the subset with any integer, will give the sum of the subset as 1.
Examples:
Input: arr[] = {12, 5, 9, 21}
Output: True
Explanation: Pick numbers 5 and 9. 5*2 + 9*(-1) = 1Input: arr[] = {9, 29, 6, 10}
Output: True
Explanation: Pick numbers 29 and 10. 29*(-1) + 10*(3) = 1
Approach: If the HCF of any pair of numbers from the array is 1, then return True else False. The equation ax + by = 1 has solution for x and y if gcd(a, b) = 1. No need to check the HCF of all possible pairs because GCD is an associative function.
gcd(a0, a1, …, an – 1) = gcd(a0, gcd(a1, …, an-1) = gcd(gcd(a0, a1), gcd(a2, …, an-1)) = …
and so on, every possible combination is included. So just iterate through array until a gcd of 1 is found. In other world, if gcd(a0, a1, …, an – 1) = 1, there exist a subsequence aij with #{ai0, …, aik} = k, 1 <= k <= N, that give a gcd of 1. Follow the steps below to solve the problem:
- Initialize the variable res as arr[0].
- Iterate over the range [1, N) using the variable i and perform the following tasks:
- Set the value of res as the gcd of res and arr[i].
- If res equals 1, then return true.
- After performing the above steps, print false as the answer.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach #include <iostream> using namespace std; // Function to find GCD int gcd( int a, int b) { if (a < b) gcd(b, a); if (a % b == 0) return b; else return gcd(b, a % b); } // Utility Function bool IsArrayGood( int arr[], int N) { int i, res = arr[0]; for (i = 1; i < N; i++) { res = gcd(res, arr[i]); if (res == 1) return true ; } return false ; } // Driver Code int main() { int arr[] = { 12, 5, 9, 21 }; int N = sizeof (arr) / sizeof (arr[0]); bool ver = IsArrayGood(arr, N); if (ver == true ) cout << "True" ; else cout << "False" ; return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.lang.*; import java.util.*; public class GFG { // Recursive function to return gcd of a and b static int gcd( int a, int b) { if (a < b) gcd(b, a); if (a % b == 0 ) return b; else return gcd(b, a % b); } // Utility Function static boolean IsArrayGood( int arr[], int N) { int i, res = arr[ 0 ]; for (i = 1 ; i < N; i++) { res = gcd(res, arr[i]); if (res == 1 ) return true ; } return false ; } // Driver Code public static void main(String[] args) { int arr[] = { 12 , 5 , 9 , 21 }; int N = arr.length; boolean ver = IsArrayGood(arr, N); if (ver == true ){ System.out.println( "True" ); } else { System.out.println( "False" ); } } } // This code is contributed by hrithikgarg03188 |
Python3
# Python code for the above approach # Function to find GCD def gcd(a, b): if (a < b): gcd(b, a); if (a % b = = 0 ): return b; else : return gcd(b, a % b); # Utility Function def IsArrayGood(arr, N): i = None res = arr[ 0 ]; for i in range ( 1 , N): res = gcd(res, arr[i]); if (res = = 1 ): return True ; return False ; # Driver Code arr = [ 12 , 5 , 9 , 21 ]; N = len (arr) ver = IsArrayGood(arr, N); if (ver = = True ): print ( "True" ); else : print ( "False" ); # This code is contributed by Saurabh Jaiswal |
C#
/*package whatever //do not write package name here */ using System; public class GFG { // Recursive function to return gcd of a and b static int gcd( int a, int b) { if (a < b) gcd(b, a); if (a % b == 0) return b; else return gcd(b, a % b); } // Utility Function static bool IsArrayGood( int [] arr, int N) { int i, res = arr[0]; for (i = 1; i < N; i++) { res = gcd(res, arr[i]); if (res == 1) return true ; } return false ; } // Driver Code public static void Main() { int [] arr = { 12, 5, 9, 21 }; int N = arr.Length; bool ver = IsArrayGood(arr, N); if (ver == true ){ Console.Write( "True" ); } else { Console.Write( "False" ); } } } // This code is contributed by gfgking |
Javascript
<script> // JavaScript code for the above approach // Function to find GCD function gcd(a, b) { if (a < b) gcd(b, a); if (a % b == 0) return b; else return gcd(b, a % b); } // Utility Function function IsArrayGood(arr, N) { let i, res = arr[0]; for (i = 1; i < N; i++) { res = gcd(res, arr[i]); if (res == 1) return true ; } return false ; } // Driver Code let arr = [12, 5, 9, 21]; let N = arr.length; let ver = IsArrayGood(arr, N); if (ver == true ) document.write( "True" ); else document.write( "False" ); // This code is contributed by Potta Lokesh </script> |
True
Time Complexity: O(N*log(D)) where D is the maximum element in the array
Auxiliary Space: O(1)