Given an array arr[] and an integer K, the task is to print the position of the array elements, where the ith value in the result is the index of the ith element in the original array after applying following operations exactly K times:
- Remove the first array element and decrement it by 1.
- If it is greater than 0 after decrementing, place it at the end of the array and shift the position of the elements to left.
Examples:
Input: arr[] = {3, 1, 3, 2}, K = 4
Output: {0, 2, 3}
Explanation:
Operation 1 -> arr[] = {3, 1, 3, 2} (position {0, 1, 2, 3}) -> {1, 3, 2, 2} (position {1, 2, 3, 0}).
Operation 2 -> arr[] = {1, 3, 2, 2} (position {1, 2, 3, 0})-> {3, 2, 2} (position {2, 3, 0}), since the first element became zero.
Operation 3 -> arr[] = {3, 2, 2} (position {2, 3, 0}) -> {2, 2, 2} (position {3, 0, 2}).
Operation 4 -> ar[] = {2, 2, 2} (position {3, 0, 2}) -> {2, 2, 1} (position {0, 2, 3}).Input: arr[] = {1, 2, 3}, K = 3
Output: {1, 2}
Explanation:
Operation 1 -> arr[] = {1, 2, 3} (position {0, 1, 2}) -> {2, 3} (position {1, 2}).
Operation 2 -> arr[] = {2, 3} (position {1, 2}) -> {3, 1} (position {2, 1}), since the first element became zero.
Operation 3 -> arr[] = {3, 1} (position {2, 1}) -> {1, 2} (position {1, 2}).
Approach: The idea is to use a Queue to simulate the K operations. Follow the steps below to solve the problem:
- Initialize a Queue to store the pairs of {arr[i], i}.
- Iterate over the range [0, K – 1] and perform the following operations:
- Pop the front element of the Queue and decrement its value by 1.
- Push the updated element back into the queue.
- Use the second member of the pair to print the position of the elements by popping out the elements until the queue is empty.
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 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]
Time Complexity: O(max(N, K))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!