Problem Statement:
You are given an target and an integer n.
You need to perform push and pop operation to reach the target by using the list from “1, 2, … n”.
Example
Input: target = [1,3], n = 3
Output: [“Push”,”Push”,”Pop”,”Push”]
Read number 1 and do push operation. Current array [1]
Then read number 2 and do push and pop from the array. Current array [1]
Then read number 3 and push the array, current array [1,3]
Solution
We use array to solve this problem.
So for every value that is not present in the target, we do “push” and then “pop”.
If there is a matching value then do “push” opeeration.
Solution in C++
#include <algorithm>
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <list>
using namespace std;
vector<string> build_array(vector<int>& target, int n)
{
vector<string> res;
string ph = "Push";
string pp = "Pop";
int num = 1;
for(int i=0; i<target.size(); i++)
{
while(num!=target[i])
{
num++;
res.push_back("Push");
res.push_back("Pop");
}
res.push_back("Push");
num++;
}
return res;
}
int main()
{
vector<int> target = {1, 3};
int n = 3;
vector<string> result = build_array(target, n);
cout<<"Result is "<<endl;
for (auto i = result.begin(); i != result.end(); ++i)
cout << *i << " ";
cout<<endl;
return 0;
}
Output:
Result is
Push Push Pop Push