Dada una array arr[] que contiene N enteros. En un paso, cualquier elemento de la array se puede aumentar o disminuir en uno. La tarea es encontrar los pasos mínimos necesarios para que el producto de los elementos del arreglo sea 1 .
Ejemplos:
Entrada: arr[] = { -2, 4, 0 }
Salida: 5
Podemos cambiar -2 a -1, 0 a -1 y 4 a 1.
Por lo tanto, se requieren un total de 5 pasos para actualizar los elementos
de manera que el producto de la array final es 1.Entrada: arr[] = { -1, 1, -1 }
Salida: 0
Enfoque: siga los pasos a continuación para resolver el problema:
- El producto de los elementos de la array solo puede ser igual a 1 cuando solo hay 1 y -1 en la array y la cuenta de -1 es par.
- Ahora, todos los números positivos se pueden reducir a 1 porque están más cerca de 1 que de -1 .
- De manera similar, todos los números negativos se pueden actualizar a -1 .
- Si hay 0 s presentes en la array, entonces se pueden reducir a 1 o -1 según la situación (la cuenta de -1 debe ser par).
- Si la cuenta de -ve números es par, entonces siempre darán -1 .
- Pero si hay un número impar de -cinco números , entonces van a producir un número impar de -1s . Para solucionarlo, hay dos posibilidades:
- Primero intente encontrar el recuento de 0 en la array porque se necesitará 1 operación para ser -1 .
- Si no hay ceros en la array, simplemente agregue 2 en la respuesta porque tomará dos pasos hacer -1 a 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum
// steps required
int MinStep(int a[], int n)
{
// To store the count of 0s, positive
// and negative numbers
int positive = 0,
negative = 0,
zero = 0;
// To store the ans
int step = 0;
for (int i = 0; i < n; i++) {
// If array element is
// equal to 0
if (a[i] == 0) {
zero++;
}
// If array element is
// a negative number
else if (a[i] < 0) {
negative++;
// Extra cost needed
// to make it -1
step = step + (-1 - a[i]);
}
// If array element is
// a positive number
else {
positive++;
// Extra cost needed
// to make it 1
step = step + (a[i] - 1);
}
}
// Now the array will
// have -1, 0 and 1 only
if (negative % 2 == 0) {
// As count of negative is even
// so we will change all 0 to 1
// total cost here will be
// count of 0s
step = step + zero;
}
else {
// If there are zeroes present
// in the array
if (zero > 0) {
// Change one zero to -1
// and rest of them to 1
// Total cost here will
// be count of '0'
step = step + zero;
}
// If there are no zeros in the array
else {
// As no 0s are available so we
// have to change one -1 to 1
// which will cost 2 to
// change -1 to 1
step = step + 2;
}
}
return step;
}
// Driver code
int main()
{
int a[] = { 0, -2, -1, -3, 4 };
int n = sizeof(a) / sizeof(a[0]);
cout << MinStep(a, n);
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Function to return the minimum
// steps required
static int MinStep(int a[], int n)
{
// To store the count of 0s, positive
// and negative numbers
int positive = 0,
negative = 0,
zero = 0;
// To store the ans
int step = 0;
for (int i = 0; i < n; i++) {
// If array element is
// equal to 0
if (a[i] == 0) {
zero++;
}
// If array element is
// a negative number
else if (a[i] < 0) {
negative++;
// Extra cost needed
// to make it -1
step = step + (-1 - a[i]);
}
// If array element is
// a positive number
else {
positive++;
// Extra cost needed
// to make it 1
step = step + (a[i] - 1);
}
}
// Now the array will
// have -1, 0 and 1 only
if (negative % 2 == 0) {
// As count of negative is even
// so we will change all 0 to 1
// total cost here will be
// count of 0s
step = step + zero;
}
else {
// If there are zeroes present
// in the array
if (zero > 0) {
// Change one zero to -1
// and rest of them to 1
// Total cost here will
// be count of '0'
step = step + zero;
}
// If there are no zeros in the array
else {
// As no 0s are available so we
// have to change one -1 to 1
// which will cost 2 to
// change -1 to 1
step = step + 2;
}
}
return step;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 0, -2, -1, -3, 4 };
int n = a.length;
System.out.println(MinStep(a, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the minimum # steps required def MinStep(a, n): # To store the count of 0s, positive # and negative numbers positive = 0; negative = 0; zero = 0; # To store the ans step = 0; for i in range(n): # If array element is # equal to 0 if (a[i] == 0): zero += 1; # If array element is # a negative number elif (a[i] < 0): negative += 1; # Extra cost needed # to make it -1 step = step + (-1 - a[i]); # If array element is # a positive number else: positive += 1; # Extra cost needed # to make it 1 step = step + (a[i] - 1); # Now the array will # have -1, 0 and 1 only if (negative % 2 == 0): # As count of negative is even # so we will change all 0 to 1 # total cost here will be # count of 0s step = step + zero; else: # If there are zeroes present # in the array if (zero > 0): # Change one zero to -1 # and rest of them to 1 # Total cost here will # be count of '0' step = step + zero; # If there are no zeros in the array else: # As no 0s are available so we # have to change one -1 to 1 # which will cost 2 to # change -1 to 1 step = step + 2; return step; # Driver code if __name__ == '__main__': a = [0, -2, -1, -3, 4]; n = len(a); print(MinStep(a, n)); # This code is contributed by PrinciRaj1992
C#
// C# implementation of the approach
using System;
class GFG {
// Function to return the minimum
// steps required
static int MinStep(int[] a, int n)
{
// To store the count of 0s,
// positive and negative numbers
int positive = 0,
negative = 0,
zero = 0;
// To store the ans
int step = 0;
for (int i = 0; i < n; i++) {
// If array element is
// equal to 0
if (a[i] == 0) {
zero++;
}
// If array element is
// a negative number
else if (a[i] < 0) {
negative++;
// Extra cost needed
// to make it -1
step = step + (-1 - a[i]);
}
// If array element is
// a positive number
else {
positive++;
// Extra cost needed
// to make it 1
step = step + (a[i] - 1);
}
}
// Now the array will
// have -1, 0 and 1 only
if (negative % 2 == 0) {
// As count of negative is even
// so we will change all 0 to 1
// total cost here will be
// count of 0s
step = step + zero;
}
else {
// If there are zeroes present
// in the array
if (zero > 0) {
// Change one zero to -1
// and rest of them to 1
// Total cost here will
// be count of '0'
step = step + zero;
}
// If there are no zeros in the array
else {
// As no 0s are available so we
// have to change one -1 to 1
// which will cost 2 to
// change -1 to 1
step = step + 2;
}
}
return step;
}
// Driver code
static public void Main()
{
int[] a = { 0, -2, -1, -3, 4 };
int n = a.Length;
Console.Write(MinStep(a, n));
}
}
// This code is contributed by ajit.
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum
// steps required
function MinStep(a, n)
{
// To store the count of 0s, positive
// and negative numbers
let positive = 0,
negative = 0,
zero = 0;
// To store the ans
let step = 0;
for (let i = 0; i < n; i++) {
// If array element is
// equal to 0
if (a[i] == 0) {
zero++;
}
// If array element is
// a negative number
else if (a[i] < 0) {
negative++;
// Extra cost needed
// to make it -1
step = step + (-1 - a[i]);
}
// If array element is
// a positive number
else {
positive++;
// Extra cost needed
// to make it 1
step = step + (a[i] - 1);
}
}
// Now the array will
// have -1, 0 and 1 only
if (negative % 2 == 0) {
// As count of negative is even
// so we will change all 0 to 1
// total cost here will be
// count of 0s
step = step + zero;
}
else {
// If there are zeroes present
// in the array
if (zero > 0) {
// Change one zero to -1
// and rest of them to 1
// Total cost here will
// be count of '0'
step = step + zero;
}
// If there are no zeros in the array
else {
// As no 0s are available so we
// have to change one -1 to 1
// which will cost 2 to
// change -1 to 1
step = step + 2;
}
}
return step;
}
// Driver code
let a = [ 0, -2, -1, -3, 4 ];
let n = a.length;
document.write(MinStep(a, n));
</script>
Producción:
7
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
?list=PLM68oyaqFM7Q-sv3gA5xbzfgVkoQ0xDrW