C++ solution with explanations


  • 0
    G
    class Solution {
    public:
    
        //
        // IsFeasible will check if can partition 
        // the set between begin - end into m partitions
        // which each partition is of sum = Amount
        //
        
        template <typename I>
        bool IsFeasible(I begin, I end,long long Amount,int m)
        {
            long long Sum = Amount;
            int Total = 0;
            
            while(begin != end)
            {
                if(Total == m)
                {
                    return false;
                }
                
                if(*begin <= Sum)
                {
                    Sum -= *begin;
                    begin++;
                }
                else
                {
                    Total++;
                    Sum = Amount;
                }
            }
            
            return (true);
        }
    
        int splitArray(vector<int>& nums, int m) 
        {
            long long Sum = accumulate(nums.begin(),nums.end(),0);
            
            long long start = 1;
            long long end = Sum + 1;
            
            int Result = INT_MAX;
            
            //
            // perform a binary search between 1 to Sum + 1
            // and find the minimum  1 <= s < Sum + 1
            // such that we can partition the set into m partitions
            // each of size s. If we find that it is possible, 
            // we adjust the upper boundry to be s. If it is not
            // possible we adjust the lower boundry to be s.
            //
            
            while(start < end)
            {
                long long Med = (start + end)/2;
                
                if(IsFeasible(nums.begin(),nums.end(),Med,m))
                {
                    Result = Med;
                    end = Med;
                }
                else
                {
                    start = Med + 1;
                }
            }
            
            return (Result);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.