Sum Find A Quadruplet With Closest Sum In C++

The task of finding a quadruplet with the closest sum, known as the 4 Sum problem, is classified within the realm of k-Sum problems. These problems are centered around identifying a group of numbers that add up to a specific target value or an approximation of it. In this scenario, the objective is to identify four numbers (referred to as a quadruplet) from respective arrays, whose total closely matches a predefined target sum.

To resolve this problem, effective sorting techniques like sorting and the two-pointer approach are usually employed to reduce the time complexity. The initial pair of numbers can be determined through two loops after sorting the array, while the remaining pair can be identified using the two-pointer method, resulting in an overall problem complexity of O(n^3). Utilizing the sorted array facilitates a systematic exploration of combinations, and leveraging two pointers enables the manipulation of the search process based on the sum of the current quadruplet to find a value that closely matches the target sum.

The objective is to continually approach the target sum by refining the sum during the optimization process. Each time a more accurate quadruplet sum is achieved, it supersedes any previous findings. Once the exact sum matching the goal is identified, the search can be halted as there will be no better solution.

This exercise provides further opportunity to practice optimization strategies like sorting and the two-pointer technique, as well as encouraging the use of the most efficient language for solving it. It also highlights the importance of employing suitable data structures and algorithms when dealing with larger sets of data to avoid potential performance issues.

Approach-1: Brute-Force Approach

Utilizing the brute force technique may be considered simple to execute when tackling the 4 Sum challenge, however, it is notably lacking in efficiency. This method involves examining every potential combination of four elements within the input array to identify the optimal grouping that closely matches the specified target value.

Program:

Let's consider a scenario to demonstrate the 4 sum issue by employing the Brute-Force Method in C++.

#include <iostream>
#include <vector>
#include <climits> // For INT_MAX and INT_MIN
#include <cmath>   // For abs()
#include <algorithm> // For sort function
//Function to find the quadruplet with the closest sum to a given target
int fourSumClosest(std::vector<int>& nums, int target) {
    int n = nums.size(); // Get the size of the input array
    // Edge case: If there are less than 4 numbers, we can't form a quadruplet
    if (n < 4) {
        std::cerr << "Error: The array must contain at least four numbers." << std::endl;
        return 0; // Handle this situation as needed
    }
    //Variable to store the closest sum found, initialized to a very large value
    int closestSum = INT_MAX;
    // Nested loops to generate all combinations of four distinct elements
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                for (int l = k + 1; l < n; l++) {
                    // Calculate the sum of the current quadruplet
                    int currentSum = nums[i] + nums[j] + nums[k] + nums[l];
                    // Check if the current sum is closer to the target than the previous closest sum
                    if (abs(currentSum - target) < abs(closestSum - target)) {
                        closestSum = currentSum; // Update the closest sum if a closer one is found
                    }
                }
            }
        }
    }
    return closestSum; // Return the closest sum found
}
//Function to display the input array and the target sum
void displayInput(const std::vector<int>& nums, int target) {
    std::cout << "Input array: ";
    for (int num : nums) {
        std::cout << num << " "; // Print each number in the input array
    }
    std::cout << "\nTarget sum: " << target << std::endl; // Print the target sum
}
//Function to test the fourSumClosest Function with multiple test cases
void testFourSumClosest() {
    // Define multiple test cases
    std::vector<std::vector<int>> testCases = {
        {1, 2, -1, -4, -2, 3, 0},
        {5, 3, 2, 7, 8, 10, -1},
        {0, 0, 0, 0},
        {1, 1, 1, 1, 1, 1},
        {-1, 2, 1, -4, 3, 0, 0, -2}
    };
    // Define corresponding target sums for each test case
    std::vector<int> targets = {1, 12, 0, 4, 1};
    // Iterate through each test case
    for (size_t i = 0; i < testCases.size(); ++i) {
        std::vector<int> nums = testCases[i];
        int target = targets[i];
        // Display the current test case input and target
        displayInput(nums, target);
        // Call the Function to find the closest sum and store the result
        int result = fourSumClosest(nums, target);
        // Output the result for the current test case
        std::cout << "The closest sum to the target " << target << " is: " << result << std::endl;
        // Separator for clarity
    }
}
// Main Function to run the tests
int main() {
    // Test the fourSumClosest Function with predefined test cases
    testFourSumClosest();
    return 0; // Indicate successful program termination
}

Output:

Input array: 1 2 -1 -4 -2 3 0 
Target sum: 1
The closest sum to the target 1 is: 1
Input array: 5 3 2 7 8 10 -1 
Target sum: 12
The closest sum to the target 12 is: 12
Input array: 0 0 0 0 
Target sum: 0
The closest sum to the target 0 is: 0
Input array: 1 1 1 1 1 1 
Target sum: 4
The closest sum to the target 4 is: 4
Input array: -1 2 1 -4 3 0 0 -2 
Target sum: 1
The closest sum to the target 1 is: 1

