Challenge: Two Sum

Lab Python Beginner 10 points

Read a list of numbers and a target. Print the positions (indexes, starting at 0) of the two numbers that add up to the target, smaller index first. There is exactly one answer. Aim for O(n) with a dictionary.

Input

Line 1: whole numbers. Line 2: the target.

Output

i j

Example

Input

2 7 11 15
9

Output

0 1

Sample input available Sample output available

Editor

Python

Hints

For each number x, the partner you need is target - x.

Store number -> index in a dict as you go.

Solution explanation

One pass; each lookup in the dictionary is O(1), so the total is O(n).

Show solution

nums = list(map(int, input().split()))
target = int(input())
seen = {}
for i, x in enumerate(nums):
    if target - x in seen:
        print(seen[target - x], i)
        break
    seen[x] = i

Output

Answer