Dada una array arr[] de N enteros, la tarea es encontrar un entero X tal que los enteros que son divisibles por X y los enteros que no son divisibles por X sean alternativos entre sí en la array. Si no existe tal valor, imprima -1 .
Ejemplos:
Entrada: arr[] = {6, 5, 9, 10, 12, 15}
Salida: 5
Explicación: x = 5 divide todos los elementos en índices impares (indexación basada en 0)
pero no divide los elementos en índices pares entonces la respuesta es 5Entrada: {10, 20, 40, 30}
Salida: -1
Enfoque: el enfoque se basa en GCD ya que un conjunto de elementos alternos, ya sea en índices impares o índices pares, debe ser completamente divisible por un número entero, el único número que divide todos los números es el GCD de ese conjunto de elementos. El GCD de un conjunto no debe ser igual al del otro conjunto, entonces solo ese GCD se convierte en la respuesta. Siga los pasos a continuación para resolver este problema:
- Recorra la array arr[] y calcule el GCD de los elementos en índices impares (gcd1) y elementos en índices pares (gcd2) por separado.
- Si ambos GCD no son iguales, haga lo siguiente:
- Compruebe si hay un número entero en índices pares que sea divisible por mcd1 . Si se encuentra algún entero de este tipo, entonces gcd1 no es el valor requerido.
- Compruebe si hay un número entero en índices impares que sea divisible por mcd2 . Si se encuentra algún entero de este tipo, entonces gcd2 no es el valor requerido.
- Si alguna de las dos condiciones anteriores es falsa, el valor GCD correspondiente es la respuesta. De lo contrario, tal X no existe.
- De lo contrario, tal X no es posible.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the gcd of the array
int gcdofarray(int arr[], int start, int N)
{
int result = arr[start];
for (int i = start + 2; i < N; i += 2)
result = __gcd(arr[i], result);
return result;
}
// Function to check if the whole set
// is not divisible by gcd
bool check(int arr[], int start, int gcd,
int N)
{
for (int i = start; i < N; i += 2) {
// If any element is divisible
// by gcd return 0
if (arr[i] % gcd == 0) {
return 0;
}
}
return 1;
}
// Function to find the value x
void find_divisor(int arr[], int N)
{
// Find gcds of values at odd indices
// and at even indices separately
int gcd1 = gcdofarray(arr, 1, N);
int gcd2 = gcdofarray(arr, 0, N);
// If both the gcds are not same
if (gcd1 != gcd2) {
if (check(arr, 0, gcd1, N) != 0) {
int x = gcd1;
cout << x << endl;
return;
}
if (check(arr, 1, gcd2, N) != 0) {
int x = gcd2;
cout << x << endl;
return;
}
}
// If both the gcds are same print -1
cout << -1 << endl;
}
// Driver Code
int main()
{
// Initialize the array
int arr[] = { 6, 5, 9, 10, 12, 15 };
int N = sizeof(arr) / sizeof(arr[0]);
// Call the function
find_divisor(arr, N);
return 0;
}
Java
// Java code for the above approach
import java.util.*;
class GFG{
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// Base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b - a);
}
// Function to find the gcd of the array
static int gcdofarray(int arr[], int start, int N)
{
int result = arr[start];
for(int i = start + 2; i < N; i += 2)
result = __gcd(arr[i], result);
return result;
}
// Function to check if the whole set
// is not divisible by gcd
static boolean check(int arr[], int start,
int gcd, int N)
{
for(int i = start; i < N; i += 2)
{
// If any element is divisible
// by gcd return 0
if (arr[i] % gcd == 0)
{
return false;
}
}
return true;
}
// Function to find the value x
static void find_divisor(int arr[], int N)
{
// Find gcds of values at odd indices
// and at even indices separately
int gcd1 = gcdofarray(arr, 1, N);
int gcd2 = gcdofarray(arr, 0, N);
// If both the gcds are not same
if (gcd1 != gcd2)
{
if (check(arr, 0, gcd1, N))
{
int x = gcd1;
System.out.println(x);
return;
}
if (check(arr, 1, gcd2, N))
{
int x = gcd2;
System.out.println(x);
return;
}
}
// If both the gcds are same print -1
System.out.print(-1);
}
// Driver Code
public static void main(String args[])
{
// Initialize the array
int arr[] = { 6, 5, 9, 10, 12, 15 };
int N = arr.length;
// Call the function
find_divisor(arr, N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python # Java code for the above approach # Recursive function to return gcd of a and b def __gcd(a, b): # Everything divides 0 if (a == 0): return b if (b == 0): return a # Base case if (a == b): return a # a is greater if (a > b): return __gcd(a - b, b) return __gcd(a, b - a) # Function to find the gcd of the array def gcdofarray(arr, start, N): result = arr[start] for i in range(start + 2, N, 2): result = __gcd(arr[i], result) return result # Function to check if the whole set # is not divisible by gcd def check(arr, start, gcd, N): for i in range(start, N, 2): # If any element is divisible # by gcd return 0 if (arr[i] % gcd == 0): return False return True # Function to find the value x def find_divisor(arr, N): # Find gcds of values at odd indices # and at even indices separately gcd1 = gcdofarray(arr, 1, N) gcd2 = gcdofarray(arr, 0, N) # If both the gcds are not same if (gcd1 != gcd2): if (check(arr, 0, gcd1, N)): x = gcd1 print(x) return if (check(arr, 1, gcd2, N)): x = gcd2 print(x) return # If both the gcds are same print-1 print(-1) # Driver Code # Initialize the array arr = [6, 5, 9, 10, 12, 15] N = len(arr) # Call the function find_divisor(arr, N) # This code is contributed by Shubham Singh
C#
// C# code for the above approach
using System;
class GFG
{
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// Base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b - a);
}
// Function to find the gcd of the array
static int gcdofarray(int[] arr, int start, int N)
{
int result = arr[start];
for (int i = start + 2; i < N; i += 2)
result = __gcd(arr[i], result);
return result;
}
// Function to check if the whole set
// is not divisible by gcd
static bool check(int[] arr, int start,
int gcd, int N)
{
for (int i = start; i < N; i += 2)
{
// If any element is divisible
// by gcd return 0
if (arr[i] % gcd == 0)
{
return false;
}
}
return true;
}
// Function to find the value x
static void find_divisor(int[] arr, int N)
{
// Find gcds of values at odd indices
// and at even indices separately
int gcd1 = gcdofarray(arr, 1, N);
int gcd2 = gcdofarray(arr, 0, N);
// If both the gcds are not same
if (gcd1 != gcd2)
{
if (check(arr, 0, gcd1, N))
{
int x = gcd1;
Console.WriteLine(x);
return;
}
if (check(arr, 1, gcd2, N))
{
int x = gcd2;
Console.WriteLine(x);
return;
}
}
// If both the gcds are same print -1
Console.Write(-1);
}
// Driver Code
public static void Main()
{
// Initialize the array
int[] arr = { 6, 5, 9, 10, 12, 15 };
int N = arr.Length;
// Call the function
find_divisor(arr, N);
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// Javascript code for the above approach
// Recursive function to return gcd of a and b
function __gcd(a,b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// Base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b - a);
}
// Function to find the gcd of the array
function gcdofarray(arr, start, N)
{
var result = arr[start];
for(var i = start + 2; i < N; i += 2)
result = __gcd(arr[i], result);
return result;
}
// Function to check if the whole set
// is not divisible by gcd
function check( arr, start, gcd, N)
{
for(var i = start; i < N; i += 2)
{
// If any element is divisible
// by gcd return 0
if (arr[i] % gcd == 0)
{
return false;
}
}
return true;
}
// Function to find the value x
function find_divisor(arr, N)
{
// Find gcds of values at odd indices
// and at even indices separately
var gcd1 = gcdofarray(arr, 1, N);
var gcd2 = gcdofarray(arr, 0, N);
// If both the gcds are not same
if (gcd1 != gcd2)
{
if (check(arr, 0, gcd1, N))
{
var x = gcd1;
document.write(x);
return;
}
if (check(arr, 1, gcd2, N))
{
var x = gcd2;
document.write(x);
return;
}
}
// If both the gcds are same print -1
document.write(-1);
}
// Driver Code
// Initialize the array
var arr = [ 6, 5, 9, 10, 12, 15 ];
var N = arr.length;
// Call the function
find_divisor(arr, N);
// This code is contributed by Shubham Singh
</script>
Producción
5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA