Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they pool together
m
dollars for ice cream. On any given day, the parlor offers a line ofn
flavors. Each flavor,i
, is numbered sequentially with a unique ID number from1
ton
and has a cost, , associated with it.Given the value of
m
and the cost of each flavor fort
trips to the Ice Cream Parlor, help Sunny and Johnny choose two flavors such that they spend their entire pool of money (m
) during each visit. For each trip to the parlor, print the ID numbers for the two types of ice cream that Sunny and Johnny purchase as two space-separated integers on a new line. You must print the smaller ID first and the larger ID second.Note: Two ice creams having unique IDs and may have the same cost
Input Format
The first line contains an integer,
t
, denoting the number of trips to the ice cream parlor. The3t
subsequent lines describe all of Sunny and Johnny's trips to the parlor; each trip is described as follows:Output Format
Print two space-separated integers denoting the respective ID numbers for the flavors they choose to purchase, where the smaller ID is printed first and the larger ID is printed second. Recall that each ice cream flavor has a unique ID number in the inclusive range from
1
ton
.
public class Solution {
private static int[] solve(int m, int []costs) {
int []indexes = new int[]{-1, -1};
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < costs.length; i++) {
int cost = costs[i];
int diff = m- cost;
if (diff < 0) continue;
Integer index = map.get(diff);
if (index == null) {
map.put(cost, i + 1);
}
else {
indexes = new int[]{map.get(diff), i + 1};
break;
}
}
return indexes;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int T = s.nextInt();
for (int j = 0; j < T; j++) {
int M = s.nextInt();
int N = s.nextInt();
int []costs = new int[N];
for (int i = 0; i < N; i++) {
costs[i] = s.nextInt();
}
int []result = solve(M, costs);
System.out.println(result[0] + " " + result[1]);
}
}
}
I was able to relate this problem to the pair sum and my solution the implements same.