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) 

4 1 3

Time Complexity: O(N * N), where N is the size of input array arr[].
Auxiliary Space: O(N)