Array Partitioning I


Solution in C
/* * main.c * * Created on: Sep 2, 2017 * Author: Prakhar Avasthi */ /* * This problem is pretty straightforward, as in this problem we need to make * n pairs each with 2 numbers from 2n numbers such that sum of min of two numbers * in each pair is largest. * basically if we sort the array and sum every odd digit, we will have our answer. * Problem is easy, I would suggest you to try various sorting algorithm. * I tried merge sort. In merge sort, there are 2 steps: * 1. divide array in 2 parts recursively as we need to implement merging in bottomup fashion * 2. while merging bottomup, we will get/make 2 sorted arrays, using some extra space * we will merge two sorted arrays in 1 extra space array and copy back. * Here 2 sorted arrays doesn't mean that we will have two actual array, * we will have one array but we will know two start points and two end points. * After sorting, a simple loop will fetch the accepted answer. * */ #include<stdio.h> #include<stdlib.h> void merge(int* arr, int start, int mid, int end) { int p = start, q = mid+1; int *temp_arr; temp_arr = (int *)malloc((end+1)*sizeof(int)); int i=start; while(p<mid+1 && q<end+1) { if(arr[p]<=arr[q]) { temp_arr[i] = arr[p]; i++; p++; } else { temp_arr[i] = arr[q]; i++; q++; } } if(p<=mid) { while(p<=mid) temp_arr[i++] = arr[p++]; } if(q<=end) { while(q<=end) temp_arr[i++] = arr[q++]; } for(int j = start; j<=end; j++) arr[j] = temp_arr[j]; free(temp_arr); } void merge_sort(int *arr, int left, int right) { if(left == right) return; int new_right = (left+right)/2; merge_sort(arr, left, new_right); merge_sort(arr, new_right+1, right); merge(arr, left, new_right, right); } int arrayPairSum(int* nums, int numsSize) { int result = 0; merge_sort(nums, 0, numsSize1); for(int i = 0; i < numsSize; i=i+1) { printf("%d ",nums[i]); result = result + nums[i]; } return result; } int main() { int arr[10] = {1,3,5,4,8,9,2,0,7,6}; setbuf(stdout, NULL); printf("%d", arrayPairSum(arr,10)); return 0; }