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