Genere una array con K números positivos de modo que arr[i] sea -1 o 1 y la suma de la array sea positiva

Dados dos enteros positivos, N y K ( 1 ≤ K ≤ N ), la tarea es construir una array arr[] ( indexación basada en 1 ) tal que cada elemento de la array arr[i] sea i o -i y la array contiene exactamente K valores positivos tales que la suma de los elementos de la array es positiva. Si se puede generar más de una de estas secuencias, imprima cualquiera de ellas. De lo contrario, imprima «-1» .

Ejemplos:

Entrada: N = 10, K = 6
Salida: -1 2 -3 4 -5 6 -7 8 9 10
Explicación:
Considere la secuencia como {-1, 2, -3, 4, -5, 6, -7, 8, 9, 10}, la suma de la secuencia construida es (-1) + 2 + (-3) + 4 + (-5) + 6 + (-7) + 8 + 9 + 10 = 23, que es positivo.

Entrada: N = 7, K = 2
Salida: -1

Enfoque: El problema dado se puede resolver usando el Enfoque Codicioso al hacer que los primeros (N – K) elementos en la secuencia sean negativos y los restantes K elementos positivos. Siga los pasos a continuación para resolver el problema: 

• Inicializa una array , por ejemplo, arr[] que almacena la secuencia resultante.
• Inicialice dos variables, digamos sumNeg y sumPos como 0 para almacenar la suma del primero (N – K) y los elementos restantes respectivamente.
• Itere sobre el rango [0, N – K – 1] usando la variable i y actualice el valor de arr[i] a -(i + 1) y agregue el valor arr[i] a la variable sumNeg .
• Itere sobre el rango [N – K, N – 1] usando la variable i y actualice el valor de arr[i] a (i + 1) y agregue el valor arr[i] a la variable sumPos .
• Si el valor del valor absoluto de sumNeg es mayor que sumPos , imprima -1 . De lo contrario, imprima los elementos de la suma en la array arr[] como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate the resultant
// sequence of first N natural numbers
void findSequence(int n, int k)
{
    // Initialize an array of size N
    int arr[n];
 
    // Stores the sum of positive and
    // negative elements
    int sumPos = 0, sumNeg = 0;
 
    // Mark the first N - K elements
    // as negative
    for (int i = 0; i < n - k; i++) {
 
        // Update the value of arr[i]
        arr[i] = -(i + 1);
 
        // Update the value of sumNeg
        sumNeg += arr[i];
    }
 
    // Mark the remaining K elements
    // as positive
    for (int i = n - k; i < n; i++) {
 
        // Update the value of arr[i]
        arr[i] = i + 1;
 
        // Update the value of sumPos
        sumPos += arr[i];
    }
 
    // If the sum of the sequence
    // is negative, then print -1
    if (abs(sumNeg) >= sumPos) {
        cout << -1;
        return;
    }
 
    // Print the required sequence
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
 
// Driver Code
int main()
{
    int N = 10, K = 6;
    findSequence(N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.Arrays;
 
class GFG{
     
// Function to generate the resultant
// sequence of first N natural numbers
static void findSequence(int n, int k)
{
     
    // Initialize an array of size N
    int[] arr = new int[n];
 
    // Stores the sum of positive and
    // negative elements
    int sumPos = 0, sumNeg = 0;
 
    // Mark the first N - K elements
    // as negative
    for(int i = 0; i < n - k; i++)
    {
         
        // Update the value of arr[i]
        arr[i] = -(i + 1);
 
        // Update the value of sumNeg
        sumNeg += arr[i];
    }
 
    // Mark the remaining K elements
    // as positive
    for(int i = n - k; i < n; i++)
    {
         
        // Update the value of arr[i]
        arr[i] = i + 1;
 
        // Update the value of sumPos
        sumPos += arr[i];
    }
 
    // If the sum of the sequence
    // is negative, then print -1
    if (Math.abs(sumNeg) >= sumPos)
    {
        System.out.print(-1);
        return;
    }
 
    // Print the required sequence
    for(int i = 0; i < n; i++)
        System.out.print(arr[i] + " ");
}
 
// Driver code
public static void main(String args[])
{
    int N = 10, K = 6;
     
    findSequence(N, K);
}
}
 
// This code is contributed by sanjoy_62

# Python program for the above approach
# Function to generate the resultant
# sequence of first N natural numbers
def findSequence(n, k):
     
    # Initialize an array of size N
    arr = [0]*n
     
    # Stores the sum of positive and
    # negative elements
    sumPos = 0
    sumNeg = 0
     
    # Mark the first N - K elements
    # as negative
    for i in range(0, n - k):
       
        # Update the value of arr[i]
        arr[i] = -(i + 1)
         
        # Update the value of sumNeg
        sumNeg += arr[i]
     
    # Mark the remaining K elements
    # as positive
    for i in range(n - k, n):
         
        # Update the value of arr[i]
        arr[i] = i + 1
         
        # Update the value of sumPos
        sumPos += arr[i]
         
    # If the sum of the sequence
    # is negative, then print -1
    if (abs(sumNeg) >= sumPos):
        print(-1)
        return
     
    # Print the required sequence
    for i in range(n):
        print( arr[i], end =" ")
 
# Driver Code
N = 10
K = 6
findSequence(N, K)
 
# This code is contributed by shivanisinghss2110

// C# program for the above approach
using System;
class GFG
{
   
    // Function to generate the resultant
    // sequence of first N natural numbers
    static void findSequence(int n, int k)
    {
        // Initialize an array of size N
        int[] arr = new int[n];
 
        // Stores the sum of positive and
        // negative elements
        int sumPos = 0, sumNeg = 0;
 
        // Mark the first N - K elements
        // as negative
        for (int i = 0; i < n - k; i++) {
 
            // Update the value of arr[i]
            arr[i] = -(i + 1);
 
            // Update the value of sumNeg
            sumNeg += arr[i];
        }
 
        // Mark the remaining K elements
        // as positive
        for (int i = n - k; i < n; i++) {
 
            // Update the value of arr[i]
            arr[i] = i + 1;
 
            // Update the value of sumPos
            sumPos += arr[i];
        }
 
        // If the sum of the sequence
        // is negative, then print -1
        if (Math.Abs(sumNeg) >= sumPos) {
            Console.Write(-1);
            return;
        }
 
        // Print the required sequence
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 10, K = 6;
        findSequence(N, K);
    }
}
 
// This code is contributed by ukasp.

<script>
// Javascript program for the above approach
 
// Function to generate the resultant
// sequence of first N natural numbers
function findSequence(n, k)
{
 
    // Initialize an array of size N
    let arr = new Array(n);
 
    // Stores the sum of positive and
    // negative elements
    let sumPos = 0, sumNeg = 0;
 
    // Mark the first N - K elements
    // as negative
    for (let i = 0; i < n - k; i++) {
 
        // Update the value of arr[i]
        arr[i] = -(i + 1);
 
        // Update the value of sumNeg
        sumNeg += arr[i];
    }
 
    // Mark the remaining K elements
    // as positive
    for (let i = n - k; i < n; i++) {
 
        // Update the value of arr[i]
        arr[i] = i + 1;
 
        // Update the value of sumPos
        sumPos += arr[i];
    }
 
    // If the sum of the sequence
    // is negative, then print -1
    if (Math.abs(sumNeg) >= sumPos)
    {
        document.write(-1);
        return;
    }
 
    // Print the required sequence
    for (let i = 0; i < n; i++)
        document.write(arr[i] + " ");
}
 
// Driver Code
let N = 10, K = 6;
findSequence(N, K);
 
// This code is contributed by _saurabh_Jaiswal.
</script>

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

Complejidad temporal: O(N)
Espacio auxiliar: O(N)