Dada una array A de tamaño N y un número K. La tarea es averiguar si es posible dividir la array A en K subarreglos contiguos de modo que la suma de los elementos dentro de cada uno de estos subarreglos sea la misma.
Prerrequisito: Cuente el número de formas de dividir una array en tres partes contiguas que tengan la misma suma
Ejemplos:
Input : arr[] = { 1, 4, 2, 3, 5 } K = 3
Output : Yes
Explanation :
Three possible partitions which have equal sum :
(1 + 4), (2 + 3) and (5)
Input : arr[] = { 1, 1, 2, 2 } K = 2
Output : No
Enfoque:
Se puede resolver usando sumas de prefijos . En primer lugar, tenga en cuenta que la suma total de todos los elementos de la array debe ser divisible por K para crear K particiones, cada una con la misma suma. Si es divisible entonces, verifique que cada partición tenga una suma igual haciendo: 1. Para un K en particular, cada subarreglo
debe tener una suma requerida = suma_total / K.
2. Comenzando desde el índice 0, comience a comparar la suma del prefijo, como tan pronto como es igual a la suma, implica el final de un subarreglo (digamos en el índice j). 3. A partir de (j + 1) el índice, encuentre otro i adecuado cuya suma ( prefix_sum [i] – prefix_sum[j]) sea igual a la suma requerida. Y el proceso va hasta
se encuentra el número requerido de subarreglos contiguos, es decir, K.
4. Si en cualquier índice, la suma de cualquier subarreglo se vuelve mayor que la suma requerida, salga
del bucle ya que cada subarreglo debe contener una suma igual.
A continuación se muestra la implementación del enfoque anterior
C++
// CPP Program to check if array
// can be split into K contiguous
// subarrays each having equal sum
#include <bits/stdc++.h>
using namespace std;
// function returns true to it is possible to
// create K contiguous partitions each having
// equal sum, otherwise false
bool KpartitionsPossible(int arr[], int n, int K)
{
// Creating and filling prefix sum array
int prefix_sum[n];
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++)
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
// return false if total_sum is not
// divisible by K
int total_sum = prefix_sum[n-1];
if (total_sum % K != 0)
return false;
// a temporary variable to check
// there are exactly K partitions
int temp = 0;
int pos = -1;
for (int i = 0; i < n; i++)
{
// find suitable i for which first
// partition have the required sum
// and then find next partition and so on
if (prefix_sum[i] - (pos == -1 ? 0 :
prefix_sum[pos]) == total_sum / K)
{
pos = i;
temp++;
}
// if it becomes greater than
// required sum break out
else if (prefix_sum[i] - prefix_sum[pos] >
total_sum / K)
break;
}
// check if temp has reached to K
return (temp == K);
}
// Driver Code
int main()
{
int arr[] = { 4, 4, 3, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 3;
if (KpartitionsPossible(arr, n, K))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java Program to check if an array
// can be split into K contiguous
// subarrays each having equal sum
public class GfG{
// Function returns true to it is possible to
// create K contiguous partitions each having
// equal sum, otherwise false
static boolean KpartitionsPossible(int arr[], int n, int K)
{
// Creating and filling prefix sum array
int prefix_sum[] = new int[n];
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++)
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
// return false if total_sum is not divisible by K
int total_sum = prefix_sum[n-1];
if (total_sum % K != 0)
return false;
// a temporary variable to check
// there are exactly K partitions
int temp = 0, pos = -1;
for (int i = 0; i < n; i++)
{
// find suitable i for which first
// partition have the required sum
// and then find next partition and so on
if (prefix_sum[i] - (pos == -1 ? 0 :
prefix_sum[pos]) == total_sum / K)
{
pos = i;
temp++;
}
// if it becomes greater than
// required sum break out
else if (prefix_sum[i] - (pos == -1 ? 0 :
prefix_sum[pos]) > total_sum / K)
break;
}
// check if temp has reached to K
return (temp == K);
}
public static void main(String []args){
int arr[] = { 4, 4, 3, 5, 6, 2 };
int n = arr.length;
int K = 3;
if (KpartitionsPossible(arr, n, K))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Rituraj Jain
Python3
# Python 3 Program to check if array
# can be split into K contiguous
# subarrays each having equal sum
# function returns true to it is possible to
# create K contiguous partitions each having
# equal sum, otherwise false
def KpartitionsPossible(arr, n, K):
# Creating and filling prefix sum array
prefix_sum = [0 for i in range(n)]
prefix_sum[0] = arr[0]
for i in range(1, n, 1):
prefix_sum[i] = prefix_sum[i - 1] + arr[i]
# return false if total_sum is not
# divisible by K
total_sum = prefix_sum[n - 1]
if (total_sum % K != 0):
return False
# a temporary variable to check
# there are exactly K partitions
temp = 0
pos = -1
for i in range(0, n, 1):
# find suitable i for which first
# partition have the required sum
# and then find next partition and so on
if (pos == -1):
sub = 0
else:
sub = prefix_sum[pos]
if (prefix_sum[i] - sub == total_sum / K) :
pos = i
temp += 1
# if it becomes greater than
# required sum break out
elif (prefix_sum[i] -
prefix_sum[pos] > total_sum / K):
break
# check if temp has reached to K
return (temp == K)
# Driver Code
if __name__ =='__main__':
arr = [4, 4, 3, 5, 6, 2]
n = len(arr)
K = 3
if (KpartitionsPossible(arr, n, K)):
print("Yes")
else:
print("No")
# This code is contributed by
# Shashank_Sharma
C#
// C# Program to check if an array
// can be split into K contiguous
// subarrays each having equal sum
using System;
class GfG
{
// Function returns true to it is possible to
// create K contiguous partitions each having
// equal sum, otherwise false
static bool KpartitionsPossible(int[] arr, int n, int K)
{
// Creating and filling prefix sum array
int[] prefix_sum = new int[n];
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++)
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
// return false if total_sum is not divisible by K
int total_sum = prefix_sum[n-1];
if (total_sum % K != 0)
return false;
// a temporary variable to check
// there are exactly K partitions
int temp = 0, pos = -1;
for (int i = 0; i < n; i++)
{
// find suitable i for which first
// partition have the required sum
// and then find next partition and so on
if (prefix_sum[i] - (pos == -1 ? 0 :
prefix_sum[pos]) == total_sum / K)
{
pos = i;
temp++;
}
// if it becomes greater than
// required sum break out
else if (prefix_sum[i] - (pos == -1 ? 0 :
prefix_sum[pos]) > total_sum / K)
break;
}
// check if temp has reached to K
return (temp == K);
}
// Driver code
public static void Main()
{
int[] arr = { 4, 4, 3, 5, 6, 2 };
int n = arr.Length;
int K = 3;
if (KpartitionsPossible(arr, n, K))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by ChitraNayal
PHP
<?php
// PHP Program to check if array
// can be split into K contiguous
// subarrays each having equal sum
// function returns true to
// it is possible to create
// K contiguous partitions
// each having equal sum,
// otherwise false
function KpartitionsPossible($arr,
$n, $K)
{
// Creating and filling
// prefix sum array
$prefix_sum = Array();
$prefix_sum[0] = $arr[0];
for ($i = 1; $i < $n; $i++)
$prefix_sum[$i] = $prefix_sum[$i - 1] +
$arr[$i];
// return false if total_sum
// is not divisible by K
$total_sum = $prefix_sum[$n - 1];
if ($total_sum % $K != 0)
return false;
// a temporary variable to
// check there are exactly
// K partitions
$temp = 0;
$pos = -1;
for ($i = 0; $i < $n; $i++)
{
// find suitable i for which
// first partition have the
// required sum and then find
// next partition and so on
if ($prefix_sum[$i] - ($pos == -1 ? 0 :
$prefix_sum[$pos]) ==
(int)$total_sum / $K)
{
$pos = $i;
$temp++;
}
}
// check if temp has
// reached to K
return ($temp == $K);
}
// Driver Code
$arr = array (4, 4, 3,
5, 6, 2);
$n = sizeof($arr) ;
$K = 3;
if (KpartitionsPossible($arr, $n, $K))
echo "Yes";
else
echo "No";
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript Program to check if an array
// can be split into K contiguous
// subarrays each having equal sum
// Function returns true to it is possible to
// create K contiguous partitions each having
// equal sum, otherwise false
function KpartitionsPossible(arr, n, K)
{
// Creating and filling prefix sum array
let prefix_sum = new Array(n);
prefix_sum[0] = arr[0];
for (let i = 1; i < n; i++)
prefix_sum[i] = prefix_sum[i - 1] +
arr[i];
// return false if total_sum is
// not divisible by K
let total_sum = prefix_sum[n-1];
if (total_sum % K != 0)
return false;
// a temporary variable to check
// there are exactly K partitions
let temp = 0, pos = -1;
for (let i = 0; i < n; i++)
{
// find suitable i for which first
// partition have the required sum
// and then find next partition and so on
if (prefix_sum[i] - (pos == -1 ? 0 :
prefix_sum[pos]) ==
parseInt(total_sum / K, 10))
{
pos = i;
temp++;
}
// if it becomes greater than
// required sum break out
else if (prefix_sum[i] - (pos == -1 ? 0 :
prefix_sum[pos]) >
parseInt(total_sum / K, 10))
break;
}
// check if temp has reached to K
return (temp == K);
}
let arr = [ 4, 4, 3, 5, 6, 2 ];
let n = arr.length;
let K = 3;
if (KpartitionsPossible(arr, n, K))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad de tiempo: O (N), donde N es el tamaño de la array.
Espacio auxiliar: O(N), donde N es el tamaño de la array.
Podemos reducir aún más la complejidad del espacio a O(1) .
Dado que la array se dividirá en k sub arrays y todas las sub arrays serán continuas. Entonces, la idea es calcular el recuento de subarrays cuya suma es igual a la suma de toda la array dividida por k.
if cuenta == k imprime Sí else imprime No.
A continuación se muestra la implementación del enfoque anterior
C++
// CPP Program to check if array
// can be split into K contiguous
// subarrays each having equal sum
#include <bits/stdc++.h>
using namespace std;
// function returns true to it is possible to
// create K contiguous partitions each having
// equal sum, otherwise false
int KpartitionsPossible(int arr[], int n, int k)
{
int sum = 0;
int count = 0;
// calculate the sum of the array
for(int i = 0; i < n; i++)
sum = sum + arr[i];
if(sum % k != 0)
return 0;
sum = sum / k;
int ksum = 0;
// ksum denotes the sum of each subarray
for(int i = 0; i < n; i++)
{
ksum=ksum + arr[i];
// one subarray is found
if(ksum == sum)
{
// to locate another
ksum = 0;
count++;
}
}
if(count == k)
return 1;
else
return 0;
}
// Driver code
int main() {
int arr[] = { 1, 1, 2, 2};
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
if (KpartitionsPossible(arr, n, k) == 0)
cout << "Yes";
else
cout<<"No";
return 0;
}
Java
//Java Program to check if array
// can be split into K contiguous
// subarrays each having equal sum
public class GFG {
// function returns true to it is possible to
// create K contiguous partitions each having
// equal sum, otherwise false
static int KpartitionsPossible(int arr[], int n, int k) {
int sum = 0;
int count = 0;
// calculate the sum of the array
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
}
if (sum % k != 0) {
return 0;
}
sum = sum / k;
int ksum = 0;
// ksum denotes the sum of each subarray
for (int i = 0; i < n; i++) {
ksum = ksum + arr[i];
// one subarray is found
if (ksum == sum) {
// to locate another
ksum = 0;
count++;
}
}
if (count == k) {
return 1;
} else {
return 0;
}
}
// Driver Code
public static void main(String[] args) {
int arr[] = {1, 1, 2, 2};
int k = 2;
int n = arr.length;
if (KpartitionsPossible(arr, n, k) == 0) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
/*This code is contributed by PrinciRaj1992*/
Python3
# Python3 Program to check if array
# can be split into K contiguous
# subarrays each having equal sum
# Function returns true to it is possible
# to create K contiguous partitions each
# having equal sum, otherwise false
def KpartitionsPossible(arr, n, k) :
sum = 0
count = 0
# calculate the sum of the array
for i in range(n) :
sum = sum + arr[i]
if(sum % k != 0) :
return 0
sum = sum // k
ksum = 0
# ksum denotes the sum of each subarray
for i in range(n) :
ksum = ksum + arr[i]
# one subarray is found
if(ksum == sum) :
# to locate another
ksum = 0
count += 1
if(count == k) :
return 1
else :
return 0
# Driver code
if __name__ == "__main__" :
arr = [ 1, 1, 2, 2]
k = 2
n = len(arr)
if (KpartitionsPossible(arr, n, k) == 0) :
print("Yes")
else :
print("No")
# This code is contributed by Ryuga
C#
// C# Program to check if array
// can be split into K contiguous
// subarrays each having equal sum
using System;
public class GFG{
// function returns true to it is possible to
// create K contiguous partitions each having
// equal sum, otherwise false
static int KpartitionsPossible(int []arr, int n, int k) {
int sum = 0;
int count = 0;
// calculate the sum of the array
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
}
if (sum % k != 0) {
return 0;
}
sum = sum / k;
int ksum = 0;
// ksum denotes the sum of each subarray
for (int i = 0; i < n; i++) {
ksum = ksum + arr[i];
// one subarray is found
if (ksum == sum) {
// to locate another
ksum = 0;
count++;
}
}
if (count == k) {
return 1;
} else {
return 0;
}
}
// Driver Code
public static void Main() {
int []arr = {1, 1, 2, 2};
int k = 2;
int n = arr.Length;
if (KpartitionsPossible(arr, n, k) == 0) {
Console.Write("Yes");
} else {
Console.Write("No");
}
}
}
/*This code is contributed by PrinciRaj1992*/
PHP
<?php
// PHP Program to check if array
// can be split into K contiguous
// subarrays each having equal sum
// function returns true to it is possible to
// create K contiguous partitions each having
// equal sum, otherwise false
function KpartitionsPossible($arr, $n, $k)
{
$sum = 0;
$count = 0;
// calculate the sum of the array
for($i = 0; $i < $n; $i++)
$sum = $sum + $arr[$i];
if($sum % $k != 0)
return 0;
$sum = $sum / $k;
$ksum = 0;
// ksum denotes the sum of each subarray
for( $i = 0; $i < $n; $i++)
{
$ksum = $ksum + $arr[$i];
// one subarray is found
if($ksum == $sum)
{
// to locate another
$ksum = 0;
$count++;
}
}
if($count == $k)
return 1;
else
return 0;
}
// Driver code
$arr = array(1, 1, 2, 2);
$k = 2;
$n = count($arr);
if (KpartitionsPossible($arr, $n, $k) == 0)
echo "Yes";
else
echo "No";
// This code is contributed by
// Rajput-Ji
?>
Javascript
<script>
// Javascript program to check if array
// can be split into K contiguous
// subarrays each having equal sum
// Function returns true to it is possible to
// create K contiguous partitions each having
// equal sum, otherwise false
function KpartitionsPossible(arr, n, k)
{
let sum = 0;
let count = 0;
// Calculate the sum of the array
for(let i = 0; i < n; i++)
sum = sum + arr[i];
if (sum % k != 0)
return 0;
sum = parseInt(sum / k, 10);
let ksum = 0;
// ksum denotes the sum of each subarray
for(let i = 0; i < n; i++)
{
ksum = ksum + arr[i];
// One subarray is found
if (ksum == sum)
{
// To locate another
ksum = 0;
count++;
}
}
if (count == k)
return 1;
else
return 0;
}
// Driver code
let arr = [ 1, 1, 2, 2 ];
let k = 2;
let n = arr.length;
if (KpartitionsPossible(arr, n, k) == 0)
document.write("Yes");
else
document.write("No");
// This code is contributed by mukesh07
</script>
Producción:
Yes
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA