Challenge: Two Tickets for the Budget

Lab Java Intermediate 20 points

Read n ticket prices and a budget. Find two different tickets whose prices add up to exactly the budget. Print their positions i j (from 0, i < j) for the pair whose second ticket comes earliest; if that ticket matches several earlier ones, use the earliest. Print -1 if no pair exists. Aim for O(n) with a HashMap from price to first position.

Input

Line 1: n budget. Line 2: n prices.

Output

i j, or -1.

Example

Input

5 85
40 15 70 25 60

Output

1 2

Sample input available Sample output available

Editor

Java

Hints

Walk left to right. For a[j], look up budget - a[j] in the map.

Only store a price the first time you see it, so the earliest position wins.

Solution explanation

Each ticket is looked at once and every map lookup is O(1) on average: O(n) instead of checking all pairs.

Show solution

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), budget = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        HashMap<Integer, Integer> firstAt = new HashMap<Integer, Integer>();
        for (int j = 0; j < n; j++) {
            Integer i = firstAt.get(budget - a[j]);
            if (i != null) {
                System.out.println(i + " " + j);
                return;
            }
            if (!firstAt.containsKey(a[j])) firstAt.put(a[j], j);
        }
        System.out.println(-1);
    }
}

Output

Answer