Editorial
Setter: Vanshika Batra
Tester: Mohit Yadav
Editorial: Tanmay
PROBLEM NAME : Almirah Key
DIFFICULTY : Easy
PREREQUISITES : Two Pointer Approach
PROBLEM : Your college roommate has gone to his hometown. He urgently requires the copy of some important documents kept in his almirah and the problem is that his almirah is locked. The lock accepts a numerical pattern, but he doesn’t completely recall the code. He gave you partial information via call regarding what he thinks can be his code. You’re provided with N - the length of the numerical code and all the digits which were present in the code. According to him, the code he provided was partially correct, that is he ensures that the zeroes are placed at the correct place but not sure of the order of the digits. He has a strong feeling that the actual key might be the reverse of the code provided by him. Being his roommate, he needs your help in unlocking the almirah and sending the click of the documents he required in the least possible time.
TASK: Determine the almirah’s code.
CONSTRAINTS :
1 <= T <= 10^4
1 <= N <= 10^5
0 <= A[i] <= 9
SAMPLE INPUT (1) :
1
5
1 0 4 0 2
SAMPLE OUTPUT (1) :
20401
SAMPLE INPUT (2) :
2
2
5 0
7
9 0 0 1 1 0 2
SAMPLE OUTPUT (2) :
50
2001109
EXPLANATION :
Declare two pointers (i, j) to the array’s beginning and ending.
Our goal is to reverse the array without reordering or relocating the 0s.
Iterate over the provided array, decreasing the end pointer if the starting pointer arrives on a ‘0’.
We follow the same method with the end pointer. The sole change is that the start pointer is ‘increased.’
If this isn’t the case, we swap the elements on the pointers and increase the starting pointer and decrease the end pointer with each iteration.
SOLUTION:
#include
using namespace std;
int *reversee(int arr[],int n){
for(int i=0,j=n-1;i<j;i++,j–){
if(arr[i]==0) j++;
else if(arr[j]==0) i–;
else{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
return arr;
}
int main(){
int t,n;
cin>>t;
while(t–){
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int p=reversee(arr,n);
for(int i=0;i<n;i++){
cout<<(p+i);
}
}
return 0;
}
OPTIMAL COMPLEXITY :
Time - O(N)
Space - O(1)