Given an array order[] consisting of N integers and an integer X, the task is to perform integer division on the array elements by X and print the indices of the array in non-decreasing order of their quotients obtained.
Examples:
Input: N = 3, X = 3, order[] = {2, 7, 4}
Output: 1 3 2
Explanation:
After dividing the array elements by 3, the array modifies to {0, 2, 1}. Therefore, required order of output is 1 3 2.Input: N = 5, X = 6, order[] = {9, 10, 4, 7, 2}
Output: 3 5 1 2 4
Explanation:
After dividing the array elements by 6, the array elements modify to 1 1 0 1 0. Therefore, the required sequence is 3 5 1 2 4.
Approach: Follow the steps below to solve the problem:
- Traverse the array
- Initialize a vector of pairs.
- For each array element, store the value of the quotient obtained after division by X as the first element of the pair in the vector and the second element as the position of the integer in the required order.
- After the traversal, sort the vector and then finally print all the second elements of the pairs.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the order of array// elements generating non-decreasing// quotient after division by Xvoid printOrder(int order[], int N, int X){ // Stores the quotient and the order vector<pair<int, int> > vect; // Traverse the array for (int i = 0; i < N; i++) { if (order[i] % X == 0) { vect.push_back({ order[i] / X, i + 1 }); } else { vect.push_back({ order[i] / X + 1, i + 1 }); } } // Sort the vector sort(vect.begin(), vect.end()); // Print the order for (int i = 0; i < N; i++) { cout << vect[i].second << " "; } cout << endl;}// Driver Codeint main(){ int N = 3, X = 3; int order[] = { 2, 7, 4 }; printOrder(order, N, X); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { // Function to print the order of array // elements generating non-decreasing // quotient after division by X static void printOrder(int order[], int N, int X) { // Stores the quotient and the order ArrayList<int[]> vect = new ArrayList<>(); // Traverse the array for (int i = 0; i < N; i++) { if (order[i] % X == 0) { vect.add(new int[] { order[i] / X, i + 1 }); } else { vect.add( new int[] { order[i] / X + 1, i + 1 }); } } // Sort the vector Collections.sort(vect, (a, b) -> a[0] - b[0]); // Print the order for (int i = 0; i < N; i++) { System.out.print(vect.get(i)[1] + " "); } System.out.println(); } // Driver Code public static void main(String args[]) { int N = 3, X = 3; int order[] = { 2, 7, 4 }; printOrder(order, N, X); }}// This code is contributed by hemanth gadarla |
Python3
# Python3 program for the above approach# Function to print the order of array# elements generating non-decreasing# quotient after division by Xdef printOrder(order, N, X): # Stores the quotient and the order vect = [] # Traverse the array for i in range(N): if (order[i] % X == 0): vect.append([order[i] // X, i + 1]) else: vect.append([order[i] // X + 1,i + 1]) # Sort the vector vect = sorted(vect) # Print the order for i in range(N): print(vect[i][1], end = " ") # Driver Codeif __name__ == '__main__': N, X = 3, 3 order = [2, 7, 4] printOrder(order, N, X)# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG {// Function to print the order of array// elements generating non-decreasing// quotient after division by Xstatic void printOrder(int[] order, int N, int X){ // Stores the quotient and the order List<Tuple<int, int>> vect = new List<Tuple<int, int>>(); // Traverse the array for (int i = 0; i < N; i++) { if (order[i] % X == 0) { vect.Add(new Tuple<int,int>((order[i] / X), i + 1)); } else { vect.Add(new Tuple<int,int>((order[i] / X + 1), i + 1)); } } // Sort the vector vect.Sort(); // Print the order for (int i = 0; i < N; i++) { Console.Write(vect[i].Item2 + " "); } Console.WriteLine();}// Driver Codepublic static void Main(){ int N = 3, X = 3; int[] order = { 2, 7, 4 }; printOrder(order, N, X);}}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript program for the above approach// Function to print the order of array// elements generating non-decreasing// quotient after division by Xfunction printOrder(order, N, X){ // Stores the quotient and the order let vect = []; // Traverse the array for(let i = 0; i < N; i++) { if (order[i] % X == 0) { vect.push([ order[i] / X, i + 1 ]); } else { vect.push([ order[i] / X + 1, i + 1 ]); } } // Sort the vector vect.sort(function(a, b){return a[0] - b[0]}); // Print the order for(let i = 0; i < N; i++) { document.write(vect[i][1] + " "); } document.write();}// Driver Codelet N = 3, X = 3;let order = [ 2, 7, 4 ];printOrder(order, N, X);// This code is contributed by unknown2108</script> |
Output:
1 3 2
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
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!
