Dada una array arr[] que consta de N enteros positivos, la tarea es verificar si la suma de los elementos de cualquier subconjunto de la array dada se puede reducir a 1 después de multiplicar todos sus elementos por cualquier número entero. Si no es posible hacerlo, escriba “No” . De lo contrario, escriba «Sí» .
Ejemplos:
Entrada: arr[] = {29, 6, 4, 10}
Salida: Sí
Explicación:
Elija un subconjunto {29, 6, 10} y multiplique cada elemento correspondiente por {1, -3, -1}.
Por lo tanto, suma del subconjunto = 29 * (1) + 6 * (-3) + 10 * (-1) = 29 – 18 – 10 = 1. Por lo tanto,
imprime “Sí”.Entrada: arr[] = {6, 3, 9}
Salida: No
Enfoque ingenuo: el enfoque más simple es generar todos los subconjuntos posibles de la array dada y si existe algún subconjunto en la array tal que la suma de sus elementos, después de ser multiplicados por cualquier número entero, da como resultado 1, entonces imprime «Sí» . De lo contrario, escriba “No” .
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la identidad de Bezout (lema de Bezout) , que establece que si el MCD de dos enteros a y b es igual a d , entonces existen los enteros x e y , tales que a * x + segundo * y = re .
Por lo tanto, la idea es verificar si el GCD de la array dada arr[] se puede hacer 1 o no. Por lo tanto, para satisfacer la condición dada, deben existir dos elementos cualesquiera cuyo MCD sea 1 , entonces el MCD del arreglo será igual a 1 . Por lo tanto, imprima «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return gcd of a and b
int gcd(int a, int b)
{
// Base Case
if (a == 0)
return b;
// Find the GCD recursively
return gcd(b % a, a);
}
// Function to calculate the GCD
// of the array arr[]
int findGCDofArray(int arr[], int N)
{
// Stores the GCD of array
int g = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Update gcd of the array
g = gcd(g, arr[i]);
// If gcd is 1, then return 1
if (g == 1) {
return 1;
}
}
// Return the resultant GCD
return g;
}
// Function to check if a subset satisfying
// the given condition exists or not
void findSubset(int arr[], int N)
{
// Calculate the gcd of the array
int gcd = findGCDofArray(arr, N);
// If gcd is 1, then print Yes
if (gcd == 1) {
cout << "Yes";
}
// Otherwise, print No
else {
cout << "No";
}
}
// Driver Code
int main()
{
int arr[] = { 29, 6, 4, 10 };
int N = sizeof(arr) / sizeof(arr[0]);
findSubset(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
// Function to return gcd of a and b
static int gcd(int a, int b)
{
// Base Case
if (a == 0)
return b;
// Find the GCD recursively
return gcd(b % a, a);
}
// Function to calculate the GCD
// of the array arr[]
static int findGCDofArray(int arr[], int N)
{
// Stores the GCD of array
int g = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Update gcd of the array
g = gcd(g, arr[i]);
// If gcd is 1, then return 1
if (g == 1) {
return 1;
}
}
// Return the resultant GCD
return g;
}
// Function to check if a subset satisfying
// the given condition exists or not
static void findSubset(int arr[], int N)
{
// Calculate the gcd of the array
int gcd = findGCDofArray(arr, N);
// If gcd is 1, then print Yes
if (gcd == 1) {
System.out.println("Yes");
}
// Otherwise, print No
else {
System.out.println("No");
}
}
// Driver code
public static void main(String[] args)
{
// Given array
int arr[] = { 29, 6, 4, 10 };
// length of the array
int N = arr.length;
// function call
findSubset(arr, N);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach
# Function to return gcd of a and b
def gcd(a, b):
# Base Case
if (a == 0):
return b
# Find the GCD recursively
return gcd(b % a, a)
# Function to calculate the GCD
# of the array arr[]
def findGCDofArray(arr, N):
# Stores the GCD of array
g = 0
# Traverse the array arr[]
for i in range(N):
# Update gcd of the array
g = gcd(g, arr[i])
# If gcd is 1, then return 1
if (g == 1):
return 1
# Return the resultant GCD
return g
# Function to check if a subset satisfying
# the given condition exists or not
def findSubset(arr, N):
# Calculate the gcd of the array
gcd = findGCDofArray(arr, N)
# If gcd is 1, then print Yes
if (gcd == 1):
print("Yes")
# Otherwise, print No
else:
print("No")
# Driver Code
if __name__ == '__main__':
arr = [29, 6, 4, 10]
N = len(arr)
findSubset(arr, N)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to return gcd of a and b
static int gcd(int a, int b)
{
// Base Case
if (a == 0)
return b;
// Find the GCD recursively
return gcd(b % a, a);
}
// Function to calculate the GCD
// of the array arr[]
static int findGCDofArray(int[] arr, int N)
{
// Stores the GCD of array
int g = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Update gcd of the array
g = gcd(g, arr[i]);
// If gcd is 1, then return 1
if (g == 1) {
return 1;
}
}
// Return the resultant GCD
return g;
}
// Function to check if a subset satisfying
// the given condition exists or not
static void findSubset(int[] arr, int N)
{
// Calculate the gcd of the array
int gcd = findGCDofArray(arr, N);
// If gcd is 1, then print Yes
if (gcd == 1) {
Console.Write("Yes");
}
// Otherwise, print No
else {
Console.Write("No");
}
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 29, 6, 4, 10 };
int N = arr.Length;
findSubset(arr, N);
}
}
// This code is contributed by shivani
Javascript
<script>
// javascript program for the above approach
// Function to return gcd of a and b
function gcd(a , b) {
// Base Case
if (a == 0)
return b;
// Find the GCD recursively
return gcd(b % a, a);
}
// Function to calculate the GCD
// of the array arr
function findGCDofArray(arr , N) {
// Stores the GCD of array
var g = 0;
// Traverse the array arr
for (i = 0; i < N; i++) {
// Update gcd of the array
g = gcd(g, arr[i]);
// If gcd is 1, then return 1
if (g == 1) {
return 1;
}
}
// Return the resultant GCD
return g;
}
// Function to check if a subset satisfying
// the given condition exists or not
function findSubset(arr , N) {
// Calculate the gcd of the array
var gcd = findGCDofArray(arr, N);
// If gcd is 1, then print Yes
if (gcd == 1) {
document.write("Yes");
}
// Otherwise, print No
else {
document.write("No");
}
}
// Driver code
// Given array
var arr = [ 29, 6, 4, 10 ];
// length of the array
var N = arr.length;
// function call
findSubset(arr, N);
// This code contributed by gauravrajput1
</script>
Yes
Complejidad de tiempo: O(N * log(M)), donde M es el elemento más pequeño de la array .
Espacio Auxiliar: O(1)