Dada una array, arr[] que consiste en N enteros positivos, la tarea es hacer que la array no sea decreciente intercambiando pares (arr[i], arr[j]) tal que i != j (1 ≤ i, j ≤ n) y GCD (arr[i], arr[j]) es igual al elemento mínimo presente en el arreglo .
Ejemplos:
Entrada: arr[] = {4, 3, 6, 6, 2, 9}
Salida: Sí
Explicación:
elemento de array mínimo = 2.
Intercambiar arr[0] y arr[2], ya que gcd(4, 6) = 2 La array se modifica a {6, 3, 4, 6, 2, 9}.
Intercambia arr[0] y arr[4], ya que mcd(6, 2) = 2.
Por lo tanto, la array modificada {2, 3, 4, 6, 6, 9} no es decreciente.Entrada: arr[] = {7, 5, 2, 2, 4}
Salida: No
Acercarse:
- En primer lugar, recorra la array para encontrar el elemento mínimo . Almacene todos estos elementos en otra array y ordene esa array .
- Para cada elemento de la array, compruebe si está en la posición correcta o no. Si se encuentra que es cierto, continúe con el siguiente elemento. De lo contrario, verifique si es divisible por el elemento más pequeño de la array, ya que solo estos elementos tendrán GCD con otros elementos iguales al elemento mínimo de la array .
- Si algún elemento del arreglo no está en su posición correcta y ese elemento no es divisible por el elemento mínimo del arreglo, imprima “No”.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the array
// can be made non-decreasing
bool check(int a[], int n)
{
int b[n];
int minElement = INT_MAX;
// Iterate till N
for(int i = 0; i < n; i++)
{
// Find the minimum element
b[i] = a[i];
minElement = min(minElement, a[i]);
}
// Sort the array
sort(b, b + n);
int k = 1;
// Iterate till N
for(int i = 0; i < n; i++)
{
// Check if the element is
// at its correct position
if (a[i] != b[i] &&
a[i] % minElement != 0)
{
k = 0;
break;
}
}
// Return the answer
return k == 1 ? true : false;
}
// Driver Code
int main()
{
int a[] = { 4, 3, 6, 6, 2, 9 };
int n = sizeof(a) / sizeof(a[0]);
// Print the answer
if (check(a, n) == true)
cout << "Yes \n";
else
cout<<"No \n";
return 0;
}
// This code is contributed by akhilsaini
Java
// Java program for above approach
import java.io.*;
import java.util.*;
import java.math.*;
class GFG {
// Function to check if the array
// can be made non-decreasing
public static boolean check(int[] a, int n)
{
int[] b = new int[n];
int minElement = Integer.MAX_VALUE;
// Iterate till N
for (int i = 0; i < n; i++) {
// Find the minimum element
b[i] = a[i];
minElement
= Math.min(minElement, a[i]);
}
// Sort the array
Arrays.sort(b);
int k = 1;
// Iterate till N
for (int i = 0; i < n; i++) {
// Check if the element is
// at its correct position
if (a[i] != b[i]
&& a[i] % minElement != 0) {
k = 0;
break;
}
}
// Return the answer
return k == 1 ? true : false;
}
// Driver Code
public static void main(String[] args)
{
int[] a = { 4, 3, 6, 6, 2, 9 };
int n = a.length;
// Print the answer
if (check(a, n) == true) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
}
Python3
# Python3 program for above approach
import sys
# Function to check if the array
# can be made non-decreasing
def check(a, n):
b = [None] * n
minElement = sys.maxsize
# Iterate till N
for i in range(0, n):
# Find the minimum element
b[i] = a[i]
minElement = min(minElement, a[i])
# Sort the array
b.sort()
k = 1
# Iterate till N
for i in range(0, n):
# Check if the element is
# at its correct position
if ((a[i] != b[i]) and
(a[i] % minElement != 0)):
k = 0
break
# Return the answer
if k == 1:
return True
else:
return False
# Driver Code
if __name__ == "__main__":
a = [ 4, 3, 6, 6, 2, 9 ]
n = len(a)
# Print the answer
if check(a, n) == True:
print("Yes")
else:
print("No")
# This code is contributed by akhilsaini
C#
// C# program for above approach
using System;
class GFG{
// Function to check if the array
// can be made non-decreasing
static bool check(int[] a, int n)
{
int[] b = new int[n];
int minElement = int.MaxValue;
// Iterate till N
for(int i = 0; i < n; i++)
{
// Find the minimum element
b[i] = a[i];
minElement = Math.Min(minElement, a[i]);
}
// Sort the array
Array.Sort(b);
int k = 1;
// Iterate till N
for(int i = 0; i < n; i++)
{
// Check if the element is
// at its correct position
if (a[i] != b[i] &&
a[i] % minElement != 0)
{
k = 0;
break;
}
}
// Return the answer
return k == 1 ? true : false;
}
// Driver Code
static public void Main()
{
int[] a = { 4, 3, 6, 6, 2, 9 };
int n = a.Length;
// Print the answer
if (check(a, n) == true)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to check if the array
// can be made non-decreasing
function check(a, n)
{
let b = new Array(n).fill(0);
let minElement = Number.MAX_VALUE;
// Iterate till N
for (let i = 0; i < n; i++) {
// Find the minimum element
b[i] = a[i];
minElement
= Math.min(minElement, a[i]);
}
// Sort the array
b.sort();
let k = 1;
// Iterate till N
for (let i = 0; i < n; i++) {
// Check if the element is
// at its correct position
if (a[i] != b[i]
&& a[i] % minElement != 0) {
k = 0;
break;
}
}
// Return the answer
return k == 1 ? true : false;
}
// Driver Code
let a = [ 4, 3, 6, 6, 2, 9 ];
let n = a.length;
// Print the answer
if (check(a, n) == true) {
document.write("Yes");
}
else {
document.write("No");
}
// This code is contributed by avijitmondal1998.
</script>
Producción:
Yes
Complejidad temporal: O(N logN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA