Given an array of integers and a number K. The task is to sort only those elements of the array which yields remainder P upon division by K . Sorting must be done at their relative positions only without affecting any other elements.
Examples:
Input : arr[] = {10, 3, 2, 6, 12}, K = 4, P = 2
Output : 2 3 6 10 12Input : arr[] = {3, 4, 5, 10, 11, 1}, K = 3, P = 1
Output : 3 1 5 4 11 10
Approach:
- Initialise two empty vectors.
- Traverse the array, from left to right and check modulo of each element with K.
- In first vector, insert the index of all elements which yields remainder P.
- In second vector, insert the elements which yields remainder P.
- Sort the second vector.
- Now, we have the index of all required elements and also all of the required elements in sorted order.
- So, insert the elements of the second vector into the array at the indices present in first vector one by one.
Below is the implementation of the above approach:
C++
// C++ program for sorting array elements// whose modulo with K yields P#include <bits/stdc++.h>using namespace std;// Function to sort elements// whose modulo with K yields Pvoid sortWithRemainderP(int arr[], int n, int k, int p){ // initialise two vectors vector<int> v1, v2; for (int i = 0; i < n; i++) { if (arr[i] % k == p) { // first vector contains indices of // required element v1.push_back(i); // second vector contains // required elements v2.push_back(arr[i]); } } // sorting the elements in second vector sort(v2.begin(), v2.end()); // replacing the elements whose modulo with K yields P // with the sorted elements for (int i = 0; i < v1.size(); i++) arr[v1[i]] = v2[i]; // printing the new sorted array elements for (int i = 0; i < n; i++) cout << arr[i] << " ";}// Driver codeint main(){ int arr[] = { 8, 255, 16, 2, 4, 0 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; int p = 0; sortWithRemainderP(arr, n, k, p); return 0;} |
Java
// Java program for sorting array elements // whose modulo with K yields P import java.util.*;class GFG {// Function to sort elements // whose modulo with K yields P static void sortWithRemainderP(int arr[], int n, int k, int p) { // initialise two vectors Vector<Integer> v1 = new Vector<Integer>(); Vector<Integer> v2 = new Vector<Integer>(); for (int i = 0; i < n; i++) { if (arr[i] % k == p) { // first vector contains indices of // required element v1.add(i); // second vector contains // required elements v2.add(arr[i]); } } // sorting the elements in second vector Collections.sort(v2); // replacing the elements whose modulo with K yields P // with the sorted elements for (int i = 0; i < v1.size(); i++) arr[v1.get(i)] = v2.get(i); // printing the new sorted array elements for (int i = 0; i < n; i++) System.out.print(arr[i]+" ");} // Driver code public static void main(String[] args) { int arr[] = { 8, 255, 16, 2, 4, 0 }; int n = arr.length; int k = 2; int p = 0; sortWithRemainderP(arr, n, k, p); }} // This code is contributed by 29AjayKumar |
Python3
# Python 3 program for sorting array# elements whose modulo with K yields P# Function to sort elements whose modulo# with K yields Pdef sortWithRemainderP(arr, n, k, p): # initialise two vectors v1 = [] v2 = [] for i in range(0, n, 1): if (arr[i] % k == p): # first vector contains indices # of required element v1.append(i) # second vector contains # required elements v2.append(arr[i]) # sorting the elements in second vector v2.sort(reverse = False) # replacing the elements whose modulo # with K yields P with the sorted elements for i in range(0, len(v1), 1): arr[v1[i]] = v2[i] # printing the new sorted array elements for i in range(0, n, 1): print(arr[i], end = " ")# Driver codeif __name__ == '__main__': arr = [8, 255, 16, 2, 4, 0] n = len(arr) k = 2 p = 0 sortWithRemainderP(arr, n, k, p) # This code is contributed by# Sahil_Shelangia |
C#
// C# program for sorting array elements // whose modulo with K yields P using System;using System.Collections.Generic;class GFG {// Function to sort elements // whose modulo with K yields P static void sortWithRemainderP(int []arr, int n, int k, int p) { // initialise two vectors List<int> v1 = new List<int>(); List<int> v2 = new List<int>(); for (int i = 0; i < n; i++) { if (arr[i] % k == p) { // first vector contains indices of // required element v1.Add(i); // second vector contains // required elements v2.Add(arr[i]); } } // sorting the elements in second vector v2.Sort(); // replacing the elements whose modulo with // K yields P with the sorted elements for (int i = 0; i < v1.Count; i++) arr[v1[i]] = v2[i]; // printing the new sorted array elements for (int i = 0; i < n; i++) Console.Write(arr[i] + " ");} // Driver code public static void Main(String[] args) { int []arr = { 8, 255, 16, 2, 4, 0 }; int n = arr.Length; int k = 2; int p = 0; sortWithRemainderP(arr, n, k, p);}}// This code is contributed by PrinciRaj1992 |
PHP
<?php// PHP program for sorting array elements// whose modulo with K yields P// Function to sort elements// whose modulo with K yields Pfunction sortWithRemainderP($arr, $n, $k, $p){ // initialise two vectors $v1 = array(); $v2 = array(); for ($i = 0; $i < $n; $i++) { if ($arr[$i] % $k == $p) { // first vector contains indices of // required element array_push($v1, $i); // second vector contains // required elements array_push($v2, $arr[$i]); } } // sorting the elements in second vector sort($v2); // replacing the elements whose modulo with K // yields P with the sorted elements for ($i = 0; $i < count($v1); $i++) $arr[$v1[$i]] = $v2[$i]; // printing the new sorted array elements for ($i = 0; $i < $n; $i++) echo $arr[$i] . " ";}// Driver code$arr = array( 8, 255, 16, 2, 4, 0 );$n = count($arr);$k = 2;$p = 0;sortWithRemainderP($arr, $n, $k, $p);// This code is contributed by mits?> |
Javascript
<script>// Javascript program for sorting array elements// whose modulo with K yields P// Function to sort elements// whose modulo with K yields Pfunction sortWithRemainderP(arr, n, k, p){ // initialise two vectors var v1 = [], v2 = []; for (var i = 0; i < n; i++) { if (arr[i] % k == p) { // first vector contains indices of // required element v1.push(i); // second vector contains // required elements v2.push(arr[i]); } } // sorting the elements in second vector v2.sort((a,b)=> a-b) // replacing the elements whose modulo with K yields P // with the sorted elements for (var i = 0; i < v1.length; i++) arr[v1[i]] = v2[i]; // printing the new sorted array elements for (var i = 0; i < n; i++) document.write( arr[i] + " ");}// Driver codevar arr = [8, 255, 16, 2, 4, 0 ];var n = arr.length;var k = 2;var p = 0;sortWithRemainderP(arr, n, k, p);</script> |
Output
0 255 2 4 8 16
Time Complexity: O(nlogn)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
