Reduce sum of any subset of an array to 1 by multiplying all its elements by any value

Reduce sum of any subset of an array to 1 by multiplying all its elements by any value

Given an array arr[] consisting of N positive integers, the task is to check if the sum of the elements of any subset of the given array can be reduced to 1 after multiplying all its elements by any integer. If it is not possible to do so, then print “No”. Otherwise, print “Yes”.

Examples:

Input: arr[] = {29, 6, 4, 10}
Output: Yes
Explanation:
Choose a subset {29, 6, 10} and multiply each corresponding element by {1, -3, -1}.
Therefore, sum of the subset = 29 * (1) + 6 * (-3) + 10 * (-1) = 29 – 18 – 10 = 1.
Therefore, print “Yes”.

Input: arr[] = {6, 3, 9}
Output: No

Naive Approach: The simplest approach is to generate all possible subsets of the given array and if there exists any subset in the array such that the sum of its elements, after being multiplied by any integer, results to 1, then print “Yes”. Otherwise print “No”.
Time Complexity: O(N * 2^N)
Auxiliary Space: O(1)

Efficient Approach: The above approach can also be optimized by using Bezout’s identity (Bezout’s lemma), which states that if the GCD of any two integers a and b is equal to d, then there exists integers x and y, such that a * x + b * y = d.

Therefore, the idea is to check if the GCD of the given array arr[] can be made 1 or not. Hence, to satisfy the given condition, there must exist any two elements whose GCD is 1, then the GCD of the array will be equal to 1. Hence, print “Yes”. Otherwise, print “No”.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    int gcd(int a, int b) {          if (a == 0)         return b;             return gcd(b % a, a); }    int findGCDofArray(int arr[], int N) {          int g = 0;             for (int i = 0; i < N; i++) {                     g = gcd(g, arr[i]);                     if (g == 1) {             return 1;         }     }             return g; }    void findSubset(int arr[], int N) {             int gcd = findGCDofArray(arr, N);             if (gcd == 1) {         cout << "Yes";     }             else {         cout << "No";     } }    int main() {     int arr[] = { 29, 6, 4, 10 };     int N = sizeof(arr) / sizeof(arr[0]);     findSubset(arr, N);        return 0; }

Output:

Yes

Time Complexity: O(N * log(M)), where M is the smallest element of the array.
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)