Imprima índices en orden no decreciente de cocientes de elementos de array en la división por X

Dada una array arr[] que consiste en N enteros y un entero X , la tarea es realizar una división de enteros en los elementos de la array por X e imprimir los índices de la array en orden no decreciente de sus cocientes obtenidos.

Ejemplos:

Entrada: N = 3, X = 3, order[] = {2, 7, 4}
Salida: 1 3 2
Explicación:
Después de dividir los elementos del arreglo por 3, el arreglo se modifica a {0, 2, 1}. Por lo tanto, el orden de salida requerido es 1 3 2.

Entrada: N = 5, X = 6, order[] = {9, 10, 4, 7, 2}
Salida: 3 5 1 2 4
Explicación:
Después de dividir los elementos del arreglo por 6, los elementos del arreglo se modifican a 1 1 0 1 0. Por lo tanto, la secuencia requerida es 3 5 1 2 4.

Enfoque: siga los pasos a continuación para resolver el problema: 
 

• Atraviesa la array
• Inicializar un vector de pares .
• Para cada elemento de la array, almacene el valor del cociente obtenido después de la división por X como el primer elemento del par en el vector y el segundo elemento como la posición del número entero en el orden requerido.
• Después del recorrido, ordene el vector y finalmente imprima todos los segundos elementos de los pares.
   

A continuación se muestra la implementación del enfoque anterior:

// 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 X
void 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 Code
int main()
{
 
    int N = 3, X = 3;
    int order[] = { 2, 7, 4 };
    printOrder(order, N, X);
 
    return 0;
}

/*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 program for the above approach
 
# Function to print the order of array
# elements generating non-decreasing
# quotient after division by X
def 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 Code
if __name__ == '__main__':
 
    N, X = 3, 3
    order = [2, 7, 4]
    printOrder(order, N, X)
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
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
    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 Code
public static void Main()
{
    int N = 3, X = 3;
    int[] order = { 2, 7, 4 };
    printOrder(order, N, X);
}
}
 
// This code is contributed by code_hunt.

<script>
 
// Javascript program for the above approach
 
// Function to print the order of array
// elements generating non-decreasing
// quotient after division by X
function 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 Code
let N = 3, X = 3;
let order = [ 2, 7, 4 ];
 
printOrder(order, N, X);
 
// This code is contributed by unknown2108
 
</script>

1 3 2

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)