Java Code to Partition an Array and return the maximized Sum of Pairs

 


Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum

This is a leetcode problem, which we will try to solve today. 

On analyzing the problem we can understand that we need to split or partition the array into pairs of 2, and then take the minimum value from a pair, such that the sum of these minimum values is maximum. 

Ideally, the value can be maximum only if we are taking bigger numbers, but we have to take minimum values from a pair of Integers. So, to work around this problem, we will sort the array first. This way, when we make pairs, we can ensure that the minimum value of a pair can come out to be a bigger number. We will then take the sum and return the same. 

/**
 * Group an array of 2n integers, into n pairs of two such that sum of min(ai, bi) for all i is maximized
 * @param nums
 * @return
 * @author computengine.com
 */
public int arrayPairSum(int[] nums) {

	Arrays.sort(nums);

	int sum = 0;

	for (int i = 0; i < nums.length; i += 2) {
		sum += Math.min(nums[i], nums[i + 1]);
	}

	return sum;
}

Thanks for Reading the Article. If you have reached this far, we hope that the article was useful to you! Please Like/Share/Follow us on FacebookTwitterTumblrLeetCode 

Comments

Popular posts from this blog

Calculate Your CTC Salary Hike Percentage - Online Calculator to find your New Salary

Find the Longest Streak of 1's in a Binary Array using Java Code

Java Program to Read a Properties file and return a Property Value

Create a File logging Utility using Java Code

What is my IP Address - How to find your IP address on Local Network using Command Prompt, and External Network using JavaScript Code