Explanation:

• ✅ In this example, the <vector> header allows the use of the dynamic array type std::type or requires a vector that is essential for working with sets of numbers.
• ✅ It offers utility macros, such as INT_MAX, which can be used to set the variable holding the sought item to an extremely large value against which to compare. It contains basic mathematical operations like abs, which finds an absolute difference.

Function fourSumClosest:

• ✅ This Function has two input parameters: nums, a vector of integers, and target, an integer representing the closest sum. The Function returns any quadruplet closest to the target.
• ✅ The Function first performs an if statement to determine whether the size of the input vector is less than four. If so, it prints an error message and does not proceed further because it is impossible to form a quadruplet with less than four elements.
• ✅ The value assigned to the adjacent sum closestSum is the maximum value of the Int type, INT_MAX, to guarantee that any computed quadruplet sum encountered during the iterations can overwrite this initial value.

Nested Loops:

• ✅ The core of the brute-force approach is the four nested loops , which generate all possible combinations of four distinct elements from the input vector.
• ✅ The outer Loop selects the first number, and the second Loop selects the second number. After each Loop, the next starts from the index value of the chosen number to avoid repeating the same values and greatly increasing the difference between the lists.
• ✅ For each of these combinations, the sum of four chosen randomly selected numbers is computed.

The existing total of the group of four numbers is computed prior to this procedure designating it as the nearest to the desired value if it is closer than the previous closest total. This assessment involves using the abs method on the sums to determine the absolute variance. Should the present total be nearer, it replaces the closestSum.

The function for displaying input:

When this function is invoked, it will output the array of input values alongside the desired sum. This feature serves as an aid in illustrating the input data while conducting tests.

Testing Procedure:

• ✅ The C++ file link additionally displays the testFourSumClosest function, which consists of various test scenarios using arrays as inputs and a target sum. In each scenario, it calls the fourSumClosest function and displays the output, aiding in the verification of the function more effectively.

Complexity Analysis:

Time Complexity

The time complexity of this brute-force method is determined to be O(n^4). This complexity arises from the four nested loops used to iterate through the array:

• ✅ Outer Loop: The first Loop runs from the first index to the fourth from the last index of the list.
• ✅ Second Loop: The second Loop starts from the next element to the first and moves to the third-last element.
• ✅ Third Loop: The third Loop starts right after the second loop index and ends at the second to last element.
• ✅ Innermost Loop: The innermost Loop begins just after the third Loop's index and goes all the way up to the last element of the array.

Given this context, as each iteration of the loop is dependent on the previous one, the total combinations assessed correspond to a polynomial function of the input array's magnitude, precisely a polynomial of the 4th degree. Consequently, the iteration count escalates with the input size, posing a significant challenge for extensive datasets and leading to a notable decline in processing efficiency.

Space Complexity

The approach's space complexity is fixed at O(1), indicating that the algorithm consumes a consistent amount of additional space beyond the input array's needs. The indicesalloc, currentsum, and best_sum variables are employed to retain the indices, current total, and optimal total, respectively. These variables remain constant regardless of the input's scale. Therefore, the algorithm operates efficiently without requiring auxiliary data structures that scale proportionally with the input size, preserving memory.

Approach-2: Sorting and Two-Pointer Technique

Utilizing and selecting the Two-Pointer technique proves to be an effective strategy for solving the 4 Sum problem. This approach significantly reduces the time complexity by half when compared to the brute force sorting method combined with the two-pointer method mentioned earlier.

Program:

Let's consider a scenario to demonstrate the problem of finding four elements that sum up to a target using the Sorting and Two-Pointer approach in C++.

#include <iostream>
#include <vector>
#include <algorithm> // For sort and abs
#include <climits>   // For INT_MAX
//Function to find the quadruplet with the closest sum to a given target
int fourSumClosest(std::vector<int>& nums, int target) {
    int n = nums.size(); // Get the size of the input array
    // Edge case: If there are less than 4 numbers, we can't form a quadruplet
    if (n < 4) {
        std::cerr << "Error: The array must contain at least four numbers." << std::endl;
        return 0; // Handle this situation as needed
    }
    // Sort the array to use the two-pointer technique
    std::sort(nums.begin(), nums.end());
    //Variable to store the closest sum found, initialized to a very large value
    int closestSum = INT_MAX; 
    //Loop through each element, fixing the first number
    for (int i = 0; i < n - 3; i++) {
        // Avoid duplicate first numbers
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        // Fix the second number
        for (int j = i + 1; j < n - 2; j++) {
            // Avoid duplicate second numbers
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            // Initialize two pointers for the third and fourth numbers
            int left = j + 1; // Pointer to the third number
            int right = n - 1; // Pointer to the fourth number
            // While there are elements between the left and righcpp tutorialers
            while (left < right) {
                // Calculate the sum of the four numbers
                int currentSum = nums[i] + nums[j] + nums[left] + nums[right];
                // Check if the current sum is closer to the target than the previously found closest sum
                if (abs(currentSum - target) < abs(closestSum - target)) {
                    closestSum = currentSum; // Update the closest sum
                }
                // Move pointers based on the comparison with the target
                if (currentSum < target) {
                    left++; // Increase the sum by moving the lefcpp tutorialer to the right
                } else if (currentSum > target) {
                    right--; // Decrease the sum by moving the righcpp tutorialer to the left
                } else {
                    // If we find an exact match, we can return it immediately
                    return currentSum;
                }
            }
        }
    }
    return closestSum; // Return the closest sum found
}
//Function to display the input array and the target sum
void displayInput(const std::vector<int>& nums, int target) {
    std::cout << "Input array: ";
    for (int num : nums) {
        std::cout << num << " "; // Print each number in the input array
    }
    std::cout << "\nTarget sum: " << target << std::endl; // Print the target sum
}
//Function to test the fourSumClosest Function with multiple test cases
void testFourSumClosest() {
    // Define multiple test cases
    std::vector<std::vector<int>> testCases = {
        {1, 2, -1, -4, -2, 3, 0},
        {5, 3, 2, 7, 8, 10, -1},
        {0, 0, 0, 0},
        {1, 1, 1, 1, 1, 1},
        {-1, 2, 1, -4, 3, 0, 0, -2}
    };
    // Define corresponding target sums for each test case
    std::vector<int> targets = {1, 12, 0, 4, 1};
    // Iterate through each test case
    for (size_t i = 0; i < testCases.size(); ++i) {
        std::vector<int> nums = testCases[i];
        int target = targets[i];
        // Display the current test case input and target
        displayInput(nums, target);
        // Call the Function to find the closest sum and store the result
        int result = fourSumClosest(nums, target);
        // Output the result for the current test case
        std::cout << "The closest sum to the target " << target << " is: " << result << std::endl;
    }
}
// Main Function to run the tests
int main() {
    // Test the fourSumClosest Function with predefined test cases
    testFourSumClosest();
    return 0; // Indicate successful program termination
}

Output:

Input array: 1 2 -1 -4 -2 3 0 
Target sum: 1
The closest sum to the target 1 is: 1
Input array: 5 3 2 7 8 10 -1 
Target sum: 12
The closest sum to the target 12 is: 12
Input array: 0 0 0 0 
Target sum: 0
The closest sum to the target 0 is: 0
Input array: 1 1 1 1 1 1 
Target sum: 4
The closest sum to the target 4 is: 4
Input array: -1 2 1 -4 3 0 0 -2 
Target sum: 1
The closest sum to the target 1 is: 1

Explanation:

• ✅ The main Function, fourSumClosest, takes an Indeed vector, which contains some integers and an Integral target as arguments. First, it verifies whether the size of the array is less than four and if that is the case, it returns an error.
• ✅ Following sorting the array for the two-pointer technique, the Function uses two cycles to adjust the first two constituents of the quadruplet. For each fixed pair, two pointers (left and right) are set as the potential candidates for the rest of the two numbers.
• ✅ The total of four selected numbers is calculated and then compared with the intended total. Moreover, the displayInput Function prints the input array and target for clarity during testing. The testFourSumClosest Function considers multiple test scenarios, calling fourSumClosest and displaying its result.
• ✅ Thus, the method achieves good improvements with the time complexity steadied at O(n^3) better than the brute-force method for larger data sets. Overall, the code structure permits structural testing and highly reliable results can be obtained even under the condition of applicable variations and shades of the scenarios in question. At the same time, the code runs with high lexicality without mixed functionality.

Complexity Analysis:

Time Complexity:

• ✅ The technique used in the 4 Sum-Find a quadruplet with the closest sum problem, identified as the Sorting and Two-Pointer Technique, has a time complexity of (O(n3)). This is because sorting the given input array and the nested loops used to identify the pairs are complex.
• ✅ Hence, the sorting operation is of order (O(n logn)). The first Loop that makes a pass through the array contributes to the time of order (O N2), and the second Loop also makes a pass through the array contribute to the time of order (O (n2).
• ✅ The innermost Loop combined with the two-pointer technique still requires time for the rest of the elements, making the whole Function on average (O(n3)). Consequently, the algorithm fairly reduces the search space, which favors it for large input sizes, outdoing the brute force approach.

Space Analysis:

The space complexity of this method is (O(1)), indicating that the algorithm only requires a fixed amount of additional space. Minimal extra storage is employed, primarily consisting of integer variables for various purposes such as indices, sums, and the closest identified sum. The original array is rearranged without the need for any additional data structures, resulting in space usage directly related to the input size. This optimal utilization of both time and space resources enhances the effectiveness of the Sorting and Two-Pointer Technique when tackling the 4 Sum problem.