Two-Sum Problem Efficient Solution O(n2)

using namespace std;
 
// Function to find and print pair
bool chkPair(int A[], int size, int x)
{
    for (int i = 0; i < (size - 1); i++) {
        for (int j = (i + 1); j < size; j++) {
            if (A[i] + A[j] == x) {
                return 1;
            }
        }
    }
 
    return 0;
}
 
// Driver code
int main()
{
    int A[] = { 0, -1, 2, -3, 1 };
    int x = -2;
    int size = sizeof(A) / sizeof(A[0]);
 
    if (chkPair(A, size, x)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << x << endl;
    }
 
    return 0;
}

/*
 * This C program tells if there exists a pair in array
 * whose sum results in x.
 */
 
#include 
 
// Function to find and print pair
int chkPair(int A[], int size, int x)
{
    for (int i = 0; i < (size - 1); i++) {
        for (int j = (i + 1); j < size; j++) {
            if (A[i] + A[j] == x) {
                return 1;
            }
        }
    }
 
    return 0;
}
 
int main(void)
{
    int A[] = { 0, -1, 2, -3, 1 };
    int x = -2;
    int size = sizeof(A) / sizeof(A[0]);
 
    if (chkPair(A, size, x)) {
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
 
    return 0;
}

// Java program to check if there exists a pair
// in array whose sum results in x.
import java.io.*;
class TwoSum{

	// Function to find and print pair
	static boolean chkPair(int A[], int size, int x)
	{
		for (int i = 0; i < (size - 1); i++) {
			for (int j = (i + 1); j < size; j++) {
				if (A[i] + A[j] == x) {
					return true;
				}
			}
		}

		return false;
	}

	public static void main(String[] args)
	{

		int A[] = { 0, -1, 2, -3, 1 };
		int x = -2;
		int size = A.length;

		if (chkPair(A, size, x)) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}
	}
}

# This python program tells if there exists a pair in array whose sum results in x.

# Function to find and print pair


def chkPair(A, size, x):
	for i in range(0, size - 1):
		for j in range(i + 1, size):
			if (A[i] + A[j] == x):
				return 1
	return 0


if __name__ == "__main__":
	A = [0, -1, 2, -3, 1]
	x = -2
	size = len(A)

	if (chkPair(A, size, x)):
		print("Yes")

	else:
		print("No")

// C# program to check if there exists a pair
// in array whose sum results in x.
using System;
class TwoSum{

	// Function to find and print pair
	static bool chkPair(int[] A, int size, int x)
	{
		for (int i = 0; i < (size - 1); i++) {
			for (int j = (i + 1); j < size; j++) {
				if (A[i] + A[j] == x) {
					return true;
				}
			}
		}

		return false;
	}

	public static void Main()
	{
		int[] A = { 0, -1, 2, -3, 1 };
		int x = -2;
		int size = A.Length;

		if (chkPair(A, size, x)) {
			Console.WriteLine("Yes");
		}
		else {
			Console.WriteLine("No");
		}
	}
}

	function chkPair(A , size , x) {
	
		for (i = 0; i < (size - 1); i++) {
			for (j = (i + 1); j < size; j++) {
	
				if (A[i] + A[j] == x) {
					document.write("Pair with a given sum " + x + " is (" + A[i] + ", " + A[j] + ")");

					return true;
				}
			}
		}

		return false;
	}

		let A = [ 0, -1, 2, -3, 1 ];
		let x = -2;
		let size = A.length;

		if (chkPair(A, size, x)) {
			document.write("<br/>Valid pair exists");
		}
		else {
			document.write("<br/>No valid pair exists for " + x);
		}

package main
import ("fmt")


func twoSum(nums [5]int, target int) {
	var flag bool = false
	result:=make([]int,2)
	for i:=0;i<len(nums)-1;i++{
		for j:=i+1;j<len(nums);j++{
			if nums[i]+nums[j]==target{
				result[0]=nums[i]
				result[1]=nums[j]
				flag = true;
			}
		}
	}
	
	if(flag == false){
		fmt.Println("No")
	}else {
	fmt.Printf( "Yes")
}
	
}

func main() {

arr2 := [5]int{0, -1, 2, -3, 1}
var x int = -2

twoSum(arr2, x)
}

package org.redquark.tutorials.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TwoSum {

    public int[] twoSum(int[] nums, int target) {
        // Array to store result
        int[] result = new int[2];
        // This map will store the difference and the corresponding index
        Map<Integer, Integer> map = new HashMap<>();
        // Loop through the entire array
        for (int i = 0; i < nums.length; i++) {
            // If we have seen the current element before
            // It means we have already encountered the other number of the pair
            if (map.containsKey(nums[i])) {
                // Index of the current element
                result[0] = i;
                // Index of the other element of the pair
                result[1] = map.get(nums[i]);
            }
            // If we have not seen the current before
            // It means we have not yet encountered any number of the pair
            else {
                // Save the difference of the target and the current element
                // with the index of the current element
                map.put(target - nums[i], i);
            }
        }
        return result;
    }
}

from typing import List


def twoSum(nums: List[int], target: int) -> List[int]:
    # List to store results
    result = []
    # Dictionary to store the difference and its index
    index_map = {}
    # Loop for each element
    for i, n in enumerate(nums):
        # Difference which needs to be checked
        difference = target - n
        if difference in index_map:
            result.append(i)
            result.append(index_map[difference])
            break
        else:
            index_map[n] = i
    return result

var twoSum = function (nums, target) {
    // Array to store the result
    result = [];
    // Map to store the difference and its index
    index_map = new Map();
    // Loop for each element in the array
    for (let i = 0; i < nums.length; i++) {
        let difference = target - nums[i];
        if (index_map.has(difference)) {
            result[0] = i;
            result[1] = index_map.get(difference);
            break;
        } else {
            index_map.set(nums[i], i);
        }
    }
    return result;
};

package org.redquark.tutorials.leetcode

fun twoSum(nums: IntArray, target: Int): IntArray {
    // Array to store result
    val result = IntArray(2)
    // This map will store the difference and the corresponding index
    val map: MutableMap<Int, Int> = HashMap()
    // Loop through the entire array
    for (i in nums.indices) {
        // If we have seen the current element before
        // It means we have already encountered the other number of the pair
        if (map.containsKey(nums[i])) {
            // Index of the current element
            result[0] = i
            // Index of the other element of the pair
            result[1] = map[nums[i]]!!
            break
        } else {
            // Save the difference of the target and the current element
            // with the index of the current element
            map[target - nums[i]] = i
        }
    }
    return result
}