CSES - Sum of Two Values

Authors: Michael Cao, DRGSH, Benjamin Qi

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

Main Idea

Let's start by iterating over the first value in time. Given one value, , the other value must be unless (in which case cannot be a valid first value).

So the question reduces to, given some value , does some other value 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 , 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 you only consider values with index .

C++

1#include <bits/stdc++.h>
2using namespace std;
3using ll = long long;
4using vi = vector<int>;
5#define pb push_back
6#define rsz resize
7#define all(x) begin(x), end(x)
8#define sz(x) (int)(x).size()
9using pi = pair<int,int>;
10#define f first

Python

1import sys
2

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

6val_to_ind = {}
7for i,val in enumerate(a):
8    if x-val in val_to_ind: 
9        # equivalent to val_to_ind.__contains__(x-val)
10        print(i+1,val_to_ind[x-val])

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

Give Us Feedback on CSES - Sum of Two Values!