CSES - Sum of Two Values

Authors: Michael Cao, DRGSH, Benjamin Qi

Appears In

Given an array of nn elements, you are asked to find two values which sum to xx.

Main Idea

Let's start by iterating over the first value in O(n)\mathcal{O}(n) time. Given one value, aa, the other value must be x−ax - a unless a>xa > x (in which case aa cannot be a valid first value).

So the question reduces to, given some value aa, does some other value x−ax - a exist?

Python

Using a Dictionary

C++

Using a Map

Java

Using a Map

One idea that comes to mind would be to used a boolean array to store the values. Unfortunately, since ai≤109a_i \leq 10^9, this approach isn't feasible.

Python

However, we can store the values in a dictionary which maps each value to an index, and use the __contains__ dunder method to check whether a value exists, and return the corresponding index if it does.

C++

However, we can store the values in an (un)ordered map which maps each value to an index, and use the .count method to check whether a value exists, and return the corresponding index if it does.

Java

However, we can store the values in a map which maps each value to an index, and use the .containsKey method to check whether a value exists, and return the corresponding index if it does.

To be careful not to count the same index twice, we'll add values to the map as we iterate through it, so at some index ii you only consider values with index j<ij < i.

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first

Python

import sys


n,x = map(int,input().split())
a = [int(x) for x in input().split()]


val_to_ind = {}
for i,val in enumerate(a):
	if x-val in val_to_ind: 
		# equivalent to val_to_ind.__contains__(x-val)
		print(i+1,val_to_ind[x-val])
		sys.exit(0)
	val_to_ind[val] = i+1
		
print("IMPOSSIBLE")

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