Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
C++ Implementation
3.1.1.
Input
3.1.2.
Output
3.2.
Complexities
3.2.1.
Time complexity
3.2.2.
Space complexity
4.
Frequently Asked Questions
4.1.
What are queues in data structure?
4.2.
What are the different types of queues in data structure?
4.3.
Write the different applications of queue data structure.
4.4.
Why do we need an array?
4.5.
How to get the front element of a queue?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find the Index of the Array Elements after Performing given Operations K Times

Author Shreya Deep
0 upvote
Queue

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 out. Just the knowledge of arrays and some basic data structures will do the work. A prerequisite 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 gotten 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;
    }
}
You can also try this code with Online C++ Compiler
Run Code

Input

6 //n
2,5,6,8,10,11 //a
2 //k
You can also try this code with Online C++ Compiler
Run Code

Output

2 3 4 5 0 1
You can also try this code with Online C++ Compiler
Run Code

Complexities

Time complexity

O(max(n,k)), where k= number of operations to be performed and n = the 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

The Space Complexity is O(n), where n = the number of elements in the array.

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

Read about Application of Queue in Data Structure here.

Frequently Asked Questions

What are queues in data structure?

A queue is a linear data structure that follows the FIFO (first in, first out) property.

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.

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.

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.

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.

Check out this problem - First And Last Occurrences Of X

Conclusion

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 queue, reversing the first k elements of a queue, and implementing of Queue

Recommended Readings:

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Live masterclass