Dada una array arr[] y un entero K . La tarea es ordenar los elementos que están entre dos múltiplos de K.
Ejemplos:
Entrada: arr[] = {2, 1, 13, 3, 7, 8, 21, 13, 12}, K = 2
Salida: 2 1 3 7 13 8 13 21 12
Los múltiplos de 2 en la array son 2, 8 y 12.
Los elementos que están entre los dos primeros múltiplos de 2 son 1, 13, 3 y 7.
Por lo tanto, estos elementos ordenados son 1, 3, 7 y 13.
De manera similar, los elementos entre 8 y 12 en el orden ordenado será 13 y 21.Entrada: arr[] = {11, 10, 9, 7, 4, 5, 12, 22, 13, 15, 17, 16}, K = 3
Salida: 11 10 9 4 5 7 12 13 22 15 17 16
Enfoque: recorra la array y realice un seguimiento de los múltiplos de K , a partir del segundo múltiplo de K clasifique cada elemento entre el múltiplo actual y el anterior de K . Imprima la array actualizada al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Utility function to print
// the contents of an array
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << (arr[i]) << " ";
}
// Function to sort elements
// in between multiples of k
void sortArr(int arr[], int n, int k)
{
// To store the index of
// previous multiple of k
int prev = -1;
for (int i = 0; i < n; i++)
{
if (arr[i] % k == 0)
{
// If it is not the
// first multiple of k
if (prev != -1)
// Sort the elements in between
// the previous and the current
// multiple of k
sort(arr + prev + 1, arr + i);
// Update previous to be current
prev = i;
}
}
// Print the updated array
printArr(arr, n);
}
// Driver code
int main()
{
int arr[] = {2, 1, 13, 3, 7,
8, 21, 13, 12};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
sortArr(arr, n, k);
}
// This code is contributed by
// Surendra_Gangwar
Java
// Java implementation of the approach
import java.util.Arrays;
class GFG {
// Utility function to print
// the contents of an array
static void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Function to sort elements
// in between multiples of k
static void sortArr(int arr[], int n, int k)
{
// To store the index of
// previous multiple of k
int prev = -1;
for (int i = 0; i < n; i++) {
if (arr[i] % k == 0) {
// If it is not the
// first multiple of k
if (prev != -1)
// Sort the elements in between
// the previous and the current
// multiple of k
Arrays.sort(arr, prev + 1, i);
// Update previous to be current
prev = i;
}
}
// Print the updated array
printArr(arr, n);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 1, 13, 3, 7, 8, 21, 13, 12 };
int n = arr.length;
int k = 2;
sortArr(arr, n, k);
}
}
Python3
# Python3 implementation of the approach # Utility function to print # the contents of an array def printArr(arr, n) : for i in range(n) : print(arr[i], end = " "); # Function to sort elements # in between multiples of k def sortArr(arr, n, k) : # To store the index of # previous multiple of k prev = -1; for i in range(n) : if (arr[i] % k == 0) : # If it is not the first # multiple of k if (prev != -1) : # Sort the elements in between #the previous and the current # multiple of k temp = arr[prev + 1:i]; temp.sort(); arr = arr[ : prev + 1] + temp + arr[i : ]; # Update previous to be current prev = i; # Print the updated array printArr(arr, n); # Driver code if __name__ == "__main__" : arr = [ 2, 1, 13, 3, 7, 8, 21, 13, 12 ]; n = len(arr); k = 2; sortArr(arr, n, k); # This code is contributed by Ryuga
C#
// C# implementation of the approach
using System.Collections;
using System;
class GFG {
// Utility function to print
// the contents of an array
static void printArr(int []arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Function to sort elements
// in between multiples of k
static void sortArr(int []arr, int n, int k)
{
// To store the index of
// previous multiple of k
int prev = -1;
for (int i = 0; i < n; i++) {
if (arr[i] % k == 0) {
// If it is not the
// first multiple of k
if (prev != -1)
// Sort the elements in between
// the previous and the current
// multiple of k
Array.Sort(arr, prev + 1, i-(prev + 1));
// Update previous to be current
prev = i;
}
}
// Print the updated array
printArr(arr, n);
}
// Driver code
public static void Main(String []args)
{
int []arr = { 2, 1, 13, 3, 7, 8, 21, 13, 12 };
int n = arr.Length;
int k = 2;
sortArr(arr, n, k);
}
}
//contributed by Arnab Kundu
Javascript
<script>
// Javascript implementation of the approach
// Utility function to print
// the contents of an array
function printArr(arr, n)
{
for (var i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Function to sort elements
// in between multiples of k
function sortArr(arr, n, k)
{
// To store the index of
// previous multiple of k
var prev = -1;
for (var i = 0; i < n; i++)
{
if (arr[i] % k == 0)
{
// If it is not the
// first multiple of k
if (prev != -1)
var tmp = arr.slice(prev+1, i).sort((a,b)=> a-b);
// Sort the elements in between
// the previous and the current
// multiple of k
for(var j=prev+1; j< i; j++)
{
arr[j] = tmp[j-prev-1];
}
// Update previous to be current
prev = i;
}
}
// Print the updated array
printArr(arr, n);
}
// Driver code
var arr = [2, 1, 13, 3, 7,
8, 21, 13, 12];
var n = arr.length;
var k = 2;
sortArr(arr, n, k);
</script>
Producción:
2 1 3 7 13 8 13 21 12