Consultas para comprobar si todos los elementos se pueden convertir en positivos cambiando los signos exactamente K veces

Dada una array de enteros arr[] y algunas consultas que consisten en un entero K , la tarea es determinar si es posible hacer que todos los enteros sean positivos cambiando los signos de los enteros exactamente K veces. Podemos invertir el signo de un número entero más de una vez. Si es posible, imprima Sí ; de lo contrario, imprima No.
Ejemplos: 
 

Entrada: arr[] = {-1, 2, -3, 4, 5}, q[] = {1, 2} 
Salida: 
No 
Sí  Consulta 1: solo se puede cambiar
el signo de -1 o -3  y
no ambos. 
Consulta 2: Los signos de ambos números negativos 
se pueden cambiar a positivos.
Entrada: arr[] = {-1, -1, 0, 6}, q[] = {1, 2, 3, 4} 
Salida: 
No 
Sí 
Sí 
Sí 
 

Enfoque: El siguiente será el algoritmo que utilizaremos: 
 

1. Cuente el número de enteros negativos en la array y guárdelo en una variable cnt .
2. Si no hay cero en la array: 
   • Si K ≥ cnt , la respuesta será Sí .
   • Si K = cnt y (K – cnt) % 2 = 0 , la respuesta será Sí .
   • De lo contrario , la respuesta será No.
3. Si existe un cero en la array, la respuesta solo será No si K <cnt; de lo contrario, la respuesta siempre será Sí .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// To store the count of
// negative integers
int cnt_neg;
 
// Check if zero exists
bool exists_zero;
 
// Function to find the count of
// negative integers and check
// if zero exists in the array
void preProcess(int arr[], int n)
{
    for (int i = 0; i < n; i++) {
        if (arr[i] < 0)
            cnt_neg++;
        if (arr[i] == 0)
            exists_zero = true;
    }
}
 
// Function that returns true if array
// elements can be made positive by
// changing signs exactly k times
bool isPossible(int k)
{
    if (!exists_zero) {
        if (k >= cnt_neg and (k - cnt_neg) % 2 == 0)
            return true;
        else
            return false;
    }
    else {
        if (k >= cnt_neg)
            return true;
        else
            return false;
    }
}
 
// Driver code
int main()
{
    int arr[] = { -1, 2, -3, 4, 5 };
    int n = sizeof(arr) / sizeof(int);
 
    // Pre-processing
    preProcess(arr, n);
 
    int queries[] = { 1, 2, 3, 4 };
    int q = sizeof(queries) / sizeof(int);
 
    // Perform queries
    for (int i = 0; i < q; i++) {
        if (isPossible(queries[i]))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
 
 
// To store the count of
// negative integers
static int cnt_neg;
 
// Check if zero exists
static boolean exists_zero;
 
// Function to find the count of
// negative integers and check
// if zero exists in the array
static void preProcess(int []arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] < 0)
            cnt_neg++;
        if (arr[i] == 0)
            exists_zero = true;
    }
}
 
// Function that returns true if array
// elements can be made positive by
// changing signs exactly k times
static boolean isPossible(int k)
{
    if (!exists_zero)
    {
        if (k >= cnt_neg && (k - cnt_neg) % 2 == 0)
            return true;
        else
            return false;
    }
    else
    {
        if (k >= cnt_neg)
            return true;
        else
            return false;
    }
}
 
// Driver code
public static void main (String[] args)
{
    int arr[] = { -1, 2, -3, 4, 5 };
    int n = arr.length;
 
    // Pre-processing
    preProcess(arr, n);
 
    int queries[] = { 1, 2, 3, 4 };
    int q = arr.length;
 
    // Perform queries
    for (int i = 0; i < q; i++)
    {
        if (isPossible(queries[i]))
            System.out.println( "Yes");
        else
            System.out.println( "No");
    }
}
}
 
// This code is contributed by anuj_67..

# Python3 implementation of the approach
 
# To store the count of
# negative integers
cnt_neg = 0;
 
# Check if zero exists
exists_zero = None;
 
# Function to find the count of
# negative integers and check
# if zero exists in the array
def preProcess(arr, n) :
    global cnt_neg
     
    for i in range(n) :
        if (arr[i] < 0) :
            cnt_neg += 1;
         
        if (arr[i] == 0) :
            exists_zero = True;
 
# Function that returns true if array
# elements can be made positive by
# changing signs exactly k times
def isPossible(k) :
 
    if (not exists_zero) :
        if (k >= cnt_neg and (k - cnt_neg) % 2 == 0) :
            return True;
        else :
            return False;
     
    else :
        if (k >= cnt_neg) :
            return True;
        else :
            return False;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ -1, 2, -3, 4, 5 ];
    n = len(arr);
 
    # Pre-processing
    preProcess(arr, n);
 
    queries = [ 1, 2, 3, 4 ];
    q = len(queries);
 
    # Perform queries
    for i in range(q) :
        if (isPossible(queries[i])) :
            print("Yes");
        else :
            print("No");
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
// To store the count of
// negative integers
static int cnt_neg;
 
// Check if zero exists
static bool exists_zero ;
 
// Function to find the count of
// negative integers and check
// if zero exists in the array
static void preProcess(int []arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] < 0)
            cnt_neg++;
        if (arr[i] == 0)
            exists_zero = true;
    }
}
 
// Function that returns true if array
// elements can be made positive by
// changing signs exactly k times
static bool isPossible(int k)
{
    if (!exists_zero)
    {
        if (k >= cnt_neg && (k - cnt_neg) % 2 == 0)
            return true;
        else
            return false;
    }
    else
    {
        if (k >= cnt_neg)
            return true;
        else
            return false;
    }
}
 
// Driver code
static public void Main ()
{
     
    int []arr = { -1, 2, -3, 4, 5 };
    int n = arr.Length;
     
    // Pre-processing
    preProcess(arr, n);
     
    int []queries = { 1, 2, 3, 4 };
    int q = arr.Length;
     
    // Perform queries
    for (int i = 0; i < q; i++)
    {
        if (isPossible(queries[i]))
            Console.WriteLine( "Yes");
        else
            Console.WriteLine( "No");
    }
}
}
 
// This code is contributed by ajit...

<script>
 
// Javascript implementation of the approach
 
// To store the count of
// negative integers
let cnt_neg = 0;
 
// Check if zero exists
let exists_zero = false;
 
// Function to find the count of
// negative integers and check
// if zero exists in the array
function preProcess(arr, n)
{
    for (let i = 0; i < n; i++) {
        if (arr[i] < 0)
            cnt_neg++;
        if (arr[i] == 0)
            exists_zero = true;
    }
}
 
// Function that returns true if array
// elements can be made positive by
// changing signs exactly k times
function isPossible(k)
{
    if (!exists_zero) {
        if (k >= cnt_neg && (k - cnt_neg) % 2 == 0)
            return true;
        else
            return false;
    }
    else {
        if (k >= cnt_neg)
            return true;
        else
            return false;
    }
}
 
// Driver code
    let arr = [ -1, 2, -3, 4, 5 ];
    let n = arr.length;
 
    // Pre-processing
    preProcess(arr, n);
 
    let queries = [ 1, 2, 3, 4 ];
    let q = queries.length;
 
    // Perform queries
    for (let i = 0; i < q; i++) {
        if (isPossible(queries[i]))
            document.write("Yes<br>");
        else
            document.write("No<br>");
    }
 
</script>

No
Yes
No
Yes

Complejidad de tiempo: O(n + q), donde n y q representan el tamaño de las arrays dadas.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.