Given integers N and X, the task is to construct an array of size N such that exactly X subarrays have positive sums and other subarrays have negative sums.

Note: If multiple subarrays are possible, print any of them.

Examples:

Input: N = 3, X = 2
Output: 2 -1 -2
Explanation: [0, 0] and [0, 1] subarrays have positive sums while other subarrays have negative sums.

Input: N = 5, X = 8
Output: 10 3 -1 -1 -2
Explanation: Any subarray starting with index 1 has positive sum and subarray [2, 2], [2, 3], [2, 4] has also positive sum while others subarrays has negative sums

Approach: To solve the problem follow the below idea:

We will iterate from i = 0 to n-1 and will do the following to build the array (say a[]):

• If X ≥ N – i Then we will assign 2N to a[i] and reduce X = X – (N – i) because we will assign a[i+1] to a[n-1] ≥ -2, so we can make positive sum (N – i) subarrays and 
• If X ≤ N – i then we will assign X to a[i] and we will assign -1 to index [i+1, i+(X-1)]. This will make exactly X positive sum subarrays because we will assign -2 to in the range [i+X, N-1].

Illustration:

Follow the below illustration for a better understanding:

Consider  N = 5, X = 8

• We will start iterating from index 0 to n-1( we are using 0-based indexing here).
• At index 0,  X ≥ N-i, so we will assign 2N to index i. and X becomes 8 – (5 – 0) = 3
• At index 1, X < N-i, so we will assign X to a[i].
• Now from the index (1+1 = 2) to (1+3-1) = 3 will be assigned with -1.
  • So at index 2, a[i] = -2.
  • At index 3 also assign -1 to a[i].
• At index 4, it is out of range [2, 3], so all indices from hereafter will have the value -2. Assign -2 to a[i].

Below are the steps to implement the approach:

• First start iterating from index 0 to n-1 ( 0-based indexing ).
  • Assign flag = false if X > 0 and assign flag = true if X = 0.
  • At any index, X ≥ N-i, so we will assign 2N to a[i] and reduce x to x-(n-i) and if X = 0, then assign flag = true.
  • At any index, X < N-i, so we will assign X to a[i] and assign flag=true.
    • If at any index, flag = true and x > 1, then we will assign -1 to a[i] and reduce x to x-1.
    • If at any index, flag = true and X = 1, then we will assign -2 to a[i].
• After iterating, print the final array.

Below is the code for the above approach:

10 3 -1 -1 -2 

Time Complexity: O(N)
Auxiliary Space: O(N)