Create Array following condition such that exactly M prefixes have positive Sum
You are given two integers N and M (M ≤ N), the task is to create an array of length N following the below-given conditions.
- |Ai| = i, Formally, A[i] will be either -i or i.
- Exactly M prefix arrays should be there, Such that sum of each prefix array should be greater than zero.
Note: If there are multiple arrangements, then output any valid arrangement.
Examples:
Input: N = 3, M = 3
Output: 1 2 3
Explanation: There are Exactly 3 prefix arrays having sum greater than zero, Which are:
First prefix arr[] : {1}, Sum=1
Second prefix arr[] 1: {1, 2}, Sum=1+2=3
Third prefix arr[] = {1, 2, 3}, Sum=1+2+3=6
It can be verified that the output arrangement follows all the constraints provided in the problem statement.Input: N = 4, M = 2
Output: 1 -2 3 -4
Explanation: There are exactly 2 prefix arrays having sum greater than zero, Which are {1} and {1, -2, 3} having sum 1 and 2 respectively.
Approach: The problem can be solved based on the following observation
Try to keep the odd positioned elements positive and even positioned elements as negative and maintain count of positive prefixes(If the required number of positive sum prefix is at most N/2). Otherwise, place positive elements till the required number of positive prefix becomes less than the remaining array size.
Follow these steps to solve the problem:
- Create a StringBuilder type ans and int type count variable for arrangement.
- Run a loop from i = 1 to N and follow the below-mentioned steps inside the loop’s scope:
- If M is at most N/2:
- If i is odd and count < M, append i in ans and increment counter else append -i.
- If M is at most N/2:
- Otherwise, do the following:
- If i is odd and count < N-M append -i in ans and increment counter else append i.
- Print ans.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; string solve( int l, int m) { // Counter variable of integer DataType int count = 0; // String "ans" to hold arrangement string ans = "" ; // Loop for applying discussed algorithm for ( int i = 1; i <= l; i++) { if (m <= l / 2) { if (i % 2 == 1 && count < m) { ans += to_string(i) + " " ; count++; } else ans += to_string(-1 * i) + " " ; } else { if (i % 2 == 1 && count < l - m) { ans += to_string(-1 * i) + " " ; count++; } else ans += to_string(i) + " " ; } } return ans; } // Driver code int main() { // Input value of L and M int N = 4; int M = 2; cout << solve(N, M); return 0; } // This code is contributed by Tapesh(tapeshdua420) |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { public static String solve( int l, int m) { // Counter variable of integer DataType int count = 0 ; // StringBuilder "ans" to hold arrangement StringBuilder ans = new StringBuilder(); // Loop for applying discussed algorithm for ( int i = 1 ; i <= l; i++) { if (m <= l / 2 ) { if (i % 2 == 1 && count < m) { ans.append(i).append( " " ); count++; } else ans.append(- 1 * i).append( " " ); } else { if (i % 2 == 1 && count < l - m) { ans.append(- 1 * i).append( " " ); count++; } else ans.append(i).append( " " ); } } return ans.toString(); } // Driver code public static void main(String[] args) { // Input value of L and M int N = 4 ; int M = 2 ; System.out.println(solve(N, M)); } } |
Python3
# Python code to implement the approach def solve(l, m): # Counter variable of integer DataType count = 0 # String "ans" to hold arrangement ans = "" # Loop for applying discussed algorithm for i in range ( 1 , l + 1 ): if (m < = l / / 2 ): if (i % 2 = = 1 and count < m): ans + = str (i) + " " count + = 1 else : ans + = str ( - 1 * i) + " " else : if (i % 2 = = 1 and count < l - m): ans + = str ( - 1 * i) + " " count + = 1 else : ans + = str (i) + " " return ans # Driver code if __name__ = = '__main__' : # Input value of L and M N = 4 M = 2 print (solve(N, M)) # This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code to implement the approach using System; class GFG { static string solve( int l, int m) { // Counter variable of integer DataType int count = 0; // String "ans" to hold arrangement string ans = "" ; // Loop for applying discussed algorithm for ( int i = 1; i <= l; i++) { if (m <= l / 2) { if (i % 2 == 1 && count < m) { ans += i.ToString() + " " ; count++; } else ans += (-1 * i).ToString() + " " ; } else { if (i % 2 == 1 && count < l - m) { ans += (-1 * i).ToString() + " " ; count++; } else ans += i.ToString() + " " ; } } return ans; } // Driver code static void Main() { // Input value of L and M int N = 4; int M = 2; Console.WriteLine(solve(N, M)); } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Javascript code to implement the approach function solve(l, m) { // Counter variable of integer DataType var count = 0 // String "ans" to hold arrangement var ans = "" // Loop for applying discussed algorithm for ( var i = 1; i <= l; i++) { if (m <= l / 2) { if (i % 2 == 1 && count < m) { ans += i + " " count += 1 } else { ans += -1 * i + " " } } else { if (i % 2 == 1 && count < l - m) { ans += -1 * i + " " count += 1 } else { ans += i + " " } } } return ans } // Driver code // Input value of L and M var N = 4 var M = 2 console.log(solve(N, M)) // This code is contributed by Tapesh(tapeshdua420) |
1 -2 3 -4
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Approach:
- Create a function solve that takes in two integers n and m and returns a vector of integers.
- Create a vector arr of size n.
- Initialize a counter variable count to 0.
- Loop through the indices of arr from 0 to n-1.
- Check if count is less than m.
- If count is less than m, check if the current index is even.
- If the current index is even, set the value at that index in arr to i+1.
- If the current index is odd, set the value at that index in arr to -(i+1) and increment count.
- If count is greater than or equal to m, check if the current index is even.
- If the current index is even, set the value at that index in arr to -(i+1).
- If the current index is odd, set the value at that index in arr to i+1.
- Return arr.
- In the main function, call solve with the inputs n and m.
- Loop through the elements in the returned vector and print each element followed by a space.
- Print a newline character to finish the output.
C++
#include <iostream> #include <vector> using namespace std; vector< int > solve( int n, int m) { vector< int > arr(n); int count = 0; for ( int i = 0; i < n; i++) { if (count < m) { if (i % 2 == 0) { arr[i] = i + 1; } else { arr[i] = -(i + 1); count++; } } else { if (i % 2 == 0) { arr[i] = -(i + 1); } else { arr[i] = i + 1; } } } return arr; } int main() { int n = 4, m = 2; vector< int > arr = solve(n, m); for ( int i = 0; i < n; i++) { cout << arr[i] << " " ; } cout << endl; return 0; } |
Java
import java.util.*; public class Main { public static void main(String[] args) { int n = 4 , m = 2 ; List<Integer> arr = solve(n, m); for ( int i = 0 ; i < n; i++) { System.out.print(arr.get(i) + " " ); } System.out.println(); } public static List<Integer> solve( int n, int m) { List<Integer> arr = new ArrayList<>(n); int count = 0 ; for ( int i = 0 ; i < n; i++) { if (count < m) { if (i % 2 == 0 ) { arr.add(i + 1 ); } else { arr.add(-(i + 1 )); count++; } } else { if (i % 2 == 0 ) { arr.add(-(i + 1 )); } else { arr.add(i + 1 ); } } } return arr; } } |
Python3
def solve(n, m): # vector arr of size n. arr = [ 0 ] * n # count variable count to 0 count = 0 # Loop through the indices of arr from 0 to n-1 for i in range (n): if count < m: # If count is less than m, check if the current index is even if i % 2 = = 0 : # set the value at that index in arr to i+1 arr[i] = i + 1 else : # set the value at that index in arr to -(i+1) and increment count arr[i] = - (i + 1 ) count + = 1 # If count is greater than or equal to m, else : # If the current index is even, set the value at that index in arr to -(i+1) if i % 2 = = 0 : arr[i] = - (i + 1 ) # If the current index is odd, set the value at that index in arr to i+1. else : arr[i] = i + 1 return arr # Driver code n = 4 m = 2 arr = solve(n, m) for i in range (n): print (arr[i], end = " " ) print () |
C#
using System; using System.Collections.Generic; public class GFG { public static List< int > Solve( int n, int m) { List< int > arr = new List< int >(n); int count = 0; for ( int i = 0; i < n; i++) { if (count < m) { if (i % 2 == 0) { arr.Add(i + 1); } else { arr.Add(-(i + 1)); count++; } } else { if (i % 2 == 0) { arr.Add(-(i + 1)); } else { arr.Add(i + 1); } } } return arr; } public static void Main() { int n = 4, m = 2; List< int > arr = Solve(n, m); foreach ( int num in arr) { Console.Write(num + " " ); } Console.WriteLine(); } } |
Javascript
// Nikunj Sonigara function solve(n, m) { const arr = []; let count = 0; for (let i = 0; i < n; i++) { if (count < m) { if (i % 2 === 0) { arr.push(i + 1); } else { arr.push(-(i + 1)); count++; } } else { if (i % 2 === 0) { arr.push(-(i + 1)); } else { arr.push(i + 1); } } } return arr; } const n = 4, m = 2; const arr = solve(n, m); console.log(...arr); console.log(); |
1 -2 3 -4
Time Complexity: O(n)
Auxiliary Space: O(1)
Related Articles: