Dada una array arr[] de n elementos, tenemos que intercambiar un índice i con otro índice i + k cualquier número de veces y comprobar si es posible ordenar la array dada arr[]. Si es así, escriba «sí», de lo contrario, escriba «no».
Ejemplos:
Entrada: K = 2, arr = [4, 3, 2, 6, 7]
Salida: Sí
Explicación:
Elija el índice i = 0 e intercambie el índice i con i + k, luego la array se convierte en [2, 3, 4, 6, 7] que está ordenado, por lo que la salida es «sí».
Entrada: K = 2, arr = [4, 2, 3, 7, 6]
Salida: No
Explicación:
No es posible obtener una array ordenada.
Enfoque:
Para resolver el problema mencionado anteriormente, debemos tomar los elementos a partir del índice 0 y agregarle los múltiplos de K, es decir, 0, 0 + k, 0 + (2 * k), y así sucesivamente. Intercambie estas posiciones para todos los índices de 0 a K-1 y verifique si la array final está ordenada. Si es así, devuelva «sí»; de lo contrario, «no».
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation to Check if it is possible to sort an
// array with conditional swapping of elements at distance K
#include <bits/stdc++.h>
using namespace std;
// Function for finding if it possible
// to obtain sorted array or not
bool fun(int arr[], int n, int k)
{
vector<int> v;
// Iterate over all elements until K
for (int i = 0; i < k; i++) {
// Store elements as multiples of K
for (int j = i; j < n; j += k) {
v.push_back(arr[j]);
}
// Sort the elements
sort(v.begin(), v.end());
int x = 0;
// Put elements in their required position
for (int j = i; j < n; j += k) {
arr[j] = v[x];
x++;
}
v.clear();
}
// Check if the array becomes sorted or not
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1])
return false;
}
return true;
}
// Driver code
int main()
{
int arr[] = { 4, 2, 3, 7, 6 };
int K = 2;
int n = sizeof(arr) / sizeof(arr[0]);
if (fun(arr, n, K))
cout << "yes" << endl;
else
cout << "no" << endl;
return 0;
}
Java
// Java implementation to check if it
// is possible to sort an array with
// conditional swapping of elements
// at distance K
import java.lang.*;
import java.io.*;
import java.util.*;
class GFG{
// Function for finding if it possible
// to obtain sorted array or not
public static boolean fun(int[] arr, int n,
int k)
{
Vector<Integer> v = new Vector<Integer>();
// Iterate over all elements until K
for(int i = 0; i < k; i++)
{
// Store elements as multiples of K
for(int j = i; j < n; j += k)
{
v.add(arr[j]);
}
// Sort the elements
Collections.sort(v);
int x = 0;
// Put elements in their
// required position
for(int j = i; j < n; j += k)
{
arr[j] = v.get(x);
x++;
}
v.clear();
}
// Check if the array becomes
// sorted or not
for(int i = 0; i < n - 1; i++)
{
if (arr[i] > arr[i + 1])
{
return false;
}
}
return true;
}
// Driver code
public static void main (String args[])
{
int[] arr = { 4, 2, 3, 7, 6 };
int K = 2;
int n = arr.length;
if (fun(arr, n, K))
{
System.out.println("yes");
}
else
{
System.out.println("no");
}
}
}
// This code is contributed by sayesha
Python3
# Python3 implementation to Check if it is possible to sort an
# array with conditional swapping of elements at distance K
# Function for finding if it possible
# to obtain sorted array or not
def fun(arr, n, k):
v = []
# Iterate over all elements until K
for i in range(k):
# Store elements as multiples of K
for j in range(i, n, k):
v.append(arr[j]);
# Sort the elements
v.sort();
x = 0
# Put elements in their required position
for j in range(i, n, k):
arr[j] = v[x];
x += 1
v = []
# Check if the array becomes sorted or not
for i in range(n - 1):
if (arr[i] > arr[i + 1]):
return False
return True
# Driver code
arr= [ 4, 2, 3, 7, 6 ]
K = 2;
n = len(arr)
if (fun(arr, n, K)):
print("yes")
else:
print("no")
# This code is contributed by apurva raj
C#
// C# implementation to check if it
// is possible to sort an array with
// conditional swapping of elements
// at distance K
using System;
using System.Collections.Generic;
class GFG{
// Function for finding if it possible
// to obtain sorted array or not
public static bool fun(int[] arr,
int n, int k)
{
List<int> v = new List<int>();
// Iterate over all elements until K
for(int i = 0; i < k; i++)
{
// Store elements as multiples of K
for(int j = i; j < n; j += k)
{
v.Add(arr[j]);
}
// Sort the elements
v.Sort();
int x = 0;
// Put elements in their
// required position
for(int j = i; j < n; j += k)
{
arr[j] = v[x];
x++;
}
v.Clear();
}
// Check if the array becomes
// sorted or not
for(int i = 0; i < n - 1; i++)
{
if (arr[i] > arr[i + 1])
{
return false;
}
}
return true;
}
// Driver code
public static void Main(String []args)
{
int[] arr = {4, 2, 3, 7, 6};
int K = 2;
int n = arr.Length;
if (fun(arr, n, K))
{
Console.WriteLine("yes");
}
else
{
Console.WriteLine("no");
}
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript implementation to
// Check if it is possible to sort an
// array with conditional swapping of
// elements at distance K
// Function for finding if it possible
// to obtain sorted array or not
function fun(arr, n, k)
{
let v = [];
// Iterate over all elements until K
for (let i = 0; i < k; i++) {
// Store elements as multiples of K
for (let j = i; j < n; j += k) {
v.push(arr[j]);
}
// Sort the elements
v.sort();
let x = 0;
// Put elements in their required position
for (let j = i; j < n; j += k) {
arr[j] = v[x];
x++;
}
v = [];
}
// Check if the array becomes sorted or not
for (let i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1])
return false;
}
return true;
}
// Driver code
let arr = [ 4, 2, 3, 7, 6 ];
let K = 2;
let n = arr.length;
if (fun(arr, n, K))
document.write("yes");
else
document.write("no");
</script>
no
Complejidad de tiempo: O(k*n*log(n))
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por ANKITKUMAR34 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA