CSES Solutions - Sum of Two values

You are given an array arr[] of N integers, and your task is to find two different indices whose sum is X.

Examples:

Input: N = 4, X = 8, arr[] = {2, 7, 5, 1}
Output: 2 4
Explanation: The sum of arr[2] and arr[4] (1-based indexing) is 7 + 1 = 8

Input: N = 5, X = 6, arr[] = {1, 2, 3, 4, 5}
Output: 1 5
Explanation: The sum of arr[1] and arr[5] (1-based indexing) is 1 + 5 = 6

Approach: To solve the problem, follow the below idea:

The problem can be solved using a map to store the element as the key and its index as the value. For every arr[i], check if there is any element already present in the map having value = X - arr[i]. If yes, then print the index of (X - arr[i]) along with the current index else insert the value and index to the map.

Step-by-step algorithm:

• Maintain a map, say m1 to store the element as the key and its index as the value.
• Maintain a flag = true, to check that we have not encountered any pair of elements whose sum = X.
• Now iterate of the array arr[] and for each arr[i] check if (X - arr[i]) is present in the map or not and set flag = true.
• If (X - arr[i]) is present in the map, then print the current index i and m1[X - arr[i]].
• Also insert the current element arr[i] into the map with index i as the value.
• After traversing through all the elements, if flag is true then print "IMPOSSIBLE".

Below is the implementation of the algorithm:

#include <bits/stdc++.h> #define ll long long using namespace std; void solve(ll* arr, ll N, ll X) {  map<ll, ll> m1;  bool flag = true;  for (int i = 0; i < N; i++) {  if (flag) {  if (m1.find(X - arr[i]) != m1.end()) {  cout << (*(m1.find(X - arr[i]))).second  << " " << i + 1;  flag = false;  }  m1.insert({ arr[i], i + 1 });  }  }  if (flag)  cout << "IMPOSSIBLE"; } int main() {  ll N = 4, X = 8;  ll arr[] = { 2, 7, 5, 1 };  solve(arr, N, X); } 

import java.util.HashMap; import java.util.Map; public class Main {  static void solve(long[] arr, long N, long X) {  Map<Long, Long> m1 = new HashMap<>();  boolean flag = true;  for (int i = 0; i < N; i++) {  if (flag) {  if (m1.containsKey(X - arr[i])) {  System.out.println(m1.get(X - arr[i]) + " " + (i + 1));  flag = false;  }  m1.put(arr[i], (long) (i + 1));  }  }  if (flag)  System.out.println("IMPOSSIBLE");  }  public static void main(String[] args) {  long N = 4, X = 8;  long[] arr = {2, 7, 5, 1};  solve(arr, N, X);  } } // This code is contributed by shivamgupta310570 

def solve(arr, N, X): # Create an empty dictionary to store the index of elements # as keys and their corresponding positions as values m1 = {} # Initialize a flag to track if a pair is found flag = True # Iterate through the array for i in range(N): # Check if the flag is still True if flag: # If the complement of the current element (X - arr[i]) # exists in the dictionary, it means a pair is found if X - arr[i] in m1: # Print the indices of the pair print(m1[X - arr[i]] + 1, i + 1) # Set the flag to False to indicate that a pair is found flag = False # Store the current element and its index in the dictionary m1[arr[i]] = i # If no pair is found, print "IMPOSSIBLE" if flag: print("IMPOSSIBLE") # Driver code N = 4 X = 8 arr = [2, 7, 5, 1] solve(arr, N, X) 

