Given an array arr[] and an integer K. The task is to sort the elements that are in between any two multiples of K.
Examples:
Input: arr[] = {2, 1, 13, 3, 7, 8, 21, 13, 12}, K = 2
Output: 2 1 3 7 13 8 13 21 12
The multiples of 2 in the array are 2, 8 and 12.
The elements that are in between the first two multiples of 2 are 1, 13, 3 and 7.
Hence, these elements in sorted order are 1, 3, 7 and 13.
Similarly, the elements between 8 and 12 in sorted order will be 13 and 21.Input: arr[] = {11, 10, 9, 7, 4, 5, 12, 22, 13, 15, 17, 16}, K = 3
Output: 11 10 9 4 5 7 12 13 22 15 17 16
Approach: Traverse the array and keep track of the multiples of K, starting from the 2nd multiple of K sort every element between the current and the previous multiple of K. Print the updated array at the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include<bits/stdc++.h>using namespace std;// Utility function to print// the contents of an arrayvoid printArr(int arr[], int n){ for (int i = 0; i < n; i++) cout << (arr[i]) << " ";}// Function to sort elements// in between multiples of kvoid 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 codeint 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 approachimport 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 arraydef printArr(arr, n) : for i in range(n) : print(arr[i], end = " ");# Function to sort elements# in between multiples of kdef 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 codeif __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 arrayfunction printArr(arr, n){ for (var i = 0; i < n; i++) document.write(arr[i] + " ");}// Function to sort elements// in between multiples of kfunction 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 codevar arr = [2, 1, 13, 3, 7, 8, 21, 13, 12];var n = arr.length;var k = 2;sortArr(arr, n, k);</script> |
Output:
2 1 3 7 13 8 13 21 12
Time Complexity: O(n2*log(n))
Auxiliary Space: O(1)
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!
