Finding Four Numbers That Sum to a Target Using C#

Introduction

Hello! Get ready to dive into an intriguing problem involving list manipulation and combinatorial logic. We will explore the challenge of finding combinations in a given list that add up to a specific target value. Are you prepared for an exciting journey? Let's delve into the world of number theory and C# .

Task Statement

Here's your challenge: Write a C# method that takes an array of distinct integers and a target sum as inputs. The goal is to find exactly four numbers in the array that, when added together, equal the target. If multiple sets satisfy this condition, your method should return any one of them. If no such combination exists, the method should return an empty array. Take this array as an example: [5, 15, 2, 7, 8, 4] . If your target sum is 24, a possible four-number set that adds up to this value could be [5, 7, 4, 8] . The input array will contain at least 4 and at most 1,000 distinct integers. The input integers will be in the range of -1,000,000 to 1,000,000. The target sum will also be within the same range. The solution must run within a time limit of 3 seconds.

Estimating Program Evaluation Time

The simplest solution is the brute-force approach that iterates over every quadruple combination of numbers in the array. The complexity of this approach is O(N^4). Assuming performing an elementary operation in C# takes about 100 nanoseconds, then for an array with a thousand distinct integers, the time taken for an O(N^4) operation would be around 100 * 1000^4 = 10^{14} nanoseconds, equating to over 27 hours. This is clearly not efficient. What if we use a solution with a time complexity of O(N^3)? By iterating over three elements and checking if target - element1 - element2 - element3 exists in the array utilizing a Dictionary, we can reduce the computation time for a thousand integers to approximately 100 seconds. While this demonstrates an improvement, further optimization is possible. By implementing a solution with O(N^2) complexity (as shown in this lesson), the time for processing a thousand integers can drop to around 1 second. It's important to note that not all operations are elementary, and some may increase the time by a constant factor. Nonetheless, this constant is usually manageable, ensuring the process stays well within a 3-second timeframe. These estimations highlight why it's crucial to develop optimized solutions for better time complexity. The solution in this lesson with O(N^2) complexity proves to be significantly faster, especially for larger datasets, making it a practical and efficient choice.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Finding the Quad

Finally, scan all pairs and, for each, compute the difference between the target sum and the pair sum. Look for this difference in the Dictionary. Verify that elements do not share indices across pairs. Upon finding valid combinations, return the four numbers. If no set is found, return an empty array.

using System;
using System.Collections.Generic;

public class QuadSumFinder
{
    public static int[] FindQuadSum(int targetSum, int[] numbers)
    {
        int length = numbers.Length;
        var sumMap = new Dictionary<int, List<(int, int)>>();

        // Step 1: Populate the Dictionary with the sums of all pairs.
        for (int i = 0; i < length - 1; ++i)
        {
            for (int j = i + 1; j < length; ++j)
            {
                int pairwiseSum = numbers[i] + numbers[j];
                if (!sumMap.ContainsKey(pairwiseSum))
                {
                    sumMap[pairwiseSum] = new List<(int, int)>();
                }
                sumMap[pairwiseSum].Add((i, j));
            }
        }

        // Step 2: Search for complement pairs.
        foreach (var kvp in sumMap)
        {
            int sum = kvp.Key;
            int complement = targetSum - sum;
            if (sumMap.ContainsKey(complement))
            {
                var pairs1 = sumMap[sum];
                var pairs2 = sumMap[complement];

                foreach (var pair1 in pairs1)
                {
                    foreach (var pair2 in pairs2)
                    {
                        var (a, b) = pair1;
                        var (c, d) = pair2;

                        // Ensure all indices are distinct.
                        if (a != c && a != d && b != c && b != d)
                        {
                            return new int[] { numbers[a], numbers[b], numbers[c], numbers[d] };
                        }
                    }
                }
            }
        }

        return new int[0];
    }

    // Example usage:
    public static void Main()
    {
        int[] numbers = { 5, 15, 2, 7, 8, 4 };
        int target = 24;
        int[] result = FindQuadSum(target, numbers);
        Console.WriteLine(string.Join(", ", result)); // Output: 5, 7, 8, 4
    }
}

using System;
using System.Collections.Generic;

public class QuadSumFinder
{
    public static int[] FindQuadSum(int targetSum, int[] numbers)
    {
        int length = numbers.Length;
        var sumMap = new Dictionary<int, List<(int, int)>>();

        // Step 1: Populate the Dictionary with the sums of all pairs.
        for (int i = 0; i < length - 1; ++i)
        {
            for (int j = i + 1; j < length; ++j)
            {
                int pairwiseSum = numbers[i] + numbers[j];
                if (!sumMap.ContainsKey(pairwiseSum))
                {
                    sumMap[pairwiseSum] = new List<(int, int)>();
                }
                sumMap[pairwiseSum].Add((i, j));
            }
        }

        // Step 2: Search for complement pairs.
        foreach (var kvp in sumMap)
        {
            int sum = kvp.Key;
            int complement = targetSum - sum;
            if (sumMap.ContainsKey(complement))
            {
                var pairs1 = sumMap[sum];
                var pairs2 = sumMap[complement];

                foreach (var pair1 in pairs1)
                {
                    foreach (var pair2 in pairs2)
                    {
                        var (a, b) = pair1;
                        var (c, d) = pair2;

                        // Ensure all indices are distinct.
                        if (a != c && a != d && b != c && b != d)
                        {
                            return new int[] { numbers[a], numbers[b], numbers[c], numbers[d] };
                        }
                    }
                }
            }
        }

        return new int[0];
    }

    // Example usage:
    public static void Main()
    {
        int[] numbers = { 5, 15, 2, 7, 8, 4 };
        int target = 24;
        int[] result = FindQuadSum(target, numbers);
        Console.WriteLine(string.Join(", ", result)); // Output: 5, 7, 8, 4
    }
}

Introduction

Task Statement

Estimating Program Evaluation Time

Join the 1M+ learners on CodeSignal

Solution Explanation

Initializing the Dictionary

Populating the Dictionary

Finding the Quad

Lesson Summary