using System; using System.Collections.Generic; public class GFG {  public static void FindPair(int[] arr, int N, int X)  {  // Create a dictionary to store the index of the elements  Dictionary<int, int> map = new Dictionary<int, int>();  bool flag = true;  // Iterate through the array  for (int i = 0; i < N; i++)  {  // If flag is true  if (flag)  {  int complement = X - arr[i];  if (map.ContainsKey(complement))  {  Console.WriteLine(map[complement] + " " + (i + 1));  flag = false;  }  map[arr[i]] = i + 1;  }  }  // If no pair is found, print "IMPOSSIBLE"  if (flag)  {  Console.WriteLine("IMPOSSIBLE");  }  }  public static void Main(string[] args)  {  // Sample Input  int N = 4;  int X = 8;  int[] arr = { 2, 7, 5, 1 };  FindPair(arr, N, X);  } } 

function GFG(arr, N, X) {  // Create a map to store the index of the elements  const map = new Map();  let flag = true;  // The Iterate through the array  for (let i = 0; i < N; i++) {  // If flag is true  if (flag) {  if (map.has(X - arr[i])) {  console.log(map.get(X - arr[i]) + " " + (i + 1));  flag = false;  }  map.set(arr[i], i + 1);  }  }  // If no pair is found  // print "IMPOSSIBLE"  if (flag) {  console.log("IMPOSSIBLE");  } } // The Sample Input const N = 4; const X = 8; const arr = [2, 7, 5, 1]; GFG(arr, N, X); 

2 4

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

Approach2 (Two Pointer Approach)

Before applying the two-pointer approach, sort the array. Initialize two pointers, typically named 'left' and 'right'. 'left' points to the beginning (index 0) of the sorted array, and 'right' points to the end (index n-1) of the array, where 'n' is the length of the array. Iterate through the array using these two pointers. The iteration continues as long as 'left' pointer is less than 'right' pointer. This ensures that every pair of elements is considered exactly once. At each iteration, the sum of elements pointed to by 'left' and 'right' pointers is calculated. Now compare, If the sum equals the target value , then the pair of indices corresponding to 'left' and 'right' pointers is a valid solution, return it. If the sum is less than target value, it means that the current sum is small, increase left pointer. If the sum is greater than target value, decrease pointer. This process continues left pointer crosses right pointer.

Step by Step implementation of above approach

• Sort the array first.
• Start with two pointers left and right , left = 0 , right = array.size() - 1.
• Calculate arr[left] + arr[right]
• If the sum is equal to the target sum, return the indices left and right.
• If the sum is less than the target sum, increase left.
• If the sum is greater than the target sum, decrease right.

Example : To demonstrate Sum of Two Values using two pointer approach

#include <iostream> #include <vector> using namespace std; pair<int, int> findTwoSum(const vector<int>& arr, int target) {  int left = 0;  int right = arr.size() - 1;  while (left < right) {  int sum = arr[left] + arr[right];  if (sum == target) {  return {left, right};  } else if (sum < target) {  left++;  } else {  right--;  }  }  // If no pair found  return {-1, -1}; } int main() {  vector<int> arr = {1, 2, 3, 4, 5, 6, 7};  int target = 9;  pair<int, int> indices = findTwoSum(arr, target);  if (indices.first != -1 && indices.second != -1) {  cout << "Indices of the two numbers are : " << indices.first << " and " << indices.second << endl;  } else {  cout << "No pair found." << endl;  }  return 0; } 

import java.util.Arrays; public class Main {  public static int[] findTwoSum(int[] arr, int target) {  int left = 0;  int right = arr.length - 1;  while (left < right) {  int sum = arr[left] + arr[right];  if (sum == target) {  return new int[]{left, right};  } else if (sum < target) {  left++;  } else {  right--;  }  }  // If no pair found  return new int[]{-1, -1};  }  public static void main(String[] args) {  int[] arr = {1, 2, 3, 4, 5, 6, 7};  int target = 9;  int[] indices = findTwoSum(arr, target);  if (indices[0] != -1 && indices[1] != -1) {  System.out.println("Indices of the two numbers are: " + indices[0] + " and " + indices[1]);  } else {  System.out.println("No pair found.");  }  } } 

def find_two_sum(arr, target): left = 0 right = len(arr) - 1 # Iterate until left pointer is less than right pointer while left < right: # Calculate sum of elements at left and right pointers _sum = arr[left] + arr[right] # If sum equals target, return indices if _sum == target: return (left, right) # If sum is less than target, move left pointer to right elif _sum < target: left += 1 # If sum is greater than target, move right pointer to left else: right -= 1 # If no pair found return (-1, -1) # Main function def main(): arr = [1, 2, 3, 4, 5, 6, 7] target = 9 # Find indices of the two numbers whose sum is equal to target indices = find_two_sum(arr, target) # Check if pair found if indices[0] != -1 and indices[1] != -1: print("Indices of the two numbers are:", indices[0], "and", indices[1]) else: print("No pair found.") # Execute main function if __name__ == "__main__": main() 

function findTwoSum(arr, target) {  let left = 0;  let right = arr.length - 1;  while (left < right) {  let sum = arr[left] + arr[right];  if (sum === target) {  return [left, right];  } else if (sum < target) {  left++;  } else {  right--;  }  }  // If no pair found  return [-1, -1]; } let arr = [1, 2, 3, 4, 5, 6, 7]; let target = 9; let indices = findTwoSum(arr, target); if (indices[0] !== -1 && indices[1] !== -1) {  console.log("Indices of the two numbers are: " + indices[0] + " and " + indices[1]); } else {  console.log("No pair found."); } // This code is contributed by Ayush Mishra 

Indices of the two numbers are : 1 and 6 

Time Complexity: O(n)

Space Complexity: O(1)