Dada una secuencia de enteros no negativos, digamos a 1 , a 2 , …, a n . Solo se pueden realizar las siguientes acciones en la secuencia dada:
- Resta 1 de a[i] y a[i+1] ambos.
Encuentre si la serie se puede modificar en todos los ceros usando cualquier número requerido de operaciones anteriores.
Ejemplos:
Input : 1 2 Output : NO Explanation: Only two elements, if we subtract 1 then it will convert into [0, 1]. so answer is NO. Input : 0 1 1 0 Output : YES Explanation: Here we can choose both 1 and subtract 1 from them then array becomes [0, 0, 0, 0]. So answer is YES. Input : 1 2 3 4 Output : NO Explanation: if we try to subtract 1 any number of times then array will be [0, 0, 0, 1]. [1, 2, 3, 4]->[0, 1, 3, 4]->[0, 0, 2, 3]-> [0, 0, 1, 2]->[0, 0, 0, 1].
Enfoque 1: si todos los elementos adyacentes (i, i+1) en la array son iguales y el número total de elementos en la array es par, entonces todos los elementos se pueden convertir a cero. Por ejemplo, si los elementos de la array son como {1, 1, 2, 2, 3, 3}, entonces todos sus elementos se pueden convertir en cero.
Entonces, en este caso, la suma de cada valor posicionado impar es siempre igual a la suma de los valores posicionados pares.
C++
// CPP program to find if it is possible
// to make all array elements 0 by decrement
// operations.
#include <bits/stdc++.h>
using namespace std;
bool isPossibleToZero(int a[], int n)
{
// used for storing the sum of even
// and odd position element in array.
int even = 0, odd = 0;
for (int i = 0; i < n; i++)
{
// if position is odd, store sum
// value of odd position in odd
if (i & 1)
odd += a[i];
// if position is even, store sum
// value of even position in even
else
even += a[i];
}
return (odd == even);
}
// Driver program
int main()
{
int arr[] = { 0, 1, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
if (isPossibleToZero(arr, n))
cout << "YES";
else
cout << "NO";
}
Java
// Java program to find if
// it is possible to make
// all array elements 0 by
// decrement operations.
import java.io.*;
class GFG
{
static boolean isPossibleToZero(int a[],
int n)
{
// used for storing the
// sum of even and odd
// position element in array.
int even = 0, odd = 0;
for (int i = 0; i < n; i++)
{
// if position is odd,
// store sum value of
// odd position in odd
if ((i & 1) == 0)
odd += a[i];
// if position is even,
// store sum value of
// even position in even
else
even += a[i];
}
return (odd == even);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 0, 1, 1, 0 };
int n = arr.length;
if (isPossibleToZero(arr, n))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by m_kit
Python3
# Python3 program to find if it is
# possible to make all array elements
# 0 by decrement operations.
def isPossibleToZero(a, n):
# used for storing the
# sum of even and odd
# position element in array.
even = 0;
odd = 0;
for i in range(n):
# if position is odd, store sum
# value of odd position in odd
if (i & 1):
odd += a[i];
# if position is even, store sum
# value of even position in even
else:
even += a[i];
return (odd == even);
# Driver Code
arr = [0, 1, 1, 0];
n = len(arr);
if (isPossibleToZero(arr, n)):
print("YES");
else:
print("NO");
# This code is contributed by mits
C#
// C# program to find if
// it is possible to make
// all array elements 0 by
// decrement operations.
using System;
class GFG
{
static bool isPossibleToZero(int []a,
int n)
{
// used for storing the
// sum of even and odd
// position element in array.
int even = 0, odd = 0;
for (int i = 0; i < n; i++)
{
// if position is odd,
// store sum value of
// odd position in odd
if ((i & 1) == 0)
odd += a[i];
// if position is even,
// store sum value of
// even position in even
else
even += a[i];
}
return (odd == even);
}
// Driver Code
static public void Main ()
{
int []arr = {0, 1, 1, 0};
int n = arr.Length;
if (isPossibleToZero(arr, n))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed
// by m_kit
PHP
<?php
// PHP program to find if it
// is possible to make all
// array elements 0 by
// decrement operations.
function isPossibleToZero($a, $n)
{
// used for storing the
// sum of even and odd
// position element in array.
$even = 0; $odd = 0;
for ($i = 0; $i < $n; $i++)
{
// if position is odd,
// store sum value of
// odd position in odd
if ($i & 1)
$odd += $a[$i];
// if position is even,
// store sum value of
// even position in even
else
$even += $a[$i];
}
return ($odd == $even);
}
// Driver Code
$arr = array (0, 1, 1, 0);
$n = sizeof($arr);
if (isPossibleToZero($arr, $n))
echo "YES";
else
echo "NO";
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find if
// it is possible to make
// all array elements 0 by
// decrement operations.
function isPossibleToZero(a, n)
{
// Used for storing the
// sum of even and odd
// position element in array.
let even = 0, odd = 0;
for(let i = 0; i < n; i++)
{
// If position is odd,
// store sum value of
// odd position in odd
if ((i & 1) == 0)
odd += a[i];
// If position is even,
// store sum value of
// even position in even
else
even += a[i];
}
return (odd == even);
}
// Driver code
let arr = [ 0, 1, 1, 0 ];
let n = arr.length;
if (isPossibleToZero(arr, n))
document.write("YES");
else
document.write("NO");
// This code is contributed by mukesh07
</script>
Producción:
YES
Enfoque 2: si el número formado por un elemento de array dado es divisible por 11, entonces todos los elementos de la array también se pueden convertir a cero.
Por ejemplo: dada la array {0, 1, 1, 0}, el número formado por esta array es 110, luego es divisible por 11. Entonces, todos los elementos se pueden convertir en cero.
C++
// CPP implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
bool isPossibleToZero(int a[], int n)
{
// converting array element into number
int num = 0;
for (int i = 0; i < n; i++)
num = num * 10 + a[i];
// Check if divisible by 11
return (num % 11 == 0);
}
// Driver program
int main()
{
int arr[] = { 0, 1, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
if (isPossibleToZero(arr, n))
cout << "YES";
else
cout << "NO";
}
Java
// Java implementation of the above approach
import java.io.*;
class GFG {
static boolean isPossibleToZero(int a[], int n)
{
// converting array element into number
int num = 0;
for (int i = 0; i < n; i++)
num = num * 10 + a[i];
// Check if divisible by 11
return (num % 11 == 0);
}
// Driver program
public static void main (String[] args)
{
int arr[] = {0, 1, 1, 0};
int n = arr.length;
if (isPossibleToZero(arr, n))
System.out.println( "YES");
else
System.out.println ("NO");
}
}
// This code is contributed by @ajit
Python3
# Python3 implementation of the
# above approach
def isPossibleToZero(a, n):
# converting array element
# into number
num = 0;
for i in range(n):
num = num * 10 + a[i];
# Check if divisible by 11
return (num % 11 == 0);
# Driver Code
arr = [ 0, 1, 1, 0 ];
n = len(arr);
if (isPossibleToZero(arr, n)):
print("YES");
else:
print("NO");
# This code is contributed mits
C#
// C# implementation of the above approach
using System;
class GFG
{
static bool isPossibleToZero(int[] a, int n)
{
// converting array element into number
int num = 0;
for (int i = 0; i < n; i++)
num = num * 10 + a[i];
// Check if divisible by 11
return (num % 11 == 0);
}
// Driver Code
public static void Main()
{
int[] arr = {0, 1, 1, 0};
int n = arr.Length;
if (isPossibleToZero(arr, n))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP implementation of
// the above approach
function isPossibleToZero($a, $n)
{
// converting array
// element into number
$num = 0;
for ($i = 0; $i < $n; $i++)
$num = $num * 10 + $a[$i];
// Check if divisible by 11
return ($num % 11 == 0);
}
// Driver Code
$arr = array( 0, 1, 1, 0 );
$n = sizeof($arr);
if (isPossibleToZero($arr, $n))
echo "YES";
else
echo "NO";
// This code is contributed ajit
?>
Javascript
<script>
// Javascript implementation of the above approach
function isPossibleToZero(a, n)
{
// Converting array element into number
let num = 0;
for(let i = 0; i < n; i++)
num = num * 10 + a[i];
// Check if divisible by 11
return (num % 11 == 0);
}
// Driver code
let arr = [ 0, 1, 1, 0 ];
let n = arr.length;
if (isPossibleToZero(arr, n))
document.write("YES");
else
document.write("NO");
// This code is contributed by divyeshrabadiya07
</script>
Producción:
YES
La implementación anterior provoca el desbordamiento de arrays un poco más grandes. Podemos usar el siguiente método para evitar el desbordamiento. Comprobar si un número grande es divisible por 11 o no
Publicación traducida automáticamente
Artículo escrito por Ravi_Maurya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA