Sum Of Three Values

May 30, 2023

Explanation

Here, we are given an array of n integers, and a number target. We need to find positions of 3 numbers whose sum equals to target.

We can do this using the help of the previous problem similar to this Sum of Two Values. We will select a number, then use target - number as the new target and select two values for it.

For the sum_of_two_values function, you can either use a hashmap/dictionary or a two pointer approach. I've used the two pointer approach here, as I've shown the hashmap approach in the previous problem.

Code

# Please use `PyPy3` instead of `CPython3` to avoid TLE
from typing import List, Tuple

n, target = map(int, input().split())
numbers = sorted(map(
    lambda x: (x[1], x[0]),
    enumerate(list(map(int, input().split())))
))

def sum_of_two_values(target: int, arr: List[Tuple[int, int]]) -> Tuple[int, int]:
    left = 0
    right = len(arr) - 1
    while right > left:
        current_sum = arr[left][0] + arr[right][0]
        if current_sum == target:
            return arr[left][-1], arr[right][-1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return -1, -1

for i in range(n):
    j, k = sum_of_two_values(target - numbers[i][0], numbers[i + 1:])
    if j != -1 and k != -1:
        print(numbers[i][-1] + 1, j + 1, k + 1)
        break
else:
    print("IMPOSSIBLE")