Finding Quadruple Sums

Finding Quadruple Sums | CodeSignal Learn

Introduction

Hello there! Get ready as we dive into an intriguing problem that involves list manipulation, combinatorial logic, and some Scala skills . This problem centers around finding combinations in a given list whose sum is equivalent to a specified target value . Are you ready for a challenging endeavor? Great! Let's jump into the world of Scala and number theory.

Task Statement

Here's the task at hand: You have to write a Scala function that accepts a list of distinct integers and a target sum as input. The aim is to identify exactly four numbers in the list that, when summed, equal this target. If there are multiple sets that meet this condition, your function should return any one of them. If no such quadruple exists, the function should return an empty list. Consider this list as an example: List(5, 15, 2, 7, 8, 4) . If your target sum is 24, a four-number set that adds up to this value could be List(5, 7, 4, 8) . The input list will contain at least 4 and at most 1,000 distinct integers. The input integers will be in the range -10^6 to 10^6. The target sum will also be in the range of -10^6 to 10^6. There is a time limit for the solution to evaluate within 3 seconds.

Estimating Program Evaluation Time

O(N^4)

Join the 1M+ learners on CodeSignal

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

The simplest solution is the brute-force approach that iterates over every quadruple of numbers in the array. The complexity of this solution is $O(N^4)$ .

Assuming that performing an elementary operation in Scala can take a small amount of time (often in the range of nanoseconds to microseconds), if we have a list of a thousand distinct integers, the total time to perform our $O(N^4)$ operation on our list would be extremely large — potentially taking hours or even days. This is definitely not an optimal solution.

If we have a solution with a time complexity of $O(N^3)$ , this can be achieved by iterating over only three elements and checking if target - element1 - element2 - element3 exists in the given list using a set or map. With an input list of a thousand integers, the operation time reduces significantly, but it may still be too slow for practical use.

Ultimately, if we have a solution with a complexity of $O(N^2)$ (like the one we will build in our lesson), the operation time on a thousand-integer list becomes very quick — well within the 3-second time limit.

These estimated time evaluations highlight why it is critical to craft optimized solutions that improve time complexity. Our planned solution (with a time complexity of $O(N^2)$ ) will be considerably faster even for larger inputs, making it highly useful and efficient.

Solution Building: Step 1

The initial strategic move is to initialize an empty mutable Map . We'll use this map to store sums of all pairs of numbers in the list as keys, with indices of the number pairs as the corresponding values. This strategy will prove beneficial when we search for pairs that meet our conditions later. Scala import scala.collection.mutable def findQuadSum(targetSum: Int, numbers: List[Int]): List[Int] = {val length = numbers.length val sumMap = mutable.Map[Int, List[(Int, Int)]]() import scala.collection.mutable def findQuadSum(targetSum: Int, numbers: List[Int]): List[Int] = {val length = numbers.length val sumMap = mutable.Map[Int, List[(Int, Int)]]()

Solution Building: Step 2

Now, let's populate the map. For each pair of integers in the list, we'll calculate their sum and store it as a key in the map, using the indices of the pair as the values. Scala import scala.collection.mutable def findQuadSum(targetSum: Int, numbers: List[Int]): List[Int] = {val length = numbers.length val sumMap = mutable.Map[Int, List[(Int, Int)]]() for (i <- 0 until length - 1) {for (j <- i + 1 until length) {val pairwiseSum = numbers(i) + numbers(j) val pairs = sumMap.getOrElse(pairwiseSum, List()) sumMap(pairwiseSum) = (i, j) :: pairs}} import scala.collection.mutable def findQuadSum(targetSum: Int, numbers: List[Int]): List[Int] = {val length = numbers.length val sumMap = mutable.Map[Int, List[(Int, Int)]]() for (i <- 0 until length - 1) {for (j <- i + 1 until length) {val pairwiseSum = numbers(i) + numbers(j) val pairs = sumMap.getOrElse(pairwiseSum, List()) sumMap(pairwiseSum) = (i, j) :: pairs}}

Solution Building: Step 3

To effectively solve this problem using Scala, we employ an optimized approach with a time complexity of $O(N^2)$ , leveraging mutable maps for fast lookups.

Conceptual Breakdown:

Store Pair Sums: We initialize a mutable Map to keep track of all possible pairs of numbers and their sums. The keys of this map will be these sums, and the values will be the pairs of indices that make up the sums.
Finding Complement Pairs: For each pair of numbers in the array, calculate the difference between the target sum and the current pair’s sum. This difference represents the sum needed from another pair of numbers.
Verify Distinct Indices: Using our map, check if there exists a pair in the array that adds up to this difference and ensure that none of these indices overlap with the initial pair. If such pairs exist, we return these four numbers as our result.

Why This Works:

Efficiency: Using a mutable Map allows for constant time complexity on average for insertion and lookup operations, dramatically speeding up our process compared to a brute-force solution.
Scalability: Even with the maximum limit of 1,000 entries, this method ensures prompt execution well within the acceptable limits.