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

2021年4月15日19:09:48 发表评论 879 次浏览

本文概述

给定大小为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
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: