Maximum sum by adding second minimum element by selecting any quadruple of the array

Problem Statement:You are Given an array of length N.Each element of array denotes the strength you can gain.Your task is to gain maximum strength possible from the array under following conditions.

1)Choose four indices i,j,k,l  

2)Among the four selected indices add the second minimum strength to your strength

Your task is to find the max strength you can gain by selecting the four strengths optimally

Note:It is guaranteed that N is a multiple of 4

input:A=[7,4,3,3]

output:3

input:A=[7,4,5,2,3,1,5,9]

output:8

Explanation:1st Set of 4 Strength=[7,1,5,9]=>2nd Min value=5 2nd Set of 4 Strength=[4,5,2,3]=>2nd Min value=3 Total Strength gained=8

Approach:Greedy Approach will work in this question.What we have to do is selecting the four indices in such a way that the second minimum value is maximized.This can be done by sorting the array and choosing 3 strengths from the back and one strength from the front.

Below is the Java implementation of the above approach 

Code

import java.io.*;

class Solution{
    public static void main(String[] args)
    {
        Scanner obj = new Scanner(System.in);
        int n = obj.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = obj.nextInt(); // Taking input of the
                                  // strengths
        }

        Arrays.sort(a);

        int strength = 0;
        int i = 0, j = n - 1;

        while (i < j) {
            strength += a[j - 2]; // Taking 3 strengths from
                                  // end of array and one
                                  // strength from the front
            i++;
            j -= 3;
        }
        System.out.println(strength);
        obj.close();
    }
}

Time Complexity:O(n)

Auxiliary Space:O(1)

NOTE:This question was asked in NASDAQ INTERN HIRING CHALLENGE

Feel free to comment if you have any doubt in comments section

For more Data structure and algorithms,computer science,programming,coding related problems search my website.
 

Learn how to prepare for Information Technology Based companies here