4–Sum Problem | Quadruplets with a given sum

Problem

The goal is to count all the quadruplets having a 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 the sum ( S – arr [i] – arr [j] ). After finding the ans2 , update the ans by ans / 2 .

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

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:

• Print given series:1 2 4 8 16 32 64 128
• Find quotient and remainder of two numbers
• Program to Find the Factors of Number
• Python Program to Make a Simple Calculator
• Find the Sum of Natural Numbers
• Python Program to Check Armstrong Number
• Program to Display the Multiplication Table
• Python Program to Merge Mails
• WAP to Find the Sum of Series 1+x+x^2+……+x^n
• Python Program to Transpose a Matrix