检查是否有可能以相等的总和划分k个子数组

本文概述

C++
Java
Python3
C#
PHP
C++
Java
Python3
C#
PHP

给定大小为N且数字为K的数组A。任务是找出是否有可能将数组A划分为K个连续的子数组, 以使每个子数组中的元素之和相同。
先决条件：计算将数组分为三个具有相等总和的连续部分的方式的数量
【检查是否有可能以相等的总和划分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 = 0pos = - 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# 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 0sum = 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 + = 1if (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# 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 ?>

输出如下：