4–Sum Problem | Quadruplets with a given sum

Posted in

4–Sum Problem | Quadruplets with a given sum
vinaykhatri

Vinay Khatri
Last updated on March 28, 2024

    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:

    Leave a Comment on this Post

    0 Comments