CSES Solutions – Sum of Three Values
You are given an array arr[] of N integers, and your task is to find three values (at distinct positions) whose sum is X.
Note: The indices can be printed in any order.
Examples:
Input: N = 4, X = 8, arr[] = {2, 7, 5, 1}
Output: 1 3 4
Explanation: The elements at position 1, 3 and 4 are: 2, 5 and 1 respectively. Sum of all these elements is 2 + 5 + 1 = 8.Input: N = 4, X = 7, arr[] = {1, 1, 1, 1}
Output: Impossible
Explanation: No three elements from arr[] can have total sum = 7.
Approach: To solve the problem, follow the below idea:
The problem can be solved using Sorting and Two Pointer approach. We can store pairs of values and index of arr[] in a 2D vector, say vec[][]. Sort vec in ascending order of the values. Iterate a loop, say ptr1 from 0 to N – 2, for the first value. We assume that vec[ptr1][0] is the first value and now we need to search for the second and third value. For the second and third value, we can use two pointers(ptr2 and ptr3) on the ends of the remaining subarray (ptr2 = ptr1 + 1, ptr3 = N – 1). Let’s say the sum of these three values is currentSum = vec[ptr1][0] + vec[ptr2][0] + vec[ptr3][0]. Now, we can have three cases:
- Case 1: currentSum = X, we got the answer so print vec[ptr1][1], vec[ptr2][1] and vec[ptr3][1].
- Case 2: currentSum < X, this means we want to increase the sum of three value. Since we have assumed that vec[ptr1][0] is the first value, we cannot change ptr1. So the only way to increase the sum is to move ptr2 forward, that is ptr2 = ptr2 + 1.
- Case 3:currentSum > X, this means we want to decrease the sum of three value. Since we have assumed that vec[ptr1][0] is the first value, we cannot change ptr1. So, the only way to decrease the sum is to move ptr3 backward, that is ptr3 = ptr3 – 1.
We keep on moving ptr2 and ptr3 closer till ptr2 < ptr3. If we didn’t get any valid triplet ptr1, ptr2 and ptr3 such that vec[ptr1][0] + vec[ptr2][0] + vec[ptr3][0] = X, it means that our assumption that vec[ptr1][0] is the first value is wrong, so we will shift ptr1 to ptr1 + 1 and assume that vec[ptr1][0] is the first value. Again, start finding a valid triplet with sum = X.
If after all the possible assumptions of the first value we do not get any answer, then it is impossible to have sum = X.
Step-by-step algorithm:
- Maintain a 2D vector, say vec[][] to store values along with their indices.
- Sort vec[][] in ascending order of the values.
- Iterate ptr1 from 0 to N – 2,
- Declare two pointers ptr2 = ptr1 + 1 and ptr3 = N – 1.
- Store the sum of vec[ptr1][0] + vec[ptr2][0] + vec[ptr3][0] as currentSum.
- If currentSum = X, then print the three indices as vec[ptr1][1], vec[ptr2][1] and vec[ptr3][1].
- Else if currentSum < X, move ptr2 to ptr2 + 1.
- Else if currentSum > X, move ptr3 to ptr3 – 1.
- After all the iterations, if no triplet is found whose sum = X, then print “IMPOSSIBLE”.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
// function to find a triplet whose sum = X
void solve(vector<ll>& arr, ll X, ll N)
{
// vector to store the values along with their indices
vector<vector<ll> > vec(N, vector<ll>(2));
for (int i = 0; i < N; i++) {
vec[i][0] = arr[i];
vec[i][1] = i + 1;
}
// Sort the vector in increasing order of the values
sort(vec.begin(), vec.end());
// Iterate for all possible values of first element
for (ll ptr1 = 0; ptr1 < N - 2; ptr1++) {
// Maintain two pointers for the second and third
// element
ll ptr2 = ptr1 + 1;
ll ptr3 = N - 1;
while (ptr2 < ptr3) {
ll currentSum = vec[ptr1][0] + vec[ptr2][0]
+ vec[ptr3][0];
// If current sum is equal to X, then we have
// found a triplet whose sum = X
if (currentSum == X) {
cout << vec[ptr1][1] << " " << vec[ptr2][1]
<< " " << vec[ptr3][1] << "\n";
return;
}
// Decrease the currentSum by moving ptr3 to
// ptr3 - 1
else if (currentSum > X) {
ptr3--;
}
// Increase the currentSum by moving ptr2 to
// ptr2 + 1
else if (currentSum < X) {
ptr2++;
}
}
}
// If no triplet has sum = X, print "IMPOSSIBLE"
cout << "IMPOSSIBLE";
}
int main()
{
// Sample Input
ll N = 4, X = 8;
vector<ll> arr = { 2, 7, 5, 1 };
solve(arr, X, N);
// your code goes here
return 0;
}
import java.util.Arrays;
public class Main {
public static void GFG(int[] arr, int X, int N) {
// Array to store the values along with their indices
int[][] vec = new int[N][2];
for (int i = 0; i < N; i++) {
vec[i][0] = arr[i];
vec[i][1] = i + 1;
}
// Sort the array in increasing order of values
Arrays.sort(vec, (a, b) -> a[0] - b[0]);
for (int ptr1 = 0; ptr1 < N - 2; ptr1++) {
// Maintain two pointers for the second and third element
int ptr2 = ptr1 + 1;
int ptr3 = N - 1;
while (ptr2 < ptr3) {
int currentSum = vec[ptr1][0] + vec[ptr2][0] + vec[ptr3][0];
// If current sum is equal to X
// then we have found a triplet whose sum = X
if (currentSum == X) {
System.out.println(vec[ptr1][1] + " " + vec[ptr2][1] + " " + vec[ptr3][1]);
return;
} else if (currentSum > X) {
ptr3--;
}
// Increase the currentSum by moving the ptr2 to ptr2 + 1
else if (currentSum < X) {
ptr2++;
}
}
}
System.out.println("IMPOSSIBLE");
}
public static void main(String[] args) {
int N = 4;
int X = 8;
int[] arr = {2, 7, 5, 1};
GFG(arr, X, N);
}
}
using System;
class Program
{
public static void Solve(int[] arr, int X, int N)
{
// Tuple array to store the values along with their 1-based indices
var vec = new (int Value, int Index)[N];
for (int i = 0; i < N; i++)
{
vec[i] = (arr[i], i + 1);
}
// Sort the tuple array in increasing order of the values
Array.Sort(vec, (a, b) => a.Value.CompareTo(b.Value));
// Iterate for all possible values of the first element
for (int ptr1 = 0; ptr1 < N - 2; ptr1++)
{
// Maintain two pointers for the second and third elements
int ptr2 = ptr1 + 1;
int ptr3 = N - 1;
while (ptr2 < ptr3)
{
int currentSum = vec[ptr1].Value + vec[ptr2].Value + vec[ptr3].Value;
// If current sum is equal to X, then we have found a triplet whose sum = X
if (currentSum == X)
{
Console.WriteLine($"{vec[ptr1].Index} {vec[ptr2].Index} {vec[ptr3].Index}");
return;
}
// Decrease the currentSum by moving ptr3 to the left
else if (currentSum > X)
{
ptr3 -= 1;
}
// Increase the currentSum by moving ptr2 to the right
else if (currentSum < X)
{
ptr2 += 1;
}
}
}
// If no triplet has sum = X, print "IMPOSSIBLE"
Console.WriteLine("IMPOSSIBLE");
}
static void Main(string[] args)
{
int N = 4;
int X = 8;
int[] arr = { 2, 7, 5, 1 };
Solve(arr, X, N);
}
}
function GFG(arr, X, N) {
// Array to store the values along with their indices
const vec = [];
for (let i = 0; i < N; i++) {
vec.push([arr[i], i + 1]);
}
// Sort the array in increasing order of values
vec.sort((a, b) => a[0] - b[0]);
for (let ptr1 = 0; ptr1 < N - 2; ptr1++) {
// Maintain two pointers for the second and third element
let ptr2 = ptr1 + 1;
let ptr3 = N - 1;
while (ptr2 < ptr3) {
const currentSum = vec[ptr1][0] + vec[ptr2][0] + vec[ptr3][0];
// If current sum is equal to X
// then we have found a triplet whose sum = X
if (currentSum === X) {
console.log(vec[ptr1][1], vec[ptr2][1], vec[ptr3][1]);
return;
}
else if (currentSum > X) {
ptr3--;
}
// Increase the currentSum by moving the ptr2 to ptr2 + 1
else if (currentSum < X) {
ptr2++;
}
}
}
console.log("IMPOSSIBLE");
}
// Main function
function main() {
const N = 4;
const X = 8;
const arr = [2, 7, 5, 1];
GFG(arr, X, N);
}
main();
# function to find a triplet whose sum = X
def solve(arr, X, N):
# list to store the values along with their indices
vec = [[arr[i], i + 1] for i in range(N)]
# Sort the list in increasing order of the values
vec.sort()
# Iterate for all possible values of first element
for ptr1 in range(N - 2):
# Maintain two pointers for the second and third element
ptr2 = ptr1 + 1
ptr3 = N - 1
while ptr2 < ptr3:
currentSum = vec[ptr1][0] + vec[ptr2][0] + vec[ptr3][0]
# If current sum is equal to X, then we have found a triplet whose sum = X
if currentSum == X:
print(vec[ptr1][1], vec[ptr2][1], vec[ptr3][1])
return
# Decrease the currentSum by moving ptr3 to ptr3 - 1
elif currentSum > X:
ptr3 -= 1
# Increase the currentSum by moving ptr2 to ptr2 + 1
elif currentSum < X:
ptr2 += 1
# If no triplet has sum = X, print "IMPOSSIBLE"
print("IMPOSSIBLE")
# Sample Input
N = 4
X = 8
arr = [2, 7, 5, 1]
solve(arr, X, N)
Output
4 1 3
Time Complexity: O(N * N), where N is the size of input array arr[].
Auxiliary Space: O(N)
Contact Us