Solution 1 - Hashmap

Using a hash map, we can store the numbers in the array as keys and their indices as values. To check if a pair exists, we use the hashmap to quickly look up if any past value plus the current one equals xx. If so, we output the current index and the one stored in the hashmap.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

Warning!

Note that this code uses std::map instead of std::unordered_map, which does add a log factor to the complexity. This is because CSES has anti-hash test cases, which are specifically designed to heavily slow down unordered maps.

#include <iostream>
#include <map>


using namespace std;


int main() {
	int n;
	int x;
	cin >> n >> x;

Java

import java.io.*;
import java.util.*;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());

Python

Warning!

The below code TLEs on a couple test cases due to anti-hashing test cases on CSES.

n, x = map(int, input().split())
nums = list(map(int, input().split()))


m = {}
for i, a in enumerate(nums):
	if x - a in m:
		print(i + 1, m[x - a] + 1)
		break
	m[a] = i
else:
	print("IMPOSSIBLE")

Solution 2 - Two Pointers

We can sort the array and use a left pointer and right pointer. If the sum is greater than xx, we decrement right. If the sum is less than xx, we increment left.

Implementation

Time Complexity: O(Nlog⁡N)\mathcal{O}(N\log N)

C++

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>


using namespace std;


int main() {
	int n, x;
	cin >> n >> x;

Java

import java.io.*;
import java.util.*;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());

Python

n, x = map(int, input().split())


nums = [(int(val), i) for i, val in enumerate(input().split())]
nums.sort()


l = 0
r = n - 1
while l < r:
	sum = nums[l][0] + nums[r][0]
	if sum == x:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum