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)**

Comments and Discussions!