Dada una array que contiene N elementos, cada elemento es 1 o 2. La tarea es averiguar si la array se puede dividir en 2 partes de modo que la suma de los elementos en ambas partes sea igual.
Ejemplos:
Input : N = 3, arr[] = {1, 1, 2}
Output : YES
Input : N = 4, arr[] = {1, 2, 2, }
Output : NO
La idea es observar que la array se puede dividir en dos partes con la misma suma solo si la suma total de la array es par, es decir, divisible por 2.
Digamos que la suma total de la array se denota por sum .
Ahora bien, se plantean dos casos:
- Si sum/2 es par : cuando el valor de sum/2 también es par, significa que la suma de cada una de las dos partes también es par y no necesitamos considerar nada especial. Por lo tanto, devuelva verdadero para este caso.
- Si la suma/2 es impar : cuando el valor de la suma/2 es impar, significa que la suma de cada parte también es impar. Esto solo es posible cuando cada una de las dos partes de la array contiene al menos un 1. Considere los casos en que suma = 2, 6 o 10. Entonces, cuando suma/2 es impar, verifique si hay al menos un 1 en la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above
// approach:
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible to
// split the array in two parts with
// equal sum
bool isSpiltPossible(int n, int a[])
{
int sum = 0, c1 = 0;
// Calculate sum of elements
// and count of 1's
for (int i = 0; i < n; i++) {
sum += a[i];
if (a[i] == 1) {
c1++;
}
}
// If total sum is odd, return False
if (sum % 2)
return false;
// If sum of each part is even,
// return True
if ((sum / 2) % 2 == 0)
return true;
// If sum of each part is even but
// there is atleast one 1
if (c1 > 0)
return true;
else
return false;
}
// Driver Code
int main()
{
int n = 3;
int a[] = { 1, 1, 2 };
if (isSpiltPossible(n, a))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java implementation of the above
// approach:
class GFG
{
// Function to check if it is possible
// to split the array in two parts with
// equal sum
static boolean isSpiltPossible(int n,
int a[])
{
int sum = 0, c1 = 0;
// Calculate sum of elements
// and count of 1's
for (int i = 0; i < n; i++)
{
sum += a[i];
if (a[i] == 1)
{
c1++;
}
}
// If total sum is odd, return False
if(sum % 2 != 0)
return false;
// If sum of each part is even,
// return True
if ((sum / 2) % 2 == 0)
return true;
// If sum of each part is even but
// there is atleast one 1
if (c1 > 0)
return true;
else
return false;
}
// Driver Code
public static void main(String[] args)
{
int n = 3;
int a[] = { 1, 1, 2 };
if (isSpiltPossible(n, a))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by
// Code Mech
Python3
# Python3 implementation of the above
# approach:
# Function to check if it is possible
# to split the array in two halfs with
# equal Sum
def isSpiltPossible(n, a):
Sum = 0
c1 = 0
# Calculate Sum of elements
# and count of 1's
for i in range(n):
Sum += a[i]
if (a[i] == 1):
c1 += 1
# If total Sum is odd, return False
if (Sum % 2):
return False
# If Sum of each half is even,
# return True
if ((Sum // 2) % 2 == 0):
return True
# If Sum of each half is even
# but there is atleast one 1
if (c1 > 0):
return True
else:
return False
# Driver Code
n = 3
a = [ 1, 1, 2 ]
if (isSpiltPossible(n, a)):
print("YES")
else:
print("NO")
# This code is contributed
# by Mohit Kumar
C#
// C# implementation of the above
// approach:
using System;
class GFG
{
// Function to check if it is possible
// to split the array in two parts with
// equal sum
static bool isSpiltPossible(int n,
int[] a)
{
int sum = 0, c1 = 0;
// Calculate sum of elements
// and count of 1's
for (int i = 0; i < n; i++)
{
sum += a[i];
if (a[i] == 1)
{
c1++;
}
}
// If total sum is odd, return False
if(sum % 2 != 0)
return false;
// If sum of each part is even,
// return True
if ((sum / 2) % 2 == 0)
return true;
// If sum of each part is even but
// there is atleast one 1
if (c1 > 0)
return true;
else
return false;
}
// Driver Code
public static void Main()
{
int n = 3;
int[] a = { 1, 1, 2 };
if (isSpiltPossible(n, a))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed by
// Code Mech
PHP
<?php
// PHP implementation of the above
// approach:
// Function to check if it is possible
// to split the array in two parts with
// equal sum
function isSpiltPossible($n, $a)
{
$sum = 0; $c1 = 0;
// Calculate sum of elements
// and count of 1's
for ($i = 0; $i < $n; $i++)
{
$sum += $a[$i];
if ($a[$i] == 1)
{
$c1++;
}
}
// If total sum is odd, return False
if($sum % 2 != 0)
return false;
// If sum of each part is even,
// return True
if (($sum / 2) % 2 == 0)
return true;
// If sum of each part is even but
// there is atleast one 1
if ($c1 > 0)
return true;
else
return false;
}
// Driver Code
$n = 3;
$a = array( 1, 1, 2 );
if (isSpiltPossible($n, $a))
echo("YES");
else
echo("NO");
// This code is contributed by
// Code Mech
?>
Javascript
<script>
// Javascript implementation of the above approach
// Function to check if it is possible
// to split the array in two parts with
// equal sum
function isSpiltPossible(n, a)
{
let sum = 0, c1 = 0;
// Calculate sum of elements
// and count of 1's
for (let i = 0; i < n; i++)
{
sum += a[i];
if (a[i] == 1)
{
c1++;
}
}
// If total sum is odd, return False
if(sum % 2 != 0)
return false;
// If sum of each part is even,
// return True
if ((sum / 2) % 2 == 0)
return true;
// If sum of each part is even but
// there is atleast one 1
if (c1 > 0)
return true;
else
return false;
}
// driver program
let n = 3;
let a = [ 1, 1, 2 ];
if (isSpiltPossible(n, a))
document.write("YES");
else
document.write("NO");
</script>
Producción:
YES
Complejidad Temporal: O(N), ya que allí corre un bucle de 0 a (n – 1).
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA