Home » Interview coding problems/challenges

Constructing the Array

Constructing the Array: Here, we are going to find the solution of this problem, it has been asked in codeforces div 3, round 642, the concept used in problem has been featured in interview round of many companies.
Submitted by Divyansh Jaipuriyar, on June 24, 2020

Problem statement

You are given an array a of length n consisting of zeros. You perform n actions with this array: during the i-th action, the following sequence of operations appears:

Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one;

Let this segment be [l;r]. If r-l+1 is odd (not divisible by 2) then assign (set) a[(l+r)/2]:=i (where i is the number of the current action), otherwise (if r-l+1 is even) assign (set) a[(l+r-1)/2]:=i.

Input

The first line of the input contains one integer t (1≤t≤10^4) — the number of test cases. Then t test cases follow.

The only line of the test case contains one integer n (1≤n≤2⋅10^5) — the length of a.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5 (∑n≤2⋅10^5).

Output

For each test case, print the answer — the array a of length n after performing n actions described in the problem statement. Note that the answer exists and unique.

Examples

Consider the array a of length 5 
(initially a=[0,0,0,0,0]). Then it changes as follows:

Firstly, 
    we choose the segment [1;5] and 
    assign a[3]:=1, so a becomes [0,0,1,0,0];
then 
    we choose the segment [1;2] and 
    assign a[1]:=2, so a becomes [2,0,1,0,0];
then
    we choose the segment [4;5] and 
    assign a[4]:=3, so a becomes [2,0,1,3,0];
then 
    we choose the segment [2;2] and 
    assign a[2]:=4, so a becomes [2,4,1,3,0];
and at last 
    we choose the segment [5;5] and 
    assign a[5]:=5, so a becomes [2,4,1,3,5].

Problem source: https://codeforces.com/contest/1353/problem/D

Solution Approach

We will use the heap data structure to solve this problem (we will use max heap), since the problem is to assign count variable i, we will create priority queue with pair, the first part of the pair is the size of subarray and the second part of the pair is another pair which contains indices l and r, left index and right index of the subarray.

A/c to the question if the size of the left and right subarray with the equal number of 0s in them we have to choose the left part, so to solve the problem we multiply the indexes with -1 so that left part is chosen.

While a priority queue is not empty, we pick the max element from the top of the priority queue and pop it from the priority queue.

Now, l=be the left index of the subarray and r be the right index of the subarray. We take the mid index as (l+r)/2 and fill it with cnt and increment it with one each time. If l==r then there is no possibility of partition among it so simply continue, else one part will be the subarray of l to mid-1 and the other part will be mid+1 to r with length (mid-l) and (r-mid) respectively.

Push them with their respective length and indices into the priority queue.

We repeat the process untill the priority queue is not empty.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll arr[200005];

// solve function to solve the entire problem which 
// takes n as the parameter,n is size of the array arr[].
void solve(ll n)
{
    // priority queue as our max heap
    priority_queue<pair<ll, pair<ll, ll> > > pq; 
    // Here, pq with pair of len and pair of 
    // indices as its elements.
    
    // base case as len of entire array as first input 
    // from index 1 to n but its multiplied with -1 
    // so that left sub-array can be chosen if len of two 
    // sub-arrays are equals.
    pq.push({ n, { -1, -n } });
    
    // initialise count as 1.
    ll cnt = 1;
    
    // if priority_queue is not empty 
    // then do the following operation.
    while (!pq.empty()) {
        // declare pair
        pair<ll, pair<ll, ll> > p = pq.top();
        pq.pop();
        ll l = p.second.first * (-1); // initialize left index
        ll r = p.second.second * (-1); // initialise right index
        ll mid = (l + r) / 2; // take mid index of the sub-array
        arr[mid] = cnt; // assign cnt value to mid index.
        cnt++; // increment count variable.

        // base case condition if only single element is present.
        if (l == r)
            continue;
        else {
            // declare left subarray
            if ((mid - 1) >= 0 and (mid - 1) >= l) {
                ll len = mid - l; // len of left sub-array
                pq.push({ len, { (-1) * l, (-1) * (mid - 1) } });
            }
            // declare right sub-array
            if ((mid + 1) <= n and (mid + 1) <= r) {
                ll len = r - mid; // len of right sub-array
                pq.push({ len, { (-1) * (mid + 1), (-1) * r } });
            }
        }
    }
    
    // iterate through final result array.
    for (ll i = 1; i <= n; i++)
        cout << arr[i] << " ";
    cout << "\n";
}

int main()
{
    ll t;
    
    cout << "Enter number of test cases: ";
    cin >> t;
    
    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;
    
        // call solve function.
        solve(n);
    }
    
    return 0;
}

Output

Enter number of test cases: 4
Enter size of array: 5
2 4 1 3 5 
Enter size of array: 4
3 1 2 4 
Enter size of array: 9
6 2 4 7 1 8 3 5 9 
Enter size of array: 3
2 1 3 

• Time Complexity for the above approach: O(nlogn)
• space Complexity for the above approach: O(n)