Sum of Four Values

Given an array of n$n$ integers, find four values (at distinct positions) whose sum is x.

Example:

Input:  n = 8, m = 15, arr = {3, 2, 5, 8, 1, 3, 2, 3}
Output: 5 1 6 4

Approach

Java

import java.util.Arrays;
import java.util.Comparator;

public class SumofFourValues {
    public static void main(String[] args) {

        int n = 8, m = 15;
        int[] arr = { 3, 2, 5, 8, 1, 3, 2, 3 };

        sumOfFourValues(n, m, arr);

    }

    static void sumOfFourValues(int n, int m, int[] arr) {

        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            int x = arr[i];

            a[i][0] = x;
            a[i][1] = i + 1;
        }
        Arrays.sort(a, Comparator.comparingDouble(o -> o[0]));
        for (int u = 0; u < n; u++) {
            for (int v = u + 1; v < n; v++) {
                for (int i = v + 1, j = n - 1; i < j;) {
                    if (a[u][0] + a[v][0] + 
                     a[i][0] + a[j][0] == m) {
                        System.out.println(a[u][1] + " " + 
      a[v][1] + " " + a[i][1] + " " + a[j][1]);
                        return;
                    } else if (a[u][0] + a[v][0] + a[i][0] 
          + a[j][0] < m) {
                        i++;
                    } else {
                        j--;
                    }
                }
            }
        }
        System.out.println("IMPOSSIBLE");
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

void sumOfFourValues(int n, int m, vector<int> &arr)
{

    vector<array<int, 2>> a(n);
    for (int i = 0; i < n; i++)
    {
        int x = arr[i];

        a[i] = {x, i + 1};
    }
    sort(a.begin(), a.end());
    for (int u = 0; u < n; u++)
    {
        for (int v = u + 1; v < n; v++)
        {
            for (int i = v + 1, j = n - 1; i < j;)
            {
                if (a[u][0] + a[v][0] + a[i][0] + a[j][0] == m)
                {
                    cout << a[u][1] << " " << a[v][1]
                         << " " << a[i][1] << " " << a[j][1]
                         << "\n";
                    return;
                }
                else if (a[u][0] + a[v][0] + a[i][0] +
     a[j][0] < m)
                {
                    i++;
                }
                else
                {
                    j--;
                }
            }
        }
    }
    cout << "IMPOSSIBLE\n";
}

int main()
{
    int n = 8, m = 15;
    vector<int> arr = {3, 2, 5, 8, 1, 3, 2, 3};

    sumOfFourValues(n, m, arr);

    return 0;
}