Dada una array arr[] que consta de N enteros, la tarea es verificar si es posible ordenar la array utilizando las siguientes operaciones de intercambio:
El intercambio de dos números es válido solo si el máximo común divisor de la cuenta de bits establecidos de los dos números es igual al número de bits establecidos en el elemento más pequeño de la array.
Si es posible ordenar la array realizando solo los intercambios anteriores, imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {2, 3, 5, 7, 6}
Salida: Sí
Explicación:
se necesita intercambiar 7 y 6 para ordenar la array.
7 tiene 3 bits establecidos y 6 tiene 2 bits establecidos.
Dado que GCD(2, 3) = 1, que es igual al número de bits establecidos en el entero más pequeño de la array, es decir, 2 (1 bit establecido).
Por lo tanto, la array se puede ordenar intercambiando (7, 6).Entrada: arr[] = {3, 3, 15, 7}
Salida: No
Explicación:
se necesita intercambiar 15 y 7 para ordenar la array.
15 tiene 4 bits establecidos y 7 tiene 3 bits establecidos. GCD(4, 3) = 1, que no es igual al número de bits establecidos en el entero más pequeño de la array, es decir, 3 (2 bits establecidos).
Por lo tanto, la array no se puede ordenar.
Enfoque: siga los pasos a continuación para resolver el problema:
- Ordene la array dada y guárdela en una array auxiliar (digamos dup[] ).
- Itere sobre la array y para cada elemento, verifique si está en el mismo índice tanto en arr[] como en dup[] o no. Si se encuentra que es cierto, continúe con el siguiente índice.
- De lo contrario, si se requiere intercambiar los elementos de posición i -ésima y j -ésima en arr[] , calcule el GCD de los bits establecidos de arr[i] con los bits establecidos de arr[j] y verifique si es igual al recuento de bits establecidos en el elemento más pequeño de la array o no.
- Si no se permite ningún intercambio de este tipo, escriba «No» . De lo contrario, escriba «Sí» .
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 count number of set
// bits in an integer
int calculateSetBit(int n)
{
int count = 0;
// Traverse every bits
for (int i = 0; i < 32; i++) {
if (n & 1)
count++;
// Right shift by 1
n = n >> 1;
}
return count;
}
// Function to check if sorting the
// given array is possible or not
void sortPossible(int arr[], int n)
{
// Duplicate array
int dup[n];
for (int i = 0; i < n; i++)
dup[i] = arr[i];
// Sorted array to check if the
// original array can be sorted
sort(dup, dup + n);
// Flag variable to check
// if possible to sort
bool flag = 1;
// Calculate bits of smallest
// array element
int bit = calculateSetBit(dup[0]);
// Check every wrong placed
// integer in the array
for (int i = 0; i < n; i++) {
if (arr[i] != dup[i]) {
// Swapping only if GCD of set
// bits is equal to set bits in
// smallest integer
if (__gcd(
calculateSetBit(arr[i]),
bit)
!= bit) {
flag = 0;
break;
}
}
}
// Print the result
if (flag) {
cout << "Yes";
}
else {
cout << "No";
}
return;
}
// Driver Code
int main()
{
int arr[] = { 3, 9, 12, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
sortPossible(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
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 count number of set
// bits in an integer
static int calculateSetBit(int n)
{
int count = 0;
// Traverse every bits
for(int i = 0; i < 32; i++)
{
if ((n & 1) != 0)
count++;
// Right shift by 1
n = n >> 1;
}
return count;
}
// Function to check if sorting the
// given array is possible or not
static void sortPossible(int arr[], int n)
{
// Duplicate array
int dup[] = new int[n];
for(int i = 0; i < n; i++)
dup[i] = arr[i];
// Sorted array to check if the
// original array can be sorted
Arrays.sort(dup);
// Flag variable to check
// if possible to sort
int flag = 1;
// Calculate bits of smallest
// array element
int bit = calculateSetBit(dup[0]);
// Check every wrong placed
// integer in the array
for(int i = 0; i < n; i++)
{
if (arr[i] != dup[i])
{
// Swapping only if GCD of set
// bits is equal to set bits in
// smallest integer
if (gcd(calculateSetBit(
arr[i]), bit) != bit)
{
flag = 0;
break;
}
}
}
// Print the result
if (flag != 0)
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
return;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 9, 12, 6 };
int N = arr.length;
// Function call
sortPossible(arr, N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach
from math import gcd
# Function to count number of set
# bits in an eger
def calculateSetBit(n):
count = 0
# Traverse every bits
for i in range(32):
if (n & 1):
count += 1
# Right shift by 1
n = n >> 1
return count
# Function to check if sorting the
# given array is possible or not
def sortPossible(arr, n):
# Duplicate array
dup = [0] * n
for i in range(n):
dup[i] = arr[i]
# Sorted array to check if the
# original array can be sorted
dup = sorted(dup)
# Flag variable to check
# if possible to sort
flag = 1
# Calculate bits of smallest
# array element
bit = calculateSetBit(dup[0])
# Check every wrong placed
# eger in the array
for i in range(n):
if (arr[i] != dup[i]):
# Swapping only if GCD of set
# bits is equal to set bits in
# smallest eger
if (gcd(calculateSetBit(arr[i]), bit) != bit):
flag = 0
break
# Print the result
if (flag):
print("Yes")
else:
print("No")
return
# Driver Code
if __name__ == '__main__':
arr = [ 3, 9, 12, 6 ]
N = len(arr)
# Function call
sortPossible(arr, N)
# This code is contributed by mohit kumar 29
C#
// C# program 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 count number of set
// bits in an integer
static int calculateSetBit(int n)
{
int count = 0;
// Traverse every bits
for(int i = 0; i < 32; i++)
{
if ((n & 1) != 0)
count++;
// Right shift by 1
n = n >> 1;
}
return count;
}
// Function to check if sorting the
// given array is possible or not
static void sortPossible(int[] arr, int n)
{
// Duplicate array
int[] dup = new int[n];
for(int i = 0; i < n; i++)
dup[i] = arr[i];
// Sorted array to check if the
// original array can be sorted
Array.Sort(dup);
// Flag variable to check
// if possible to sort
int flag = 1;
// Calculate bits of smallest
// array element
int bit = calculateSetBit(dup[0]);
// Check every wrong placed
// integer in the array
for(int i = 0; i < n; i++)
{
if (arr[i] != dup[i])
{
// Swapping only if GCD of set
// bits is equal to set bits in
// smallest integer
if (gcd(calculateSetBit(
arr[i]), bit) != bit)
{
flag = 0;
break;
}
}
}
// Print the result
if (flag != 0)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
return;
}
// Driver Code
public static void Main()
{
int[] arr = { 3, 9, 12, 6 };
int N = arr.Length;
// Function call
sortPossible(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program to implement
// 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 count number of set
// bits in an integer
function calculateSetBit(n)
{
let count = 0;
// Traverse every bits
for(let i = 0; i < 32; i++)
{
if ((n & 1) != 0)
count++;
// Right shift by 1
n = n >> 1;
}
return count;
}
// Function to check if sorting the
// given array is possible or not
function sortPossible(arr, n)
{
// Duplicate array
let dup = [];
for(let i = 0; i < n; i++)
dup[i] = arr[i];
// Sorted array to check if the
// original array can be sorted
dup.sort();
// Flag variable to check
// if possible to sort
let flag = 1;
// Calculate bits of smallest
// array element
let bit = calculateSetBit(dup[0]);
// Check every wrong placed
// integer in the array
for(let i = 0; i < n; i++)
{
if (arr[i] != dup[i])
{
// Swapping only if GCD of set
// bits is equal to set bits in
// smallest integer
if (gcd(calculateSetBit(
arr[i]), bit) != bit)
{
flag = 0;
break;
}
}
}
// Print the result
if (flag != 0)
{
document.write("Yes");
}
else
{
document.write("No");
}
return;
}
// Driver code
let arr = [ 3, 9, 12, 6 ];
let N = arr.length;
// Function call
sortPossible(arr, N);
// This code is contributed by target_2.
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pradyumanagarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA