CSES - Sum of Two Values

Authors: Michael Cao, Benjamin Qi, Brad Ma, Ryan Chou, David Zhang

Edit This Page

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

Solution 1 - Dictionary/Map

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.

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.

Python

However, we can store the values in a dictionary which maps each value to an index. Then, we can use the dictionary to check in O(1)\mathcal{O}(1) time get the corresponding index for a value (if there is one).

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;


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


	vector<int> values(n);
	for (int i = 0; i < n; i++) { cin >> values[i]; }

Java

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


public class TwoSum {
	public static void main(String[] args) {
		Kattio io = new Kattio();


		int n = io.nextInt();
		int target = io.nextInt();

Python

import sys


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


# use a map to avoid using a very large array
val_to_ind = {}
for i, val in enumerate(values):
	# target minus a number is the other number
	if target - val in val_to_ind:
		print(i + 1, val_to_ind[target - val])
		sys.exit(0)
	val_to_ind[val] = i + 1


print("IMPOSSIBLE")

Solution 2 - Two Pointers

By keeping two pointers, one at each end of the list, we can greedily move the left and right pointers if the sum of the two elements are less than or greater than the target sum, finding the two indices in O(N)\mathcal{O}(N) time.

However, we do have to sort the values in order to use two pointers, bringing our total complexity to O(Nlog⁡N)\mathcal{O}(N \log N).

C++

#include <bits/stdc++.h>
using namespace std;


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


	vector<pair<int, int>> values;
	// append the element and its index
	for (int i = 0; i < n; i++) {

Java

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


public class TwoSum {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int target = io.nextInt();


		List<Pair> values = new ArrayList<>();

Python

n, target = list(map(int, input().split()))
nums = list(map(int, input().split()))
values = []


# append the element and its index
for i in range(n):
	values.append([nums[i], i + 1])


values.sort()

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