本文概述
给定大小为N且数字为K的数组A。任务是找出是否有可能将数组A划分为K个连续的子数组, 以使每个子数组中的元素之和相同。
先决条件:计算将数组分为三个具有相等总和的连续部分的方式的数量
例子 :
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
方法:
可以通过使用前缀和来求解。首先,注意数组中所有元素的总和应该被K整除,以创建K个分区,每个分区的总和相等。如果它是可整除的,通过以下方法检查每个分区的和是相等的:
1.对于特定的K, 每个子数组应具有所需的总和= total_sum /K。
2.从第0个下标开始,开始比较前缀sum,只要它等于sum,它就意味着一个子数组的结束(假设是在下标j处)。
3.从(j + 1)第一个索引中,找到另一个合适的i,其sum (prefix_sum[i] - prefix_sum[j])等于所需的sum。这个过程一直进行,直到找到所需数量的连续子数组,即K。
4.如果在任意下标处,任何子数组的和大于所需的和,则退出循环,因为每个子数组都应该包含一个相等的和。
以下是上述方法的实现
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
?>
输出如下:
Yes
时间复杂度:O(N), 其中N是数组的大小。
辅助空间:O(N), 其中N是数组的大小。
我们可以进一步减少空间复杂度toO(1).
由于该数组将被划分为k个子数组, 因此所有子数组都是连续的。因此, 想法是计算子数组的总和等于整个数组的总和除以k。
如果计数== k打印是, 否则打印否。
以下是上述方法的实现
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
?>
输出如下:
Yes