Build Array of length N such that exactly X Subarrays have positive sums
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:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to print an array of size n // such that x subarrays has positive // sums while other subarrays has // negative sums void xsubarrays( int n, int x) { bool flag = false ; // if x is 0, initially if (x == 0) { flag = true ; } int arr[n]; // iterating from 0 to n-1 for ( int i = 0; i < n; i++) { // if flag is true if (flag) { // if x is greater than 1 if (x > 1) { // Then assign -1 to arr[i] arr[i] = -1; // Reduce x by 1 x -= 1; } // If x is less than or // equal to 1 else { // Then assign -2 to arr[i] arr[i] = -2; } } // If x is greater or equal to // (n-i) else if (x >= n - i) { // Assign 2*n to arr[i] arr[i] = n * 2; // Reduce x by (n-i) x -= (n - i); // If x is 0 at that point if (x == 0) { // Assign flag to true flag = true ; } } // if x is less than (n-i) else { // Assign x to arr[i] arr[i] = x; // Assign flag to true flag = true ; } } // Print th final array arr[] for ( int i = 0; i < n; i++) { cout << arr[i] << " " ; } cout << endl; } // Drive code int main() { int n = 5, x = 8; // Function call xsubarrays(n, x); return 0; } |
Java
// Java Code for the above approach: import java.util.*; public class Main { // Function to print an array of size n // such that x subarrays has positive // sums while other subarrays has // negative sums static void xsubarrays( int n, int x) { boolean flag = false ; // if x is 0, initially if (x == 0 ) { flag = true ; } int [] arr = new int [n]; // iterating from 0 to n-1 for ( int i = 0 ; i < n; i++) { // if flag is true if (flag) { // if x is greater than 1 if (x > 1 ) { // Then assign -1 to arr[i] arr[i] = - 1 ; // Reduce x by 1 x -= 1 ; } // If x is less than or // equal to 1 else { // Then assign -2 to arr[i] arr[i] = - 2 ; } } // If x is greater or equal to // (n-i) else if (x >= n - i) { // Assign 2*n to arr[i] arr[i] = n * 2 ; // Reduce x by (n-i) x -= (n - i); // If x is 0 at that point if (x == 0 ) { // Assign flag to true flag = true ; } } // if x is less than (n-i) else { // Assign x to arr[i] arr[i] = x; // Assign flag to true flag = true ; } } // Print th final array arr[] for ( int i = 0 ; i < n; i++) { System.out.print(arr[i] + " " ); } System.out.println(); } // Drive code public static void main(String[] args) { int n = 5 , x = 8 ; // Function call xsubarrays(n, x); } } |
Python3
# Python coe for the above approach: def xsubarrays(n, x): flag = False # if x is 0, initially if x = = 0 : flag = True arr = [ 0 ] * n # iterating from 0 to n-1 for i in range (n): # if flag is true if flag: # if x is greater than 1 if x > 1 : # Then assign -1 to arr[i] arr[i] = - 1 # Reduce x by 1 x - = 1 # If x is less than or equal to 1 else : # Then assign -2 to arr[i] arr[i] = - 2 # If x is greater or equal to (n-i) elif x > = n - i: # Assign 2*n to arr[i] arr[i] = n * 2 # Reduce x by (n-i) x - = (n - i) # If x is 0 at that point if x = = 0 : # Assign flag to true flag = True # if x is less than (n-i) else : # Assign x to arr[i] arr[i] = x # Assign flag to true flag = True # Print the final array arr[] print ( * arr) # Drive code n = 5 x = 8 # Function call xsubarrays(n, x) |
C#
// c# code for the above approach: using System; class GFG { // Function to print an array of size n // such that x subarrays has positive // sums while other subarrays has // negative sums static void XSubarrays( int n, int x) { bool flag = false ; // if x is 0, initially if (x == 0) { flag = true ; } int [] arr = new int [n]; // iterating from 0 to n-1 for ( int i = 0; i < n; i++) { // if flag is true if (flag) { // if x is greater than 1 if (x > 1) { // Then assign -1 to arr[i] arr[i] = -1; // Reduce x by 1 x -= 1; } // If x is less than or equal to 1 else { // Then assign -2 to arr[i] arr[i] = -2; } } // If x is greater or equal to (n-i) else if (x >= n - i) { // Assign 2*n to arr[i] arr[i] = n * 2; // Reduce x by (n-i) x -= (n - i); // If x is 0 at that point if (x == 0) { // Assign flag to true flag = true ; } } // if x is less than (n-i) else { // Assign x to arr[i] arr[i] = x; // Assign flag to true flag = true ; } } // Print the final array arr[] for ( int i = 0; i < n; i++) { Console.Write(arr[i] + " " ); } Console.WriteLine(); } // Driver code static void Main() { int n = 5, x = 8; // Function call XSubarrays(n, x); } } |
Javascript
// Function to print an array of size n // such that x subarrays has positive // sums while other subarrays has // negative sums function xsubarrays(n, x) { let flag = false ; // if x is 0, initially if (x === 0) { flag = true ; } let arr = []; // iterating from 0 to n-1 for (let i = 0; i < n; i++) { // if flag is true if (flag) { // if x is greater than 1 if (x > 1) { // Then assign -1 to arr[i] arr[i] = -1; // Reduce x by 1 x -= 1; } // If x is less than or // equal to 1 else { arr[i] = -2; } } // If x is greater or equal to // (n-i) else if (x >= n - i) { arr[i] = n * 2; x -= (n - i); if (x === 0) { flag = true ; } } // if x is less than (n-i) else { arr[i] = x; flag = true ; } } // Print th final array arr[] for (let i = 0; i < n; i++) { console.log(arr[i] + " " ); } console.log(); } // Function call let n = 5, x = 8; xsubarrays(n, x); |
10 3 -1 -1 -2
Time Complexity: O(N)
Auxiliary Space: O(N)