Dada una array arr[] y un entero K , la tarea es imprimir la posición de los elementos de la array, donde el i -ésimo valor en el resultado es el índice del i -ésimo elemento en la array original después de aplicar las siguientes operaciones exactamente K veces :
- Elimine el primer elemento de la array y disminuya en 1 .
- Si es mayor que 0 después de disminuir, colóquelo al final de la array y cambie la posición de los elementos a la izquierda.
Ejemplos:
Entrada: arr[] = {3, 1, 3, 2}, K = 4
Salida: {0, 2, 3}
Explicación:
Operación 1 -> arr[] = {3, 1, 3, 2} (posición { 0, 1, 2, 3}) -> {1, 3, 2, 2} (posición {1, 2, 3, 0}).
Operación 2 -> arr[] = {1, 3, 2, 2} (posición {1, 2, 3, 0})-> {3, 2, 2} (posición {2, 3, 0}), ya que el primer elemento se convirtió en cero.
Operación 3 -> arr[] = {3, 2, 2} (posición {2, 3, 0}) -> {2, 2, 2} (posición {3, 0, 2}).
Operación 4 -> ar[] = {2, 2, 2} (posición {3, 0, 2}) -> {2, 2, 1} (posición {0, 2, 3}).Entrada: arr[] = {1, 2, 3}, K = 3
Salida: {1, 2}
Explicación:
Operación 1 -> arr[] = {1, 2, 3} (posición {0, 1, 2} ) -> {2, 3} (posición {1, 2}).
Operación 2 -> arr[] = {2, 3} (posición {1, 2}) -> {3, 1} (posición {2, 1}), ya que el primer elemento se convirtió en cero.
Operación 3 -> arr[] = {3, 1} (posición {2, 1}) -> {1, 2} (posición {1, 2}).
Enfoque: La idea es utilizar una cola para simular las operaciones K. Siga los pasos a continuación para resolver el problema:
- Inicialice una cola para almacenar los pares de {arr[i], i} .
- Iterar sobre el rango [0, K – 1] y realizar las siguientes operaciones:
- Haga estallar el elemento frontal de la Cola y disminuya su valor en 1 .
- Vuelva a colocar el elemento actualizado en la cola.
- Utilice el segundo miembro del par para imprimir la posición de los elementos extrayéndolos hasta que la cola esté vacía.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print position of array // elements after performing given // operations exactly K times void findElementPositions(int arr[], int N, int K) { // make the queue of pairs queue<pair<int, int> > que; // Convert the array // to queue of pairs for (int i = 0; i < N; i++) { que.push({ arr[i], i }); } // Perform the operations // for K units of time for (int i = 0; i < K; i++) { // get the front pair pair<int, int> value = que.front(); // If the first element // value is one if (value.first == 1) { que.pop(); } // Otherwise else { que.pop(); value.first -= 1; que.push(value); } } // Print all the positions // after K operations while (!que.empty()) { pair<int, int> value = que.front(); que.pop(); cout << value.second << " "; } } // Driven Program int main() { // Given array int arr[] = { 3, 1, 3, 2 }; // Stores the length of array int N = sizeof(arr) / sizeof(arr[0]); // Given value of K int K = 4; // Function call findElementPositions(arr, N, K); return 0; } // This code is contributed by Kingash.
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to print position of array // elements after performing given // operations exactly K times static void findElementPositions(int arr[], int N, int K) { // make the queue of pairs ArrayDeque<int[]> que = new ArrayDeque<>(); // Convert the array // to queue of pairs for (int i = 0; i < N; i++) { que.addLast(new int[] { arr[i], i }); } // Perform the operations // for K units of time for (int i = 0; i < K; i++) { // get the front pair int value[] = que.peekFirst(); // If the first element // value is one if (value[0] == 1) { que.pollFirst(); } // Otherwise else { que.pollFirst(); value[0] -= 1; que.addLast(value); } } // Print all the positions // after K operations while (!que.isEmpty()) { int value[] = que.pollFirst(); System.out.print(value[1] + " "); } } // Driver code public static void main(String[] args) { // Given array int arr[] = { 3, 1, 3, 2 }; // length of the array int N = arr.length; // Given value of K int K = 4; // Function call findElementPositions(arr, N, K); } } // This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to print position of array # elements after performing given # operations exactly K times def findElementPositions(que, K): # Convert the queue # to queue of pairs for i in range(len(que)): que[i] = [que[i], i] # Perform the operations # for K units of time for i in range(K): # If the first element # value is one if que[0][0] == 1: que.pop(0) # Otherwise else: temp = que.pop(0) temp[0] -= 1 que.append(temp) # All the positions # after K operations ans = [i[1] for i in que] # Print the answer print(ans) # Given array arr = [3, 1, 3, 2] # Given value of K K = 4 findElementPositions(arr, K)
C#
// C# program for the above approach using System; using System.Collections; class GFG { // Function to print position of array // elements after performing given // operations exactly K times static void findElementPositions(int[] arr, int N, int K) { // make the queue of pairs Queue que = new Queue(); // Convert the array // to queue of pairs for (int i = 0; i < N; i++) { que.Enqueue(new Tuple<int,int>(arr[i], i)); } // Perform the operations // for K units of time for (int i = 0; i < K; i++) { // get the front pair Tuple<int,int> value = (Tuple<int,int>)que.Peek(); // If the first element // value is one if (value.Item1 == 1) { que.Dequeue(); } // Otherwise else { que.Dequeue(); value = new Tuple<int,int>(value.Item1-1, value.Item2); que.Enqueue(value); } } // Print all the positions // after K operations Console.Write("["); while (que.Count > 0) { Tuple<int,int> value = (Tuple<int,int>)que.Peek(); que.Dequeue(); if(que.Count > 0) { Console.Write(value.Item2 + ", "); } else{ Console.Write(value.Item2); } } Console.Write("]"); } // Driver code static void Main() { // Given array int[] arr = { 3, 1, 3, 2 }; // Stores the length of array int N = arr.Length; // Given value of K int K = 4; // Function call findElementPositions(arr, N, K); } } // This code is contributed by rameshtravel07
Javascript
<script> // Javascript program for the above approach // Function to print position of array // elements after performing given // operations exactly K times function findElementPositions(arr, N, K) { // make the queue of pairs let que = []; // Convert the array // to queue of pairs for (let i = 0; i < N; i++) { que.push([ arr[i], i ]); } // Perform the operations // for K units of time for (let i = 0; i < K; i++) { // get the front pair let value = que[0]; // If the first element // value is one if (value[0] == 1) { que.shift(); } // Otherwise else { que.shift(); value[0] -= 1; que.push(value); } } // Print all the positions // after K operations document.write("["); while (que.length > 0) { let value = que[0]; que.shift(); if(que.length > 0) { document.write(value[1] + ", "); } else{ document.write(value[1]); } } document.write("]"); } // Given array let arr = [ 3, 1, 3, 2 ]; // Stores the length of array let N = arr.length; // Given value of K let K = 4; // Function call findElementPositions(arr, N, K); // This code is contributed by mukesh07. </script>
[0, 2, 3]
Complejidad de tiempo: O(max(N, K))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA