Estimating Algorithm Processing Time and Optimizing Brute-Force Solutions by Picking Optimal Variable for Brute Force

Introduction

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

Task Statement

Here's the task at hand: You have to write a Python 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. Should there be multiple sets that meet this condition, your function should return any one of them. If no such quad exists, the function should return an empty list. Consider this list as an example: [5, 15, 2, 7, 8, 4] . If your target sum is 24, a four-number set that adds up to this value could be [5, 7, 4, 8] . The input list will contain at least 4 and at most 1000 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

Solution Building: Step 3

On to the last step! We will now scan all pairs, and for each, we will calculate the difference between the target sum and the pair sum, searching for this difference value in the dictionary. For successful searches, we validate that the elements do not belong to more than one pair. If we find such combinations, we return the four numbers. However, if we traverse all pairs and fail to find a suitable set, we return an empty list.

Python

def find_quad_sum(target_sum, numbers):
    length = len(numbers)
    sum_dict = {}

    for i in range(length - 1):
        for j in range(i + 1, length):
            pairwise_sum = numbers[i] + numbers[j]
            if pairwise_sum not in sum_dict:
                sum_dict[pairwise_sum] = [(i, j)]
            else:
                sum_dict[pairwise_sum].append((i, j))
    
    for i in range(length - 1):
        for j in range(i + 1, length):
            total = numbers[i] + numbers[j]
            diff = target_sum - total
            if diff in sum_dict:
                pairs = sum_dict[diff]
                for pair in pairs:
                    x = pair[0]
                    y = pair[1]
                    if (x != i and x != j and y != i and y != j):
                        return [numbers[i], numbers[j], numbers[x], numbers[y]]
    return []

def find_quad_sum(target_sum, numbers):
    length = len(numbers)
    sum_dict = {}

    for i in range(length - 1):
        for j in range(i + 1, length):
            pairwise_sum = numbers[i] + numbers[j]
            if pairwise_sum not in sum_dict:
                sum_dict[pairwise_sum] = [(i, j)]
            else:
                sum_dict[pairwise_sum].append((i, j))
    
    for i in range(length - 1):
        for j in range(i + 1, length):
            total = numbers[i] + numbers[j]
            diff = target_sum - total
            if diff in sum_dict:
                pairs = sum_dict[diff]
                for pair in pairs:
                    x = pair[0]
                    y = pair[1]
                    if (x != i and x != j and y != i and y != j):
                        return [numbers[i], numbers[j], numbers[x], numbers[y]]
    return []

Note that since the integers in the array are distinct, the list pairs doesn't contain pairs that share the same number, so the loop on the 19th line doesn't do more than two steps.

Introduction

Task Statement

Estimating Program Evaluation Time

Join the 1M+ learners on CodeSignal

Solution Explanation

Solution Building: Step 1

Solution Building: Step 2

Solution Building: Step 3

Lesson Summary