Dada una array, arr[] de enteros y un entero K. La tarea es ordenar los elementos de la array dada en el orden creciente de su módulo con K . Si dos números tienen el mismo resto, el número más pequeño debe ir primero.
Ejemplos :
Entrada: arr[] = {10, 3, 2, 6, 12}, K = 4
Salida: 12 2 6 10 3
{12, 2, 6, 10, 3} es el orden ordenado requerido como módulo
de estos elementos con K = 4 es {0, 2, 2, 2, 3}.Entrada: arr[] = {3, 4, 5, 10, 11, 1}, K = 3
Salida: 3 1 4 10 5 11
Acercarse:
- Crear K vectores vacíos .
- Recorra la array de izquierda a derecha y actualice los vectores de modo que el i – ésimo vector contenga los elementos que dan i como el resto cuando se divide por K.
- Ordene todos los vectores por separado ya que todos los elementos que dan el mismo valor de módulo con K deben ordenarse en forma ascendente.
- Ahora, comenzando desde el primer vector hasta el último vector y yendo de izquierda a derecha en los vectores, se obtendrán los elementos en el orden requerido.
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 the array elements
// based on their modulo with K
void sortWithRemainder(int arr[], int n, int k)
{
// Create K empty vectors
vector<int> v[k];
// Update the vectors such that v[i]
// will contain all the elements
// that give remainder as i
// when divided by k
for (int i = 0; i < n; i++) {
v[arr[i] % k].push_back(arr[i]);
}
// Sorting all the vectors separately
for (int i = 0; i < k; i++)
sort(v[i].begin(), v[i].end());
// Replacing the elements in arr[] with
// the required modulo sorted elements
int j = 0;
for (int i = 0; i < k; i++) {
// Add all the elements of the
// current vector to the array
for (vector<int>::iterator it = v[i].begin();
it != v[i].end(); it++) {
arr[j] = *it;
j++;
}
}
// Print the sorted array
printArr(arr, n);
}
// Driver code
int main()
{
int arr[] = { 10, 7, 2, 6, 12, 3, 33, 46 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
sortWithRemainder(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
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 the array elements
// based on their modulo with K
static void sortWithRemainder(int[] arr,
int n, int k)
{
// Create K empty vectors
ArrayList<
ArrayList<Integer>> v = new ArrayList<
ArrayList<Integer>>(k);
for(int i = 0; i < k; i++)
v.add(new ArrayList<Integer>());
// Update the vectors such that v[i]
// will contain all the elements
// that give remainder as i
// when divided by k
for(int i = 0; i < n; i++)
{
int t = arr[i] % k;
v.get(t).add(arr[i]);
}
// Sorting all the vectors separately
for(int i = 0; i < k; i++)
{
Collections.sort(v.get(i));
}
// Replacing the elements in
// arr[] with the required
// modulo sorted elements
int j = 0;
for(int i = 0; i < k; i++)
{
// Add all the elements of the
// current vector to the array
for(int x : v.get(i))
{
arr[j] = x;
j++;
}
}
// Print the sorted array
printArr(arr, n);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 10, 7, 2, 6,
12, 3, 33, 46 };
int n = arr.length;
int k = 4;
sortWithRemainder(arr, n, k);
}
}
// This code is contributed by grand_master
Python3
# Python3 implementation of the approach # Utility function to print # contents of an array def printArr(arr, n): for i in range(n): print(arr[i], end = ' ') # Function to sort the array elements # based on their modulo with K def sortWithRemainder(arr, n, k): # Create K empty vectors v = [[] for i in range(k)] # Update the vectors such that v[i] # will contain all the elements # that give remainder as i # when divided by k for i in range(n): v[arr[i] % k].append(arr[i]) # Sorting all the vectors separately for i in range(k): v[i].sort() # Replacing the elements in arr[] with # the required modulo sorted elements j = 0 for i in range(k): # Add all the elements of the # current vector to the array for it in v[i]: arr[j] = it j += 1 # Print the sorted array printArr(arr, n) # Driver code if __name__=='__main__': arr = [ 10, 7, 2, 6, 12, 3, 33, 46 ] n = len(arr) k = 4 sortWithRemainder(arr, n, k) # This code is contributed by pratham76
C#
// C# implementation of the
// above approach
using System;
using System.Collections;
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 the array elements
// based on their modulo with K
static void sortWithRemainder(int []arr,
int n, int k)
{
// Create K empty vectors
ArrayList []v = new ArrayList[k];
for(int i = 0; i < k; i++)
{
v[i] = new ArrayList();
}
// Update the vectors such that v[i]
// will contain all the elements
// that give remainder as i
// when divided by k
for (int i = 0; i < n; i++)
{
v[arr[i] % k].Add(arr[i]);
}
// Sorting all the vectors separately
for (int i = 0; i < k; i++)
{
v[i].Sort();
}
// Replacing the elements in
// arr[] with the required
// modulo sorted elements
int j = 0;
for (int i = 0; i < k; i++)
{
// Add all the elements of the
// current vector to the array
foreach(int x in v[i])
{
arr[j] = x;
j++;
}
}
// Print the sorted array
printArr(arr, n);
}
// Driver Code
public static void Main(string[] args)
{
int []arr = {10, 7, 2, 6,
12, 3, 33, 46};
int n = arr.Length;
int k = 4;
sortWithRemainder(arr, n, k);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation of the approach
// Utility function to print the
// contents of an array
function printArr(arr, n)
{
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Function to sort the array elements
// based on their modulo with K
function sortWithRemainder(arr, n, k)
{
// Create K empty vectors
let v = new Array();
for (let i = 0; i < k; i++)
{
v.push([])
}
// Update the vectors such that v[i]
// will contain all the elements
// that give remainder as i
// when divided by k
for (let i = 0; i < n; i++) {
v[arr[i] % k].push(arr[i]);
}
// Sorting all the vectors separately
for (let i = 0; i < k; i++)
v[i].sort((a, b) => a - b);
console.log(v)
// Replacing the elements in arr[] with
// the required modulo sorted elements
let j = 0;
for (let i = 0; i < k; i++) {
// Add all the elements of the
// current vector to the array
for (let it of v[i]) {
arr[j] = it;
j++;
}
}
// Print the sorted array
printArr(arr, n);
}
// Driver code
let arr = [10, 7, 2, 6, 12, 3, 33, 46];
let n = arr.length;
let k = 4;
sortWithRemainder(arr, n, k);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
12 33 2 6 10 46 3 7
Complejidad de tiempo: O (nlogn)