Dada una array arr[] . La tarea es minimizar la cantidad de intercambios necesarios de modo que para cada i en arr[] , arr[i]%3 = i%3 . Si tal reordenamiento no es posible, imprima -1.
Ejemplos:
Entrada: arr[ ] = {4, 3, 5, 2, 9, 7}
Salida: 3
Explicación: Las siguientes son las operaciones realizadas en arr[]
Inicialmente, índice % 3 = {0, 1, 2, 0, 1, 2} y arr[i] % 3 = {1, 0, 2, 2, 0, 1}.
intercambiar arr[0] y arr[1] actualiza arr[] a arr[] % 3 = {0, 1, 2, 2, 0, 1}
intercambiar arr[3] y arr[4] actualiza arr[] a arr [] % 3 = {0, 1, 2, 0, 2, 1}
intercambiar arr[4] y arr[5] actualiza arr[] a arr[] % 3 = {0, 1, 2, 0, 1, 2}
Por lo tanto, se requieren 3 intercambios para obtener la array resultante que es la mínima posible.Entrada: arr[] ={0, 1, 2, 3, 4}
Salida: 0
Enfoque: este problema está basado en la implementación y está relacionado con las propiedades del módulo . Siga los pasos a continuación para resolver el problema dado.
- Iterar la array con i de i = 0 a i = n-1
- si arr[i] % 3 es igual a 0 entonces, continuar.
- de lo contrario, encuentre el índice j de i+1 a n-1 , donde i % 3 = arr[j] % 3 y j % 3 = arr[i] % 3 .
- Con el paso anterior, mueva dos elementos de la array a sus posiciones deseadas.
- Si no se encuentra tal j , busque un índice k de i+1 a n-1 , donde i % 3 = arr[k] % 3 , e intercambie los elementos.
- El caso base será el recuento de índices tales que index%3 = arr[i] % 3 .
- Devuelve el conteo final como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for above approach
#include <iostream>
using namespace std;
// Function to swap two array elements.
void swapping(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to count the Swaps required such that
// for all i in arr[] arr[]% 3 = i % 3
int CountMinSwaps(int arr[], int n)
{
// index_mod_i = count of indexes which
// give i on modulo 3: index%3==i
int index_mod_0 = 0,
index_mod_1 = 0,
index_mod_2 = 0;
// array_mod_i = count of array elements
// which give i on modulo 3: arr[i]%3==i
int array_mod_0 = 0,
array_mod_1 = 0,
array_mod_2 = 0;
int i, j, count = 0;
for (i = 0; i < n; i++) {
if (i % 3 == 0)
index_mod_0 += 1;
else if (i % 3 == 1)
index_mod_1 += 1;
else if (i % 3 == 2)
index_mod_2 += 1;
if (arr[i] % 3 == 0)
array_mod_0 += 1;
else if (arr[i] % 3 == 1)
array_mod_1 += 1;
else if (arr[i] % 3 == 2)
array_mod_2 += 1;
}
// check for base condition.
if (index_mod_0 != array_mod_0
|| index_mod_1 != array_mod_1
|| index_mod_2 != array_mod_2)
return -1;
// count the swaps now.
for (i = 0; i < n; i++) {
// If already in right format
// Then goto next index
if (i % 3 == arr[i] % 3)
continue;
int index_org = i % 3;
int array_org = arr[i] % 3;
// Initially set swapped to false
bool swapped = false;
for (j = i + 1; j < n; j++) {
int index_exp = j % 3;
int array_exp = arr[j] % 3;
if (index_org == array_exp
&& array_org == index_exp) {
swapping(arr, i, j);
// Set swapped to true to make sure
// any value is swapped
swapped = true;
// Increment the count
count += 1;
break;
}
}
// Check if element is swapped or not
if (swapped == false) {
for (j = i + 1; j < n; j++) {
int array_exp = arr[j] % 3;
if (index_org == array_exp) {
// Swap indices i and j
swapping(arr, i, j);
// Increment the count of swaps
count += 1;
break;
}
}
}
}
// Return the final result
return count;
}
// Driver Code
int main()
{
int arr[6] = { 4, 3, 5, 2, 9, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int swaps = CountMinSwaps(arr, n);
cout << swaps << endl;
}
Java
// Java code for the above approach
import java.io.*;
class GFG {
// Function to swap two array elements.
static void swapping(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to count the Swaps required such that
// for all i in arr[] arr[]% 3 = i % 3
static int CountMinSwaps(int arr[], int n)
{
// index_mod_i = count of indexes which
// give i on modulo 3: index%3==i
int index_mod_0 = 0,
index_mod_1 = 0,
index_mod_2 = 0;
// array_mod_i = count of array elements
// which give i on modulo 3: arr[i]%3==i
int array_mod_0 = 0,
array_mod_1 = 0,
array_mod_2 = 0;
int i, j, count = 0;
for (i = 0; i < n; i++) {
if (i % 3 == 0)
index_mod_0 += 1;
else if (i % 3 == 1)
index_mod_1 += 1;
else if (i % 3 == 2)
index_mod_2 += 1;
if (arr[i] % 3 == 0)
array_mod_0 += 1;
else if (arr[i] % 3 == 1)
array_mod_1 += 1;
else if (arr[i] % 3 == 2)
array_mod_2 += 1;
}
// check for base condition.
if (index_mod_0 != array_mod_0
|| index_mod_1 != array_mod_1
|| index_mod_2 != array_mod_2)
return -1;
// count the swaps now.
for (i = 0; i < n; i++) {
// If already in right format
// Then goto next index
if (i % 3 == arr[i] % 3)
continue;
int index_org = i % 3;
int array_org = arr[i] % 3;
// Initially set swapped to false
boolean swapped = false;
for (j = i + 1; j < n; j++) {
int index_exp = j % 3;
int array_exp = arr[j] % 3;
if (index_org == array_exp
&& array_org == index_exp) {
swapping(arr, i, j);
// Set swapped to true to make sure
// any value is swapped
swapped = true;
// Increment the count
count += 1;
break;
}
}
// Check if element is swapped or not
if (swapped == false) {
for (j = i + 1; j < n; j++) {
int array_exp = arr[j] % 3;
if (index_org == array_exp) {
// Swap indices i and j
swapping(arr, i, j);
// Increment the count of swaps
count += 1;
break;
}
}
}
}
// Return the final result
return count;
}
public static void main (String[] args) {
int arr[] = { 4, 3, 5, 2, 9, 7 };
int n = arr.length;
int swaps = CountMinSwaps(arr, n);
System.out.println(swaps );
}
}
// This code is contributed by Potta Lokesh
Python3
# python Program for above approach # Function to swap two array elements. def swapping(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp # Function to count the Swaps required such that # for all i in arr[] arr[]% 3 = i % 3 def CountMinSwaps(arr, n): # index_mod_i = count of indexes which # give i on modulo 3: index%3==i index_mod_0 = 0 index_mod_1 = 0 index_mod_2 = 0 # array_mod_i = count of array elements # which give i on modulo 3: arr[i]%3==i array_mod_0 = 0 array_mod_1 = 0 array_mod_2 = 0 count = 0 for i in range(0, n): if (i % 3 == 0): index_mod_0 += 1 elif (i % 3 == 1): index_mod_1 += 1 elif (i % 3 == 2): index_mod_2 += 1 if (arr[i] % 3 == 0): array_mod_0 += 1 elif (arr[i] % 3 == 1): array_mod_1 += 1 elif (arr[i] % 3 == 2): array_mod_2 += 1 # check for base condition. if (index_mod_0 != array_mod_0 or index_mod_1 != array_mod_1 or index_mod_2 != array_mod_2): return -1 # count the swaps now. for i in range(0, n): # If already in right format # Then goto next index if (i % 3 == arr[i] % 3): continue index_org = i % 3 array_org = arr[i] % 3 # Initially set swapped to false swapped = False for j in range(i+1, n): index_exp = j % 3 array_exp = arr[j] % 3 if (index_org == array_exp and array_org == index_exp): swapping(arr, i, j) # Set swapped to true to make sure # any value is swapped swapped = True # Increment the count count += 1 break # Check if element is swapped or not if (swapped == False): for j in range(i+1, n): array_exp = arr[j] % 3 if (index_org == array_exp): # Swap indices i and j swapping(arr, i, j) # Increment the count of swaps count += 1 break # Return the final result return count # Driver Code if __name__ == "__main__": arr = [4, 3, 5, 2, 9, 7] n = len(arr) swaps = CountMinSwaps(arr, n) print(swaps) # This code is contributed by rakeshsahni
C#
// C# code for the above approach
using System;
class GFG
{
// Function to swap two array elements.
static void swapping(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to count the Swaps required such that
// for all i in arr[] arr[]% 3 = i % 3
static int CountMinSwaps(int[] arr, int n)
{
// index_mod_i = count of indexes which
// give i on modulo 3: index%3==i
int index_mod_0 = 0,
index_mod_1 = 0,
index_mod_2 = 0;
// array_mod_i = count of array elements
// which give i on modulo 3: arr[i]%3==i
int array_mod_0 = 0,
array_mod_1 = 0,
array_mod_2 = 0;
int i, j, count = 0;
for (i = 0; i < n; i++)
{
if (i % 3 == 0)
index_mod_0 += 1;
else if (i % 3 == 1)
index_mod_1 += 1;
else if (i % 3 == 2)
index_mod_2 += 1;
if (arr[i] % 3 == 0)
array_mod_0 += 1;
else if (arr[i] % 3 == 1)
array_mod_1 += 1;
else if (arr[i] % 3 == 2)
array_mod_2 += 1;
}
// check for base condition.
if (index_mod_0 != array_mod_0
|| index_mod_1 != array_mod_1
|| index_mod_2 != array_mod_2)
return -1;
// count the swaps now.
for (i = 0; i < n; i++)
{
// If already in right format
// Then goto next index
if (i % 3 == arr[i] % 3)
continue;
int index_org = i % 3;
int array_org = arr[i] % 3;
// Initially set swapped to false
Boolean swapped = false;
for (j = i + 1; j < n; j++)
{
int index_exp = j % 3;
int array_exp = arr[j] % 3;
if (index_org == array_exp
&& array_org == index_exp)
{
swapping(arr, i, j);
// Set swapped to true to make sure
// any value is swapped
swapped = true;
// Increment the count
count += 1;
break;
}
}
// Check if element is swapped or not
if (swapped == false)
{
for (j = i + 1; j < n; j++)
{
int array_exp = arr[j] % 3;
if (index_org == array_exp)
{
// Swap indices i and j
swapping(arr, i, j);
// Increment the count of swaps
count += 1;
break;
}
}
}
}
// Return the final result
return count;
}
public static void Main()
{
int[] arr = { 4, 3, 5, 2, 9, 7 };
int n = arr.Length;
int swaps = CountMinSwaps(arr, n);
Console.Write(swaps);
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// JavaScript Program for above approach
// Function to swap two array elements.
const swapping = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to count the Swaps required such that
// for all i in arr[] arr[]% 3 = i % 3
const CountMinSwaps = (arr, n) => {
// index_mod_i = count of indexes which
// give i on modulo 3: index%3==i
let index_mod_0 = 0,
index_mod_1 = 0,
index_mod_2 = 0;
// array_mod_i = count of array elements
// which give i on modulo 3: arr[i]%3==i
let array_mod_0 = 0,
array_mod_1 = 0,
array_mod_2 = 0;
let i, j, count = 0;
for (i = 0; i < n; i++) {
if (i % 3 == 0)
index_mod_0 += 1;
else if (i % 3 == 1)
index_mod_1 += 1;
else if (i % 3 == 2)
index_mod_2 += 1;
if (arr[i] % 3 == 0)
array_mod_0 += 1;
else if (arr[i] % 3 == 1)
array_mod_1 += 1;
else if (arr[i] % 3 == 2)
array_mod_2 += 1;
}
// check for base condition.
if (index_mod_0 != array_mod_0
|| index_mod_1 != array_mod_1
|| index_mod_2 != array_mod_2)
return -1;
// count the swaps now.
for (i = 0; i < n; i++) {
// If already in right format
// Then goto next index
if (i % 3 == arr[i] % 3)
continue;
let index_org = i % 3;
let array_org = arr[i] % 3;
// Initially set swapped to false
let swapped = false;
for (j = i + 1; j < n; j++) {
let index_exp = j % 3;
let array_exp = arr[j] % 3;
if (index_org == array_exp
&& array_org == index_exp) {
swapping(arr, i, j);
// Set swapped to true to make sure
// any value is swapped
swapped = true;
// Increment the count
count += 1;
break;
}
}
// Check if element is swapped or not
if (swapped == false) {
for (j = i + 1; j < n; j++) {
let array_exp = arr[j] % 3;
if (index_org == array_exp) {
// Swap indices i and j
swapping(arr, i, j);
// Increment the count of swaps
count += 1;
break;
}
}
}
}
// Return the final result
return count;
}
// Driver Code
let arr = [4, 3, 5, 2, 9, 7];
let n = arr.length;
let swaps = CountMinSwaps(arr, n);
document.write(swaps);
// This code is contributed by rakeshsahni
</script>
Producción:
3
Complejidad de tiempo: O(N 2 ), donde N es el tamaño de arr[].
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA