Dada una array arr[] y un entero K , la tarea es encontrar si la array se puede dividir en dos sub-arrays de modo que la diferencia absoluta de la suma de los elementos de ambas sub-arrays sea K.
Ejemplos:
Entrada: arr[] = {2, 4, 5, 1}, K = 0
Salida: Sí
{2, 4} y {5, 1} son los dos subconjuntos posibles.
|(2 + 4) – (5 + 1)| = |6 – 6| = 0
Entrada: arr[] = {2, 4, 1, 5}, K = 2
Salida: No
Acercarse:
- Suponga que existe una respuesta, deje que la suma de los elementos del subarreglo (con una suma más pequeña) sea S .
- La suma de los elementos de la segunda array será S + K .
- Y, S + S + K debe ser igual a la suma de todos los elementos de la array, digamos totalSum = 2 *S + K .
- S = (sumatotal – K) / 2
- Ahora, recorra la array hasta que logremos una suma de S a partir del primer elemento y, si no es posible, imprima No.
- De lo contrario, imprima Sí .
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function that return true if it is possible
// to divide the array into sub-arrays
// that satisfy the given condition
bool solve(int array[], int size, int k)
{
// To store the sum of all the elements
// of the array
int totalSum = 0;
for (int i = 0; i < size; i++)
totalSum += array[i];
// Sum of any sub-array cannot be
// a floating point value
if ((totalSum - k) % 2 == 1)
return false;
// Required sub-array sum
int S = (totalSum - k) / 2;
int sum = 0;
for (int i = 0; i < size; i++) {
sum += array[i];
if (sum == S)
return true;
}
return false;
}
// Driver Code
int main()
{
int array[] = { 2, 4, 1, 5 };
int k = 2;
int size = sizeof(array) / sizeof(array[0]);
if (solve(array, size, k))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// Function that return true if it is possible
// to divide the array into sub-arrays
// that satisfy the given condition
static boolean solve(int array[], int size, int k)
{
// To store the sum of all the elements
// of the array
int totalSum = 0;
for (int i = 0; i < size; i++)
totalSum += array[i];
// Sum of any sub-array cannot be
// a floating point value
if ((totalSum - k) % 2 == 1)
return false;
// Required sub-array sum
int S = (totalSum - k) / 2;
int sum = 0;
for (int i = 0; i < size; i++)
{
sum += array[i];
if (sum == S)
return true;
}
return false;
}
// Driver Code
public static void main (String[] args)
{
int array[] = { 2, 4, 1, 5 };
int k = 2;
int size = array.length;
if (solve(array, size, k))
System.out.println ("Yes");
else
System.out.println ("No" );
}
}
// This Code is contributed by akt_mit
Python3
# Function that return true if it is possible
# to divide the array into sub-arrays
# that satisfy the given condition
def solve(array,size,k):
# To store the sum of all the elements
# of the array
totalSum = 0
for i in range (0,size):
totalSum += array[i]
# Sum of any sub-array cannot be
# a floating point value
if ((totalSum - k) % 2 == 1):
return False
# Required sub-array sum
S = (totalSum - k) / 2
sum = 0;
for i in range (0,size):
sum += array[i]
if (sum == S):
return True
return False
# Driver Code
array= [2, 4, 1, 5]
k = 2
n = 4
if (solve(array, n, k)):
print("Yes")
else:
print("No")
# This code is contributed by iAyushRaj.
C#
using System;
class GFG
{
// Function that return true if it is possible
// to divide the array into sub-arrays
// that satisfy the given condition
public static bool solve(int[] array, int size, int k)
{
// To store the sum of all the elements
// of the array
int totalSum = 0;
for (int i = 0; i < size; i++)
totalSum += array[i];
// Sum of any sub-array cannot be
// a floating point value
if ((totalSum - k) % 2 == 1)
return false;
// Required sub-array sum
int S = (totalSum - k) / 2;
int sum = 0;
for (int i = 0; i < size; i++)
{
sum += array[i];
if (sum == S)
return true;
}
return false;
}
// Driver Code
public static void Main()
{
int[] array = { 2, 4, 1, 5 };
int k = 2;
int size = 4;
if (solve(array, size, k))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by iAyushRaj.
PHP
<?php
// Function that return true if it is possible
// to divide the array into sub-arrays
// that satisfy the given condition
function solve($array, $size,$k)
{
// To store the sum of all the elements
// of the array
$totalSum = 0;
for ($i = 0; $i < $size; $i++)
$totalSum += $array[$i];
// Sum of any sub-array cannot be
// a floating point value
if (($totalSum - $k) % 2 == 1)
return false;
// Required sub-array sum
$S = ($totalSum - $k) / 2;
$sum = 0;
for ($i = 0; $i < $size; $i++)
{
$sum += $array[$i];
if ($sum == $S)
return true;
}
return false;
}
// Driver Code
$array = array( 2, 4, 1, 5 );
$k = 2;
$size = sizeof($array);
if (solve($array, $size, $k))
echo "Yes";
else
echo "No";
// This code is contributed by iAyushRaj.
?>
Javascript
<script>
// Javascript program to illustrate
// the above problem
// Function that return true if it is possible
// to divide the array into sub-arrays
// that satisfy the given condition
function solve(array, size, k)
{
// To store the sum of all the elements
// of the array
let totalSum = 0;
for (let i = 0; i < size; i++)
totalSum += array[i];
// Sum of any sub-array cannot be
// a floating point value
if ((totalSum - k) % 2 == 1)
return false;
// Required sub-array sum
let S = (totalSum - k) / 2;
let sum = 0;
for (let i = 0; i < size; i++)
{
sum += array[i];
if (sum == S)
return true;
}
return false;
}
// Driver Code
let array = [ 2, 4, 1, 5 ];
let k = 2;
let size = array.length;
if (solve(array, size, k))
document.write("Yes");
else
document.write ("No" );
</script>
Producción:
No
Complejidad de tiempo: O(n) donde n es el tamaño de la array.
Espacio Auxiliar: O(1)