DSA sheet / Sorting and searching
Sum of Two Values
Do these first: Apartments
The problem in brief
Given an array of n integers (n up to 200 000) and a target x, print the positions (1-indexed) of two different elements whose values sum to x. If no such pair exists print IMPOSSIBLE. Any valid pair is accepted.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1640.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Fix one element. What single value would its partner have to have? Now the question becomes a lookup.
-
Which structures give a fast “does this value exist, and where?” lookup? Think hashing, and think sorting plus binary search.
-
Alternatively sort the values (remembering original positions) and walk one pointer from each end. When the sum is too small, which pointer should move?
-
Remember you need the original positions, not the sorted ones, and the two positions must differ.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
The naive O(n^2) approach tries every pair. The improvement comes from reframing: for each a[i], the only acceptable partner is x - a[i], and “find a specific value” is a lookup problem. A hash map makes it expected O(1) per element; a sorted array makes it O(log n).
The two-pointer variant is even neater once the array is sorted. If the smallest plus the largest is too small, the smallest can never help (every other partner is even smaller), so drop it; if too large, drop the largest. Each step discards an element, so the sweep is linear. Because sorting scrambles positions, sort pairs of (value, original index) or sort indices by value.
The habit: whenever you are asked for a pair with a sum/difference condition, think “fix one, look up the other” or “sort and squeeze from both ends”.
Intuition
Line the numbers up small to large and put a finger on each end. If the two fingers add to less than the target you need bigger numbers, so move the left finger right; if they add to more, move the right finger left. They meet if no pair exists.
Approach
- Build a list of indices 0..n-1 sorted by value.
- Set l = 0, r = n - 1. While l < r: let s = a[idx[l]] + a[idx[r]]. If s == x, print idx[l] + 1 and idx[r] + 1 and stop. If s < x, l += 1; otherwise r -= 1.
- If the loop ends without a match, print IMPOSSIBLE.
Pitfalls: the sum of two values can reach 2 * 10^9 (over a 32-bit int), so add as 64-bit; the two positions must differ (guaranteed here by l < r even when two values are equal); output positions are 1-based.
Complexity
O(n log n) for the sort and O(n) for the sweep; O(n) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long x;
cin >> n >> x;
vector<pair<long long, int>> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i].first;
a[i].second = i + 1;
}
sort(a.begin(), a.end());
int l = 0, r = n - 1;
while (l < r) {
long long s = a[l].first + a[r].first;
if (s == x) {
cout << a[l].second << " " << a[r].second << "\n";
return 0;
}
if (s < x) l++;
else r--;
}
cout << "IMPOSSIBLE\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
idx = sorted(range(n), key=a.__getitem__)
l, r = 0, n - 1
while l < r:
s = a[idx[l]] + a[idx[r]]
if s == x:
print(idx[l] + 1, idx[r] + 1)
return
if s < x:
l += 1
else:
r -= 1
print("IMPOSSIBLE")
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
st.nextToken();
long x = (long) st.nval;
long[] key = new long[n]; // value in the high bits, original index in the low 18: sorts by value
for (int i = 0; i < n; i++) {
st.nextToken();
key[i] = ((long) st.nval << 18) | i;
}
Arrays.sort(key);
long mask = (1L << 18) - 1;
int l = 0, r = n - 1;
while (l < r) {
long s = (key[l] >> 18) + (key[r] >> 18);
if (s == x) {
System.out.println(((key[l] & mask) + 1) + " " + ((key[r] & mask) + 1));
return;
}
if (s < x) l++;
else r--;
}
System.out.println("IMPOSSIBLE");
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const x = data[1];
// value * 2^18 + index: exact in a double (10^9 * 262144 is about 2.6e14) and sorts by value.
const SHIFT = 262144;
const key = new Float64Array(n);
for (let i = 0; i < n; i++) key[i] = data[2 + i] * SHIFT + i;
key.sort();
let l = 0;
let r = n - 1;
let answer = 'IMPOSSIBLE';
while (l < r) {
const vl = Math.floor(key[l] / SHIFT);
const vr = Math.floor(key[r] / SHIFT);
const s = vl + vr;
if (s === x) {
answer = `${(key[l] % SHIFT) + 1} ${(key[r] % SHIFT) + 1}`;
break;
}
if (s < x) l++;
else r--;
}
console.log(answer);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).