4–Sum Problem | Quadruplets with a given sum

By | November 17, 2021
4–Sum Problem Quadruplets with a given sum

Problem

The goal is to count all the quadruplets having target sum S.

Sample Input

[2, 2, 2, 2, 2]

Sample Output

5

Approach

Initialize ans variable with 0. Traverse the given array from 0 to N-3. For each element arr[i], traverse the array again from i+1 to N-2 using the variable j and do the following:

Find the value of the required sum as (S – arr[i] – arr[j]).

Initialize the ans2 with 0 that will store the count of ordered pairs in the above subarray with sum (S – arr[i] – arr[j]).

After finding the ans2, update the ans by ans / 2.

Vamware

C++ Programming

#include <iostream>
#include <unordered_map>
using namespace std;

// Function to return the number of
// quadruplets
int solve(int a[], int n, int sum)
{

    int i, j, k, l;
    int ans = 0;

    // all possible first elements
    for (i = 0; i < n - 3; i++) 
       {

        // all possible second element
        for (j = i + 1; j < n - 2; j++) 
          {

            int req = sum - a[i] - a[j];
            unordered_map<int, int> mp;

            for (k = j + 1; k < n; k++)
                mp[a[k]]++;

            int ans2 = 0;

            for (k = j + 1; k < n; k++) 
            {
                ans2 += mp[req - a[k]];
                if (req - a[k] == a[k])
                    ans2--;
            }
            ans += ans2 / 2;
        }
    }
    return ans;
}

int main()
{
    int arr[] = {2, 2, 2, 2, 2 };

    int S = 8;

    int N = sizeof(arr) / sizeof(arr[0]);
    cout << solve(arr, N, S);
    return 0;
}

Output

5

Python Programming

def solve(a, n, total):
    ans = 0
    # All possible first elements
    for i in range(n - 3):
        # All possible second elements
        for j in range(i + 1, n - 2, 1):
            req = total - a[i] - a[j]
            mp = {}
        
            for k in range(j + 1, n, 1):
                mp[a[k]] = mp.get(a[k], 0) + 1

            ans2 = 0
        
            for k in range(j + 1, n, 1):
                ans2 += mp.get(req - a[k], 0)
                if (req - a[k] == a[k]):
                    ans2 -= 1
            ans += ans2 // 2
    return ans

arr = [2, 2, 2, 2, 2]
S = 8
N = len(arr)
print(solve(arr, N, S))

Output

Vamware
5

C# Programming

using System;
using System.Collections.Generic;

class Solution{
static int solve(int []a, int n,int sum)
{
    // Initialize variables
    int i, j, k;

    // Initialize answer
    int ans = 0;

    // All possible first elements
    for(i = 0; i < n - 3; i++)
    {
        // All possible second element
        for(j = i + 1; j < n - 2; j++)
        {
            int req = sum - a[i] - a[j];

            Dictionary<int,int> mp = new Dictionary<int,int>();

            for(k = j + 1; k < n; k++)
                if (mp.ContainsKey(a[k]))
                {
                    mp[a[k]]++;
                }

                else
                {
                    mp.Add(a[k], 1);
                }

            int ans2 = 0;

            // Calculate number of valid
            // 4th elements
            for(k = j + 1; k < n; k++)
            {
                // Update the ans2
                if (mp.ContainsKey(req - a[k]))
                    ans2 += mp[req - a[k]];

                if (req - a[k] == a[k])
                    ans2--;
            }
            ans += ans2 / 2;
        }
    }

    return ans;
}

public static void Main(String[] args)
{
    int []arr = {2, 2, 2, 2, 2};
    int S = 8;
    int N = arr.Length;
    Console.Write(solve(arr, N, S));
}
}

Output

5

People are also reading:

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published.