Encuentre si la array se puede ordenar mediante intercambios limitados a múltiplos de k

Dada una array y un número k, la tarea es verificar si la array dada se puede ordenar o no con operaciones de intercambio limitadas. Podemos intercambiar arr[i] solo con arr[i] o arr[i + k] o arr[i + 2*k] o arr[i + 3*k] y así sucesivamente. En general, un elemento en el índice i se puede intercambiar con elementos en los índices i + j*k donde j = 0, 1, 2, 3, …
Nota: se puede realizar cualquier cantidad de intercambios en la array.

Ejemplos:

Entrada: arr[8] = [1, 5, 6, 9, 2, 3, 5, 9], k = 3 
Salida: Posible ordenar 
Explicación: 1 5 6 9 2 3 5 9 
0 1 2 3 4 5 6 7 aquí k es 3 
0 puede intercambiar con 0 + 3 = (3) elemento 
1 puede intercambiar con 1 + 3 = (4) elemento 
2 puede intercambiar con 2 + 3 = (5) elemento 
3 puede intercambiar con 3 + 3 = ( 6) el elemento 
4 puede intercambiarse con 4 + 3 = (7) elemento 
podemos ver que el elemento en el índice 0, 3, 6 puede intercambiarse entre sí 
podemos ver que el elemento en el índice 1, 4, 7 puede intercambiarse entre 
sí puede ver ese elemento en el índice 2, 5 puede intercambiar entre sí 
elemento 0 nunca puede intercambiar con 7, 1, 4, 2, 5 
intercambiar elemento en el índice (1, 4) 1 2 6 9 5 3 5 9 
porque sortarr[1 ] = 2 
intercambiar elemento en el índice (2, 5) 1 2 3 9 5 6 5 9 
porque sortarr[2] = 3 
intercambiar elemento en el índice (3, 6) 1 2 3 5 5 6 9 9 
porque sortarr[3] = 5 
intercambiando en este caso podemos llegar a 1 2 3 5 5 6 9 9

Entrada: arr=[1, 4, 2, 3], k = 2 
Salida: No es posible ordenar 
Explicación: 1 4 2 3 
0 1 2 3 donde k es 2 
0 puede intercambiarse con 0 + 2 = (2) elemento. 
1 puede intercambiar con 1 + 2 = (3) elemento. 
podemos ver que el elemento en el índice 0, 2 puede intercambiarse entre sí. 
podemos ver que el elemento en el índice 1, 3 puede intercambiarse entre sí. 
no es necesario intercambiar el elemento en el índice (0, 2) 1 4 2 3 
0 1 2 3 
en el índice 1 de la array ordenada es 2 
2 no está presente en 1 + j * 2, donde j = {0, 1} 
entonces desde 2 nunca puede venir en el índice 1 de la array, 
la array no se puede ordenar. 
la array no se ordena después del intercambio.

Entrada: arr[] = [1, 4, 2, 3], k = 1 
Salida: Posible ordenar 
Explicación: 1 4 2 3 
0 1 2 3 donde k es 1 
cuando k es 1 siempre es posible ordenar 
porque el intercambio tener lugar entre elementos adyacentes. 
 

Enfoque: 
1) Cree sortArr[] como una versión ordenada de un arr dado. 
2) Compare esta array con la array ordenada. 
3) Iterar sobre el ciclo for, para comparar el índice i. 
4) Ahora el índice i, el elemento se compara con 
index = i + j * k 
donde j = 0, 1, 2….. 
5) si para el elemento i particular de sortArr[i] coincide con la secuencia arr[index], entonces marca es 1 e 
intercambia arr[i], arr[índice] 
6) si no hay intercambio entonces el indicador es 0 y eso significa que no se encuentra ningún elemento en la secuencia 
7) si el indicador es 0 rompe el ciclo e imprime No es posible 
8) si no imprime Posible

#include <bits/stdc++.h>
using namespace std;
 
// CheckSort function
// To check if array can be sorted
void CheckSort(vector<int> arr,int k,int n){
 
    // sortarr is sorted array of arr
    vector<int> sortarr(arr.begin(),arr.end());
 
    sort(sortarr.begin(),sortarr.end());
 
    // if k = 1 then (always possible to sort)
    // swapping can easily give sorted
    // array
    if (k == 1)
        printf("yes");
    else
    {
        int flag = 0;
         
        // comparing sortarray with array
        for (int i = 0; i < n; i++)
        {
            flag = 0;
 
            // element at index j
            // must be in j = i + l * k form
            // where i = 0, 1, 2, 3...
            // where l = 0, 1, 2, 3, ..n-1
            for (int j = i; j < n; j += k)
            {
 
                //if element is present
                //then swapped
                if (sortarr[i] == arr[j]){
                    swap(arr[i], arr[j]);
                    flag = 1;
                    break;
                }
                if (j + k >= n)
                    break;
 
            }
 
 
            // if element of sorted array
            // does not found in its sequence
            // then flag remain zero
            // that means arr can not be
            // sort after swapping
            if (flag == 0)
                break;
 
            }
 
        // if flag is 0
        // Not possible
        // else Possible
        if (flag == 0)
            printf("Not possible to sort");
        else
            printf("Possible to sort");
        }
}
 
 
// Driver code
int main()
{
    // size of step
    int k = 3;
 
    // array initialized
    vector<int> arr ={1, 5, 6, 9, 2, 3, 5, 9};
 
    // length of arr
    int n =arr.size();
 
    // calling function
    CheckSort(arr, k, n);
 
    return 0;
}
 
// This code is contributed by mohit kumar 29

import java.util.*;
 
class GFG{
     
// CheckSort function
// To check if array can be sorted
public static void CheckSort(Vector<Integer> arr,
                             int k, int n)
{
     
    // sortarr is sorted array of arr
    Vector<Integer> sortarr = new Vector<Integer>();
    for(int i = 0; i < arr.size(); i++)
    {
        sortarr.add(arr.get(i));
    }
  
    Collections.sort(sortarr);
  
    // If k = 1 then (always possible to sort)
    // swapping can easily give sorted
    // array
    if (k == 1)
        System.out.println("yes");
    else
    {
        int flag = 0;
          
        // Comparing sortarray with array
        for(int i = 0; i < n; i++)
        {
            flag = 0;
  
            // Element at index j
            // must be in j = i + l * k form
            // where i = 0, 1, 2, 3...
            // where l = 0, 1, 2, 3, ..n-1
            for(int j = i; j < n; j += k)
            {
                 
                // If element is present
                //then swapped
                if (sortarr.get(i) == arr.get(j))
                {
                    Collections.swap(arr, i, j);
                    flag = 1;
                    break;
                }
                if (j + k >= n)
                    break;
            }
  
            // If element of sorted array
            // does not found in its sequence
            // then flag remain zero
            // that means arr can not be
            // sort after swapping
            if (flag == 0)
                break;
        }
         
        // If flag is 0
        // Not possible
        // else Possible
        if (flag == 0)
            System.out.println("Not possible to sort");
        else
            System.out.println("Possible to sort");
    }
}
 
// Driver code
public static void main(String[] args)
{
     
    // Size of step
    int k = 3;
  
    // Array initialized
    Vector<Integer> arr = new Vector<Integer>();
    arr.add(1);
    arr.add(5);
    arr.add(6);
    arr.add(9);
    arr.add(2);
    arr.add(3);
    arr.add(5);
    arr.add(9);
  
    // Length of arr
    int n = arr.size();
  
    // Calling function
    CheckSort(arr, k, n);
}
}
 
// This code is contributed by divyeshrabadiya07

# CheckSort function
# To check if array can be sorted
def CheckSort(arr, k, n):
     
    # sortarr is sorted array of arr
    sortarr = sorted(arr)
     
    # if k = 1 then (always possible to sort)
    # swapping can easily give sorted
    # array
    if (k == 1):
        print("yes")
    else:
         
        # comparing sortarray with array
        for i in range(0, n):
            flag = 0
             
            # element at index j
            # must be in j = i + l * k form
            # where i = 0, 1, 2, 3...
            # where l = 0, 1, 2, 3, ..n-1
            for j in range(i, n, k):
 
                # if element is present
                # then swapped
                if (sortarr[i] == arr[j]):
                    arr[i], arr[j] = arr[j], arr[i]
                    flag = 1
                    break
                if (j + k >= n):
                    break
 
            # if element of sorted array
            # does not found in its sequence
            # then flag remain zero
            # that means arr can not be
            # sort after swapping
            if (flag == 0):
                break
             
        # if flag is 0
        # Not possible
        # else Possible
        if (flag == 0):
            print("Not possible to sort")
        else:
            print("Possible to sort")
 
 
# Driver code
if __name__ == "__main__":
    # size of step
    k = 3
 
    # array initialized
    arr =[1, 5, 6, 9, 2, 3, 5, 9]
 
    # length of arr
    n = len(arr)
 
    # calling function
    CheckSort(arr, k, n)   

using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
   
// CheckSort function
// To check if array can be sorted
static void CheckSort(ArrayList arr, int k, int n)
{
     
    // sortarr is sorted array of arr
    ArrayList sortarr = new ArrayList(arr);
    sortarr.Sort();
     
    // If k = 1 then (always possible to sort)
    // swapping can easily give sorted
    // array
    if (k == 1)
        Console.Write("yes");
    else
    {
        int flag = 0;
          
        // Comparing sortarray with array
        for(int i = 0; i < n; i++)
        {
            flag = 0;
             
            // Element at index j
            // must be in j = i + l * k form
            // where i = 0, 1, 2, 3...
            // where l = 0, 1, 2, 3, ..n-1
            for(int j = i; j < n; j += k)
            {
                 
                // If element is present
                // then swapped
                if ((int)sortarr[i] == (int)arr[j])
                {
                    int tmp = (int)arr[i];
                    arr[i] = (int)arr[j];
                    arr[j] = tmp;
                    flag = 1;
                    break;
                }
                 
                if (j + k >= n)
                {
                    break;
                }
            }
 
            // If element of sorted array
            // does not found in its sequence
            // then flag remain zero
            // that means arr can not be
            // sort after swapping
            if (flag == 0)
            {
                break;
            }
        }
         
        // If flag is 0
        // Not possible
        // else Possible
        if (flag == 0)
            Console.Write("Not possible to sort");
        else
            Console.Write("Possible to sort");
    }
}
 
// Driver code
public static void Main(string[] args)
{
     
    // Size of step
    int k = 3;
  
    // Array initialized
    ArrayList arr = new ArrayList(){ 1, 5, 6, 9,
                                     2, 3, 5, 9 };
  
    // Length of arr
    int n = arr.Count;
  
    // Calling function
    CheckSort(arr, k, n);
}
}
 
// This code is contributed by rutvik_56

<script>
      // CheckSort function
      // To check if array can be sorted
      function CheckSort(arr, k, n)
      {
       
        // sortarr is sorted array of arr
        var sortarr = arr.sort((a, b) => a - b);
 
        // If k = 1 then (always possible to sort)
        // swapping can easily give sorted
        // array
        if (k === 1) document.write("yes");
        else
        {
          var flag = 0;
           
          // Comparing sortarray with array
          for (var i = 0; i < n; i++) {
            flag = 0;
 
            // Element at index j
            // must be in j = i + l * k form
            // where i = 0, 1, 2, 3...
            // where l = 0, 1, 2, 3, ..n-1
            for (var j = i; j < n; j += k)
            {
             
              // If element is present
              // then swapped
              if (sortarr[i] === arr[j])
              {
                var tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                flag = 1;
                break;
              }
 
              if (j + k >= n) {
                break;
              }
            }
 
            // If element of sorted array
            // does not found in its sequence
            // then flag remain zero
            // that means arr can not be
            // sort after swapping
            if (flag === 0) {
              break;
            }
          }
 
          // If flag is 0
          // Not possible
          // else Possible
          if (flag === 0) document.write("Not possible to sort");
          else document.write("Possible to sort");
        }
      }
 
      // Driver code
      // Size of step
      var k = 3;
 
      // Array initialized
      var arr = [1, 5, 6, 9, 2, 3, 5, 9];
 
      // Length of arr
      var n = arr.length;
 
      // Calling function
      CheckSort(arr, k, n);
       
      // This code is contributed by rdtank.
    </script>

Possible to sort

Análisis de rendimiento:  
Complejidad del tiempo: O(N^2) Donde N es el tamaño de la array. En el peor de los casos
Espacio auxiliar: O(N) donde N es el tamaño de la array.