Compruebe si existe un subconjunto con suma 1 cuando cada elemento se multiplica por un número entero

Dada una array arr[] de números positivos. La tarea es verificar si existe algún subconjunto de cualquier tamaño tal que después de multiplicar cada elemento del subconjunto con cualquier número entero, dará la suma del subconjunto como 1. 

Ejemplos:

Entrada: arr[] = {12, 5, 9, 21}
Salida: Verdadero
Explicación: Elija los números 5 y 9. 5*2 + 9*(-1) = 1

Entrada: arr[] = {9, 29, 6, 10}
Salida: Verdadero
Explicación: Elija los números 29 y 10. 29*(-1) + 10*(3) = 1

Enfoque: si el HCF de cualquier par de números de la array es 1 , devuelva True else False . La ecuación ax + by = 1 tiene solución para xey si mcd(a, b) = 1 . No es necesario verificar el HCF de todos los pares posibles porque GCD es una función asociativa.

mcd(a0, a1, …, an – 1) = mcd(a0, mcd(a1, …, an-1) = mcd(mcd(a0, a1), mcd(a2, …, an-1)) = …

y así sucesivamente, se incluyen todas las combinaciones posibles. Así que simplemente itere a través de la array hasta que se encuentre un gcd de 1 . En otro mundo, si mcd(a0, a1, …, an – 1) = 1, existe una subsecuencia aij con #{ai0, …, aik} = k, 1 <= k <= N , que da un mcd de 1 . Siga los pasos a continuación para resolver el problema:

• Inicialice la variable res como arr[0].
• Itere sobre el rango [1, N) usando la variable i y realice las siguientes tareas:
  • Establezca el valor de res como el gcd de res y arr[i].
  • Si res es igual a 1, devuelve verdadero.
• Después de realizar los pasos anteriores, escriba falso como respuesta.

A continuación se muestra la implementación del enfoque anterior:

// 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;
}

/*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

# 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

/*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

<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

Complejidad de tiempo: O(N*log(D)) donde D es el elemento máximo en el arreglo
Espacio auxiliar: O(1)