Find the index of the array elements after performing given operations k times

Shreya Deep
Last Updated: May 13, 2022

Introduction

In this article, we will find out how to find the index of the array elements after performing some operation k times. These kinds of problems don’t need a lot of logic to be thought. Just the knowledge of arrays and some basic data structures will do the work. A pre-requisite for solving this problem is the knowledge of arrays and queues. For more information on these data structures, you can refer to these: arrays and queues

Without any further ado, let’s move on to the problem statement and solution approach.

Problem Statement

Given an array of n elements and an integer k, you are required to print the index of the array elements after doing operations on it k times. The operation is:

  • Remove the first element of the array and decrement it by 1.
  • If the value after decrement is greater than 0, push it to the back of the array and shift all the other elements by 1 to the left side.


Note: In the output array, the ith value denotes the index of the ith element of the original array after doing k operations on it. Also, you need to find the index for the existing elements only and not the ones which are not in the array after the k operations.

Solution Approach

The solution approach is quite simple. You might have got the idea a bit. Since we need to shift all the other elements to the left by one and also push the front element if after decrementing it is greater than 1, we get an intuition that a queue should be used. So, while doing the operations, we will do it on a queue rather than an array. 

Steps are:

  • Input the number of elements in the Queue, n, and the value of k.
  • Input the n numbers in an array.
  • Push the elements in a queue of pairs, q, along with their indexes. 
  • Run a loop for k times. In each iteration of this for loop,
    • Check if the Queue is empty. If yes, break out of the loop.
    • Pop-out the front element of the Queue. Decrement the first element of the front element by 1. If the value is still greater than 0, push this pair back in the Queue. Else, continue to the next iteration.
  • After the loop ends, either the Queue will be empty, there will be some elements in it. If the Queue is empty, print (“Array becomes empty”). Otherwise, print the second elements of each element of the Queue.

C++ implementation

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n; // Input the number of elements in the array
    int a[n]; // Declare the array for storing the n numbers
    int k;
    cin>>k; // Input the value of k
    queue<pair<int,int>>q; // Declare the queue of pairs
    for(int i=0;i<n;i++){
       cin>>a[i]; // Input the numbers of the array one by one
       q.push({a[i],i}); // Push the numbers along with their indices into the //queue.
    }
    for(int i=0;i<k;i++){
       // for each of the k operations
       if(q.empty()){ // Check if the queue is empty. If yes, break out of the //loop as we can't do any more operations
           break;
       }
       else{
           pair<int,int> x = q.front(); // Store the front element of the queue //and pop it out.
           q.pop();
           int u = x.first; 
           u--; // Decrement the first element of the front as it is the number
           if(u>0){ // If after decrementing, the value is greater than 0, push //the pair at the back of the queue.
               q.push({u,x.second});
           }
       }
    }
    if(q.empty()){ // If the queue becomes empty, print ARRAY BECOMES EMPTY
       cout<<"ARRAY BECOMES EMPTY"<<endl;
    }
    else{
       while(!q.empty()){ // Else, print out the indices one by one by printing //the second element of the queue front
           cout<<q.front().second<<" ";
           q.pop();
       }
       cout<<endl;
    }
}

Input

6 //n
2,5,6,8,10,11 //a
2 //k

Output

2 3 4 5 0 1

Complexities

Time complexity

O(max(n,k)), where k= number of operations to be performed and n = number of elements in the array.

Reason: We use one loop of length k whose time complexity will be O(k). And in the end, we have one loop to print the indexes which is of length equal to the number of elements present in the queue. Since, in the worst case, the maximum number of elements present in the queue can be equal to n, so the time complexity of printing the indexes is O(n). 
Hence, the total time complexity is equal to O(k)+O(n) which is approximately O(max(n,k)).
 

Space complexity

O(n), where n = number of elements in the array.

Reason: we’re storing the numbers in the array and the Queue. Both take O(n) space.

Frequently asked questions

  1. What are queues in data structure?
    A queue is a linear data structure that follows the FIFO (first in, first out) property.
     
  2. What are the different types of queues in data structure?
    There are four types of queues – simple/linear Queue, Circular Queue, priority queue, and double-ended Queue.
     
  3. Write the different applications of queue data structure?
    Queues are applied in places where data has to be stored but not processed immediately. Some examples include – CPU scheduling, printer queue, phone calling system, etc.
     
  4. Why do we need an array?
    Elements in an array can be accessed very easily. They are best to use when we need to store multiple values of the same type.
     
  5. How to get the front element of a queue?
    We use the in-built function q.front() to get the front element of the Queue.

Key Takeaways

In this article, we discussed the problem of finding the index of the array elements after performing given operations k times. A major takeaway from this problem is the implementation of the idea using a queue data structure. This problem tells you how to use the queue functions efficiently. Some more problems based on the queue data structure are: reversing a queuereverse the first k elements of a queue, and implementation of Queue

You can try these out to gain more confidence on this topic. These questions are asked during various coding contests as well as placements tests.

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think