Minimum Partitions of Maximum Size 2 and Sum Limited by Given Value in C++

Problem statement

Given an array arr[] of positive numbers, find minimum number of sets in array which satisfy following property,

• A set can contain maximum two elements in it. The two elements need not to be contiguous.
• Sum of elements of set should be less than or equal to given Key. It may be assumed that given key is greater than or equal to the largest array element.

Example

If arr[] = {1, 2, 3, 4} and k = 5 then following 2 pairs can be created −

{1, 4} and {2, 3}

Algorithm

• Sort the array
• Begin two pointers from two corners of the sorted array. If their sum is smaller than or equal to given key, then we make set of them, else we consider the last element alone

Example

#include <iostream>
#include <algorithm>
using namespace std;
int getMinSets(int *arr, int n, int key) {
   int i, j;
   sort (arr, arr + n);
   for (i = 0, j = n - 1; i <= j; ++i) {
      if (arr[i] + arr[j] <= key) {
         --j;
      }
   }
   return i;
}
int main() {
   int arr[] = {1, 2, 3, 4};
   int key = 5;
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Minimum set = " << getMinSets(arr, n, key) << endl;
   return 0;
}

Output

When you compile and execute above program. It generates following output −

Minimum set = 2