Generate an array with K positive numbers such that arr[i] is either -1 or 1 and sum of the array is positive

Generate an array with K positive numbers such that arr[i] is either -1 or 1 and sum of the array is positive

Given two positive integers, N and K ( 1 ≤ K ≤ N ), the task is to construct an array arr[](1-based indexing) such that each array element arr[i] is either i or -i and the array contains exactly K positive values such that sum of the array elements is positive. If more than one such sequences can be generated, print any of them. Otherwise, print “-1”.

Examples:

Input: N = 10, K = 6
Output: -1 2 -3 4 -5 6 -7 8 9 10
Explanation:
Consider the sequence as {-1, 2, -3, 4, -5, 6, -7, 8, 9, 10}, the sum of the constructed sequence is (-1) + 2 + (-3) + 4 + (-5) + 6 + (-7) + 8 + 9 + 10 = 23, which is positive.

Input: N = 7, K = 2
Output: -1

Approach: The given problem can be solved by using the Greedy Approach by making the first (N – K) elements in the sequence negative and the remaining K elements positive. Follow the steps below to solve the problem: 

• Initialize an array say, arr[] that stores the resultant sequence.
• Initialize two variables, say sumNeg and sumPos as 0 to store the sum of the first (N – K) and the remaining elements respectively.
• Iterate over the range [0, N – K – 1] using the variable i and update the value of arr[i] to -(i + 1) and add the value arr[i] to the variable sumNeg.
• Iterate over the range [N – K, N – 1] using the variable i and update the vaue of arr[i] to (i + 1) and add the value arr[i] to the variable sumPos.
• If the value of absolute value of sumNeg is greater than sumPos, then print -1. Otherwise, print the sum elements in the array arr[] as the result.

Below is the implementation of the above approach:

C++14

#include <bits/stdc++.h> using namespace std;    void findSequence(int n, int k) {          int arr[n];                  int sumPos = 0, sumNeg = 0;                  for (int i = 0; i < n - k; i++) {                     arr[i] = -(i + 1);                     sumNeg += arr[i];     }                  for (int i = n - k; i < n; i++) {                     arr[i] = i + 1;                     sumPos += arr[i];     }                  if (abs(sumNeg) >= sumPos) {         cout << -1;         return;     }             for (int i = 0; i < n; i++)         cout << arr[i] << " "; }    int main() {     int N = 10, K = 6;     findSequence(N, K);        return 0; }

Output:

-1 -2 -3 -4 5 6 7 8 9 10

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

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets