CPP solution using Binary Search


  • 0
    H

    The solution uses the fact that the level where all the numbers become equal will lie within the range of [Minimum element in the array,Maximum element in the array]. The required level can be found using a binary search. If we choose each numbers in our range and calculate the number of moves that will be required to bring all the other elements to that level and then plot the results on a graph, we will see that the number of moves required will first decrease, reach a minimum and then will increase. This minimum is our required level which can be found using binary search. The idea is to find the number of moves for mid, then for mid+1 and for mid-1. If moves(mid-1)>moves(mid)<moves(mid+1), then we have our level. Otherwise if moves(mid-1)>moves(mid)>moves(mid+1), then the graph is still decreasing and we begin our search in its right part. Otherwise if moves(mid-1)<moves(mid)<moves(mid+1), then the graph is increasing and we search in the left part. The overall complexity for the algorithm is O(n*log(max-min)), where n is the number of elements and max is the highest whereas min is the lowest element in the array.

    class Solution {
    public:
        int diffSum(vector<int>& nums,int avg)
        {
            int sum = 0;
            for(int i=0;i<nums.size();i++)
                sum+= abs(nums[i]-avg);
            return sum;
        }
        
        int minMoves2(vector<int>& nums) {
            int low = INT_MAX,high = INT_MIN;
            
            for(int i=0;i<nums.size();i++)
            {
                low = min(nums[i],low);
                high = max(nums[i],high);
            }
            
            int left,right,l = low,h = high,centre,ans;
            while(l<=h)
            {
                int mid = l+(h-l)/2;
                left = right = INT_MAX;
                
                if(mid!=low)
                    left = diffSum(nums,mid-1);
                if(mid!=high)
                    right = diffSum(nums,mid+1);
                centre = diffSum(nums,mid);
                
                if(centre<=left && centre<=right)
                {
                    ans = centre;
                    break;
                }
                else if(centre<=left)
                {
                    l = mid+1;
                }
                else h = mid-1;
            }
            
            return ans;
        }
    };
    

Log in to reply
 

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