Compruebe si GCD de Array se puede hacer mayor que 1 reemplazando pares con sus productos

Posted on by Rudeus Greyrat

Dados tres números enteros L , R y K . Considere una array arr[] que consta de todos los elementos de L a R , la tarea es verificar si el GCD de la array se puede hacer mayor que 1 utilizando como máximo K operaciones. Una operación se define a continuación:

  • Elija dos números cualquiera de la array
  • Eliminarlos de la array
  • Inserte su producto nuevamente en la array

Ejemplos:

Entrada: L = 4, R = 10, K = 3
Salida: verdadero
Explicación: La array será arr[] = {4, 5, 6, 7, 8, 9, 10}
Elija arr[0], arr[1] : arr[] = {20, 6, 7, 8, 9, 10}
Elija arr[1], arr[2]: arr[] = {20, 42, 8, 9, 10}
Elija arr[2], arr[3]: arr[] = {20, 42, 72, 10}
GCD de la array formada = 2

Entrada: L = 3, R = 5, K = 1
Salida: falso
Explicación: La array será arr[] = {3, 4, 5}]
Operación en arr[0], arr[1]: arr[] = { 12, 5}, GCD = 1, o
Operación en arr[1], arr[2]: arr[] = {3, 20}, GCD = 1, o
Operación en arr[0], arr[2]: arr [] = {4, 15}, MCD = 1

 

Enfoque: la tarea se puede resolver convirtiendo todos los elementos impares de la array en pares , de modo que el GCD general de la array se vuelva par, es decir, mayor que 1 . Para comprobar si es posible o no, siga los casos a continuación:

  • Caso 1: si L = R = 1 entonces GCD siempre será 1, devuelve falso
  • Caso 2: si L = R (y L≠1) entonces GCD = L, devuelve verdadero
  • Caso 3: si K es mayor igual al número de probabilidades entre el rango L y R , entonces devuelve verdadero
  • Si alguno de los casos anteriores no implica, devuelve false .

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 find that GCD of array is
// greater than 1 or
// not after at most K operations
bool gcdOfArray(int L, int R, int K)
{
    // Finding number of integers
    // between L and R
    int range = (R - L + 1);
    int even = 0;
    int odd = 0;
 
    // Finding number of odd and even integers
    // in the given range
    if (range % 2 == 0) {
        even = range / 2;
        odd = range - even;
    }
    else {
        if (L % 2 != 0 || R % 2 != 0) {
            odd = (range / 2) + 1;
            even = range - odd;
        }
        else {
            odd = range / 2;
            even = range - odd;
        }
    }
 
    // Case 1
    if (L == R && L == 1)
        return false;
 
    // Case 2
    if (L == R)
        return true;
 
    // Case 3
    if (K >= odd)
        return true;
 
    // Otherwise not possible
    else
        return false;
}
 
// Driver Code
int main()
{
 
    int L = 4;
    int R = 10;
    int K = 3;
    bool isPossible = gcdOfArray(L, R, K);
    if (isPossible)
        cout << "true" << endl;
    else
        cout << "false" << endl;
    return 0;
}

Java

// JAVA program for the above approach
import java.util.*;
class GFG
{
   
  // Function to find that GCD of array is
  // greater than 1 or
  // not after at most K operations
  public static boolean gcdOfArray(int L, int R, int K)
  {
     
    // Finding number of integers
    // between L and R
    int range = (R - L + 1);
    int even = 0;
    int odd = 0;
 
    // Finding number of odd and even integers
    // in the given range
    if (range % 2 == 0) {
      even = range / 2;
      odd = range - even;
    }
    else {
      if (L % 2 != 0 || R % 2 != 0) {
        odd = (range / 2) + 1;
        even = range - odd;
      }
      else {
        odd = range / 2;
        even = range - odd;
      }
    }
 
    // Case 1
    if (L == R && L == 1)
      return false;
 
    // Case 2
    if (L == R)
      return true;
 
    // Case 3
    if (K >= odd)
      return true;
 
    // Otherwise not possible
    else
      return false;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    int L = 4;
    int R = 10;
    int K = 3;
    boolean isPossible = gcdOfArray(L, R, K);
    if (isPossible)
      System.out.println("true");
    else
      System.out.println("false");
  }
}
 
// This code is contributed by Taranpreet

Python3

# Python program for the above approach
 
# Function to find that GCD of array is
# greater than 1 or
# not after at most K operations
def gcdOfArray(L, R, K):
 
    # Finding number of integers
    # between L and R
    range = (R - L + 1)
    even = 0
    odd = 0
 
    # Finding number of odd and even integers
    # in the given range
    if (range % 2 == 0):
        even = range // 2
        odd = range - even
 
    else:
        if (L % 2 != 0 or R % 2 != 0):
            odd = (range // 2) + 1
            even = range - odd
        else:
            odd = range // 2
            even = range - odd
 
    # Case 1
    if (L == R and L == 1):
        return False
 
    # Case 2
    if (L == R):
        return True
 
    # Case 3
    if (K >= odd):
        return True
 
    # Otherwise not possible
    else:
        return False
 
 
# Driver Code
 
L = 4
R = 10
K = 3
isPossible = gcdOfArray(L, R, K)
if (isPossible):
    print("true")
else:
    print("false")
 
# This code is contributed by gfgking

C#

// C# program for the above approach
using System;
 
public class GFG{
   
  // Function to find that GCD of array is
  // greater than 1 or
  // not after at most K operations
  public static bool gcdOfArray(int L, int R, int K)
  {
     
    // Finding number of integers
    // between L and R
    int range = (R - L + 1);
    int even = 0;
    int odd = 0;
 
    // Finding number of odd and even integers
    // in the given range
    if (range % 2 == 0) {
      even = range / 2;
      odd = range - even;
    }
    else {
      if (L % 2 != 0 || R % 2 != 0) {
        odd = (range / 2) + 1;
        even = range - odd;
      }
      else {
        odd = range / 2;
        even = range - odd;
      }
    }
 
    // Case 1
    if (L == R && L == 1)
      return false;
 
    // Case 2
    if (L == R)
      return true;
 
    // Case 3
    if (K >= odd)
      return true;
 
    // Otherwise not possible
    else
      return false;
  }
 
  // Driver Code
  static public void Main (){
 
    int L = 4;
    int R = 10;
    int K = 3;
    bool isPossible = gcdOfArray(L, R, K);
    if (isPossible)
      Console.WriteLine("true");
    else
      Console.WriteLine("false");
  }
}
 
// This code is contributed by Shubham Singh

Javascript

<script>
    // JavaScript program for the above approach
 
    // Function to find that GCD of array is
    // greater than 1 or
    // not after at most K operations
    const gcdOfArray = (L, R, K) => {
     
        // Finding number of integers
        // between L and R
        let range = (R - L + 1);
        let even = 0;
        let odd = 0;
 
        // Finding number of odd and even integers
        // in the given range
        if (range % 2 == 0) {
            even = parseInt(range / 2);
            odd = range - even;
        }
        else {
            if (L % 2 != 0 || R % 2 != 0) {
                odd = parseInt(range / 2) + 1;
                even = range - odd;
            }
            else {
                odd = parseInt(range / 2);
                even = range - odd;
            }
        }
 
        // Case 1
        if (L == R && L == 1)
            return false;
 
        // Case 2
        if (L == R)
            return true;
 
        // Case 3
        if (K >= odd)
            return true;
 
        // Otherwise not possible
        else
            return false;
    }
 
    // Driver Code
 
    let L = 4;
    let R = 10;
    let K = 3;
    let isPossible = gcdOfArray(L, R, K);
    if (isPossible)
        document.write("true");
    else
        document.write("false");
 
// This code is contributed by rakeshsahni
 
</script>
Producción

true

Tiempo Complejidad :O(1)
Espacio Auxiliar :O(1)

Publicación traducida automáticamente

Artículo escrito por Kdheeraj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *