Dada una array arr[] de enteros positivos y un número positivo K, la tarea es encontrar los intercambios mínimos de elementos requeridos de modo que para cada elemento en el índice i, se cumpla la siguiente condición:
arr[i] % K = i % K
Ejemplo:
Entrada: arr = {4, 3, 5, 2, 9, 7}, K=3
Salida: 3
Explicación: Índice % 3 = 0 1 2 0 1 2 y arr[i] % 3 = 1 0 2 2 0 1
intercambiar el índice 0 con el índice 1 => 0 1 2 2 0 1
intercambiar el índice 3 con el índice 4 => 0 1 2 0 2 1
intercambiar el índice 4 con el índice 5 => 1 0 2 0 1 2Entrada: arr = {0, 1, 2, 3, 4, 5}, K=1
Salida: 0
Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . La idea es atravesar la array y hacer intercambios de modo que dos elementos se lleven a sus posiciones precisas si es posible, o bien, el elemento correcto se lleva a la posición actual. Se pueden seguir los siguientes pasos para resolver el problema:
- Compruebe si es posible completar la tarea comparando las frecuencias del índice % k con el elemento % k
- Si las frecuencias no coinciden, devuelve -1
- Iterar la array y en cada índice i :
- Si arr[i] % 3 == i % 3 entonces continúa con el siguiente índice
- De lo contrario, si arr[i] % 3 != i % 3 entonces encuentre el índice j de i+1 a N-1, donde i % 3 = arr[j] % 3 y j % 3 = arr[i] % 3 que traerá dos elementos a sus posiciones precisas
- De lo contrario, encuentre el índice k, iterando de i+1 a N-1, donde i % 3 = arr[k] % 3, e intercambie los elementos
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <iostream>
using namespace std;
// Function to swap the values
void swapping(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to find the minimum swaps
// required such that arr[i] % k = i % k
int CountMinSwaps(int arr[], int N, int K)
{
// initialize matrix with 0 values
int mat[K][2] = { 0 };
int i, j, count = 0;
for (i = 0; i < N; i++) {
// Count the frequency of
// index % k
mat[i % K][0] += 1;
// Count the frequency of
// index % k
mat[arr[i] % K][1] += 1;
}
// If the count of indexes % k and
// array elements % K are not same
// then the task is not possible
// therefore return -1
for (i = 0; i < K; i++) {
if (mat[i][0] != mat[i][1])
return -1;
}
// Count the swaps
for (i = 0; i < N; i++) {
// If condition is already true
// move to the next index
if (i % K == arr[i] % K)
continue;
// Current index remainder
int ind = i % K;
// Current element remainder
int ele = arr[i] % K;
// Boolean variable to indicate
// if the swap was made with the
// element such that both the swapped
// elements would be at correct place
bool swapped = false;
// Search for the element from
// i + 1 till end of the array
for (j = i + 1; j < N; j++) {
// Expected index remainder
int ind_exp = j % K;
// Expected element remainder
int ele_exp = arr[j] % K;
if (ind == ele_exp
&& ele == ind_exp) {
// Swap the element if found
swapping(arr, i, j);
// Update the boolean
// variable swap to true
swapped = true;
// Increment count of swaps
count++;
break;
}
}
// If the swap didnt take place
if (swapped == false) {
// Iterate from i+1 till end and
// find the accurate element for
// the current index
for (j = i + 1; j < N; j++) {
// Expected element remainder
int ele_exp = arr[j] % K;
if (ind == ele_exp) {
// Swap after finding
// the element
swapping(arr, i, j);
// Increment the count
count++;
break;
}
}
}
}
// Return the result
return count;
}
// Driver code
int main()
{
int arr[6] = { 0, 1, 2, 3, 4, 5 };
int K = 1;
int N = sizeof(arr) / sizeof(arr[0]);
// Call the function
int swaps = CountMinSwaps(arr, N, K);
// Print the answer
cout << swaps << endl;
}
Java
// Java implementation for the above approach
public class GFG {
// Function to swap the values
static void swapping(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to find the minimum swaps
// required such that arr[i] % k = i % k
static int CountMinSwaps(int arr[], int N, int K)
{
// initialize matrix with 0 values
int mat[][] = new int[K][2] ;
int i, j, count = 0;
for (i = 0; i < N; i++) {
// Count the frequency of
// index % k
mat[i % K][0] += 1;
// Count the frequency of
// index % k
mat[arr[i] % K][1] += 1;
}
// If the count of indexes % k and
// array elements % K are not same
// then the task is not possible
// therefore return -1
for (i = 0; i < K; i++) {
if (mat[i][0] != mat[i][1])
return -1;
}
// Count the swaps
for (i = 0; i < N; i++) {
// If condition is already true
// move to the next index
if (i % K == arr[i] % K)
continue;
// Current index remainder
int ind = i % K;
// Current element remainder
int ele = arr[i] % K;
// Boolean variable to indicate
// if the swap was made with the
// element such that both the swapped
// elements would be at correct place
boolean swapped = false;
// Search for the element from
// i + 1 till end of the array
for (j = i + 1; j < N; j++) {
// Expected index remainder
int ind_exp = j % K;
// Expected element remainder
int ele_exp = arr[j] % K;
if (ind == ele_exp
&& ele == ind_exp) {
// Swap the element if found
swapping(arr, i, j);
// Update the boolean
// variable swap to true
swapped = true;
// Increment count of swaps
count++;
break;
}
}
// If the swap didnt take place
if (swapped == false) {
// Iterate from i+1 till end and
// find the accurate element for
// the current index
for (j = i + 1; j < N; j++) {
// Expected element remainder
int ele_exp = arr[j] % K;
if (ind == ele_exp) {
// Swap after finding
// the element
swapping(arr, i, j);
// Increment the count
count++;
break;
}
}
}
}
// Return the result
return count;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 0, 1, 2, 3, 4, 5 };
int K = 1;
int N = arr.length;
// Call the function
int swaps = CountMinSwaps(arr, N, K);
// Print the answer
System.out.println(swaps);
}
}
// This code is contributed by AnkThon
Python3
# python implementation for the above approach # Function to swap the values def swapping(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp # Function to find the minimum swaps # required such that arr[i] % k = i % k def CountMinSwaps(arr, N, K): # initialize matrix with 0 values mat = [[0 for _ in range(2)] for _ in range(K)] count = 0 for i in range(0, N): # Count the frequency of # index % k mat[i % K][0] += 1 # Count the frequency of # index % k mat[arr[i] % K][1] += 1 # If the count of indexes % k and # array elements % K are not same # then the task is not possible # therefore return -1 for i in range(0, K): if (mat[i][0] != mat[i][1]): return -1 # Count the swaps for i in range(0, N): # If condition is already true # move to the next index if (i % K == arr[i] % K): continue # Current index remainder ind = i % K # Current element remainder ele = arr[i] % K # Boolean variable to indicate # if the swap was made with the # element such that both the swapped # elements would be at correct place swapped = False # Search for the element from # i + 1 till end of the array for j in range(i+1, N): # Expected index remainder ind_exp = j % K # Expected element remainder ele_exp = arr[j] % K if (ind == ele_exp and ele == ind_exp): # Swap the element if found swapping(arr, i, j) # Update the boolean # variable swap to true swapped = True # Increment count of swaps count += 1 break # If the swap didnt take place if (swapped == False): # Iterate from i+1 till end and # find the accurate element for # the current index for j in range(i+1, N): # Expected element remainder ele_exp = arr[j] % K if (ind == ele_exp): # Swap after finding # the element swapping(arr, i, j) # Increment the count count += 1 break # Return the result return count # Driver code if __name__ == "__main__": arr = [0, 1, 2, 3, 4, 5] K = 1 N = len(arr) # Call the function swaps = CountMinSwaps(arr, N, K) # Print the answer print(swaps) # This code is contributed by rakeshsahni
C#
// C# implementation for the above approach
using System;
public class GFG
{
// Function to swap the values
static void swapping(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to find the minimum swaps
// required such that arr[i] % k = i % k
static int CountMinSwaps(int[] arr, int N, int K)
{
// initialize matrix with 0 values
int[,] mat = new int[K, 2];
int i, j, count = 0;
for (i = 0; i < N; i++)
{
// Count the frequency of
// index % k
mat[i % K, 0] += 1;
// Count the frequency of
// index % k
mat[arr[i] % K, 1] += 1;
}
// If the count of indexes % k and
// array elements % K are not same
// then the task is not possible
// therefore return -1
for (i = 0; i < K; i++)
{
if (mat[i, 0] != mat[i, 1])
return -1;
}
// Count the swaps
for (i = 0; i < N; i++)
{
// If condition is already true
// move to the next index
if (i % K == arr[i] % K)
continue;
// Current index remainder
int ind = i % K;
// Current element remainder
int ele = arr[i] % K;
// Boolean variable to indicate
// if the swap was made with the
// element such that both the swapped
// elements would be at correct place
bool swapped = false;
// Search for the element from
// i + 1 till end of the array
for (j = i + 1; j < N; j++)
{
// Expected index remainder
int ind_exp = j % K;
// Expected element remainder
int ele_exp = arr[j] % K;
if (ind == ele_exp
&& ele == ind_exp)
{
// Swap the element if found
swapping(arr, i, j);
// Update the boolean
// variable swap to true
swapped = true;
// Increment count of swaps
count++;
break;
}
}
// If the swap didnt take place
if (swapped == false)
{
// Iterate from i+1 till end and
// find the accurate element for
// the current index
for (j = i + 1; j < N; j++)
{
// Expected element remainder
int ele_exp = arr[j] % K;
if (ind == ele_exp)
{
// Swap after finding
// the element
swapping(arr, i, j);
// Increment the count
count++;
break;
}
}
}
}
// Return the result
return count;
}
// Driver code
public static void Main()
{
int[] arr = { 0, 1, 2, 3, 4, 5 };
int K = 1;
int N = arr.Length;
// Call the function
int swaps = CountMinSwaps(arr, N, K);
// Print the answer
Console.Write(swaps);
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to swap the values
function swapping(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to find the minimum swaps
// required such that arr[i] % k = i % k
function CountMinSwaps(arr, N, K) {
// initialize matrix with 0 values
let mat = new Array(K);
for (let i = 0; i < mat.length; i++) {
mat[i] = new Array(2).fill(0);
}
let i, j, count = 0;
for (i = 0; i < N; i++) {
// Count the frequency of
// index % k
mat[i % K][0] += 1;
// Count the frequency of
// index % k
mat[arr[i] % K][1] += 1;
}
// If the count of indexes % k and
// array elements % K are not same
// then the task is not possible
// therefore return -1
for (i = 0; i < K; i++) {
if (mat[i][0] != mat[i][1])
return -1;
}
// Count the swaps
for (i = 0; i < N; i++) {
// If condition is already true
// move to the next index
if (i % K == arr[i] % K)
continue;
// Current index remainder
let ind = i % K;
// Current element remainder
let ele = arr[i] % K;
// Boolean variable to indicate
// if the swap was made with the
// element such that both the swapped
// elements would be at correct place
let swapped = false;
// Search for the element from
// i + 1 till end of the array
for (j = i + 1; j < N; j++) {
// Expected index remainder
let ind_exp = j % K;
// Expected element remainder
let ele_exp = arr[j] % K;
if (ind == ele_exp
&& ele == ind_exp) {
// Swap the element if found
swapping(arr, i, j);
// Update the boolean
// variable swap to true
swapped = true;
// Increment count of swaps
count++;
break;
}
}
// If the swap didnt take place
if (swapped == false) {
// Iterate from i+1 till end and
// find the accurate element for
// the current index
for (j = i + 1; j < N; j++) {
// Expected element remainder
let ele_exp = arr[j] % K;
if (ind == ele_exp) {
// Swap after finding
// the element
swapping(arr, i, j);
// Increment the count
count++;
break;
}
}
}
}
// Return the result
return count;
}
// Driver code
let arr = [0, 1, 2, 3, 4, 5];
let K = 1;
let N = arr.length;
// Call the function
let swaps = CountMinSwaps(arr, N, K);
// Print the answer
document.write(swaps + '<br>');
// This code is contributed by Potta Lokesh
</script>
Producción
0
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(2 * K)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA