CSES - Sum of Three Values

Authors: Andrew Wang, Brad Ma, Paul Chen

Appears In

Silver - Two Pointers

Explanation

This problem is an extension of the two sum problem except now with three values. We can set the third pointer to a certain value in the array and then the problem becomes the two sum problem discussed earlier in this module.

First we'll sort the array. Then we'll loop through all possible values for the third pointer and check if all three pointers add up to the target amount, $x$ , while having distinct positions. We can maintain the original positions of all values by storing the pairs {a[i],i}.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

C++

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, x;
	cin >> n >> x;
	vector<pair<int, int>> arr;
	for (int i = 1; i <= n; i++) {

Java

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

public class SumOfThreeValues {
	static class Group implements Comparable<Group> {
		int value, index;

		Group(int value, int index) {
			this.value = value;
			this.index = index;

Python

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

p = [(a[i], i + 1) for i in range(n)]

p.sort()

for i in range(n):
	left = 0
	right = n - 1

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!