Given a list of numbers and a number k, return whether any two numbers from the list add up to k

Question

This question was asked in the Google programming interview. I thought of two approaches for the same:

1. Find all the subsequences of length. While doing so compute the sum and of the two elements and check if it is equal to k. If ye, print Yes, else keep searching. This is a brute Force approach.

2. Sort the array in non-decreasing order. Then start traversing the array from its right end. Say we have the sorted array, {3,5,7,10} and we want the sum to be 17. We will start from element 10, index=3, let's denote the index with 'j'. Then include the current element and compute required_sum= sum - current_element. After that, we can perform a binary or ternary search in array[0- (j-1)] to find if there is an element whose value is equal to the required_sum. If we find such an element, we can break as we have found a subsequence of length 2 whose sum is the given sum. If we don't find any such element, then decrease the index of j and repeat the above-mentioned steps for resulting subarray of length= length-1 i.e. by excluding the element at index 3 in this case.

Here we have considered that array could have negative as well as positive integers.

Can you suggest a better solution than this? A DP solution maybe? A solution that can further reduce it's time complexity.

Naturalism

There is an O(n) time and space algorithm for this. For each element check if it exists in the hashmap. If not,' store k - arr[i] and move on to the next element. – Isogamete

dictionary and meaning of sum make trick of this question. – Whereas

Can numbers in the array duplicate? – Lobito

The version of the question that I have seen also includes the requirement that it must be done in 1 pass. – Subgenus

Answer 1

This question can be easily solved with the help of set in O(N) time and space complexity.First add all the elements of array into set and then traverse each element of array and check whether K-ar[i] is present in set or not.

Here is the code in java with O(N) complexity :

boolean flag=false;
HashSet<Long> hashSet = new HashSet<>();
for(int i=0;i<n;i++){
    if(hashSet.contains(k-ar[i]))flag=true;
    hashSet.add(ar[i]);
}
if(flag)out.println("YES PRESENT");
else out.println("NOT PRESENT");

Cheddite

@GiorgosLamprakis this solution works perfectly with it. The solution will return false on the case you gave since we want to select two elements with different indexes. If it could have been same, only the order of adding it to set will change before comparison. – Cheddite

Not working: if you look for sum 20 and the set contains 10 once it will return true. It would work if you build the set on the go, but not with a pre built set. – Buckshot

I mean the code works, but the description in english does not. The Java code doesn't match the description. Elements are added after checking if a previous item made a pair. – Buckshot

Answer 2

Here is a Java implementation with the same time complexity as the algorithm used to sort the array. Note that this is faster than your second idea because we do not need to search the entire array for a matching partner each time we examine a number.

public static boolean containsPairWithSum(int[] a, int x) {
    Arrays.sort(a);
    for (int i = 0, j = a.length - 1; i < j;) {
        int sum = a[i] + a[j];
        if (sum < x)
            i++;
        else if (sum > x)
            j--;
        else
            return true;
    }
    return false;
}

Proof by induction: Let a[0,n] be an array of length n+1 and p = (p1, p2) where p1, p2 are integers and p1 <= p2 (w.l.o.g.). Assume a[0,n] contains p1 and p2. In the case that it does not, the algorithm is obviously correct.

Base case (i = 0, j = n): a[0,-1] does not contain p1 and a[n,n+1] does not contain p2.

Hypothesis: a[0,i-1] does not contain a[i] and a[j+1,n] does not contain p2.

Step case (i to i + 1 or j to j - 1):

1. Assume p1 = a[i]. Then, since p1 + a[j] < p1 + p2, index j must be increased. But from the hypothesis we know that a[j+1,n-1] does not contain p2. Contradiction. It follows that p1 != a[i].
2. j to j - 1 analogously.

Because each iteration, a[0,i-1] and a[j+1,n], does not contain p1, and p2, a[i,j] does contain p1 and p2. Eventually, a[i] = p1 and a[j] = p2 and the algorithm returns true.

Bowman

Simple solution. Your response is much appreciated. Thank you. :) – Naturalism

Can you suggest a way through which I can go about if the question has asked n element sub-sequence that adds up to sum k? – Naturalism

@Jhanak Didwania But your question doesn't mention subsequences, only two numbers. – Wedurn

@Wedurn if the question was not limited upto two numbers, then what should be the approach? – Naturalism

Subset sum problem. It is completely different question. – Wedurn

@Wedurn It will be extension to subset sum problem with the constraint on the total number of elements of the subset as well. – Naturalism

Didn't execute, but I dont think this would work for the case [1,5,2,3,10,6] where x = 15. elements [1] and [4] arent compared – Meletius

@sheldonj22 I added a correctness proof. Also, here you can see that your example works correctly: onlinegdb.com/HJITFPuT4 – Bowman

yup, didn't see the sort at the top – Meletius

Answer 3

This is java implementation with O(n) Time complexity and O(n) space. The idea is have a HashMap which will contain complements of every array element w.r.t target. If the complement is found, we have 2 array elements which sum to the target.

 public boolean twoSum(int[] nums, int target) {
    if(nums.length == 0 || nums == null) return false;

    Map<Integer, Integer> complementMap = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
         int curr = nums[i];
         if(complementMap.containsKey(target - curr)){
           return true;
         }
    complementMap.put(curr, i);
    }
  return false;
}

Implode

Very elegant solution but what do you mean by complement? – Voyage

Answer 4

if you want to find pair count,

pairs = [3,5,7,10]
k = 17
counter = 0

for i in pairs:
    if k - i in pairs:
        counter += 1

print(counter//2)

Aegisthus

You could improve this logic by using a list comprehension: def pair_count(_list, k): return sum([k - j in _list for i in _list]) // 2, which works since True == 1, and sum() counts how many elements in the generator are true. Obviously, this flows back into the original question - replace the return statement with return any(k - j in _list for i in _list), which may actually be a lot more efficient, since any returns True on the first occurrence of True, meaning that you wouldn't necessarily have to go through every element of list_ in some cases. – Lynnelle

Answer 5

Here is python's implementation

arr=[3,5,7,10]
k=17
flag=False
hashset = set()
for i in range(0,len(arr)):
    if k-arr[i] in hashset:
      flag=True
    hashset.add(arr[i])
print( flag )

Bleachers

This, much like many answers here will not account for k/2 == i, resulting in false-positives. – Deyoung

question is to find if 2 numbers in array sums up to a number or not and what you are saying is for finding count of pairs – Bleachers

@Bleachers the problem in your approach is if k=20, then your program will print true because 20-10 is again 10 which is present in the array, but your program will printout True even though there's only one 10 present in the array, which is a false positive case. – Contend

Ya have added set to fix this issue – Bleachers

Answer 6

Python Solution:

def FindPairs(arr, k):
    for i in range(0, len(arr)):
        if k - arr[i] in arr:
            return True
    return False        
A = [1, 4, 45, 6, 10, 8]
n = 100
print(FindPairs(A, n))

Or

def findpair(list1, k):
    for i in range(0, len(list1)):
        for j in range(0, len(list1)):
            if k == list1[i] + list1[j]:
                return True    
    return False       
nums = [10, 5, 6, 7, 3]
k = 100
print(findpair(nums, k))

Contumelious

there's a chance of false-postive, refer @saurabh's answer comment section. – Contend

The solutions dont look correct as it will sum the number to itself also and return true.. – Plenish

Answer 7

Javascript solution:

function hasSumK(arr, k) {
    hashMap = {};
    for (let value of arr) {
        if (hashMap[value]) { return true;} else { hashMap[k - value] = true };
    }
    return false;
}

Unwieldy

Answer 8

Using Scala, in a single pass with O(n) time and space complexity.

import collection.mutable.HashMap

def addUpToK(arr: Array[Int], k: Int): Option[Int] = {

val arrayHelper = new HashMap[Int,Int]()

def addUpToKHelper( i: Int): Option[Int] = {
  if(i < arr.length){
    if(arrayHelper contains k-arr(i) ){
      Some(arr(i))
    }else{
      arrayHelper += (arr(i) -> (k-arr(i)) )
      addUpToKHelper( i+1)
    }

  }else{
   None
  }
}
addUpToKHelper(0)
}

addUpToK(Array(10, 15, 3, 7), 17)

Veterinarian

This is not O(n). Scanning the arrayHelper contains will do a pass over the values. Worst case this also is O(n^2). – Philipp

Answer 9

The solution can be found out in just one pass of the array. Initialise a hash Set and start iterating the array. If the current element in the array is found in the set then return true, else add the complement of this element (x - arr[i]) to the set. If the iteration of array ended without returning it means that there is no such pair whose sum is equal to x so return false.

  public boolean containsPairWithSum(int[] a, int x) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i< a.length; i++) {
        if(set.contains(a[i])) 
            return true;
        set.add(x - a[i]);
    }
    return false;
 }

Padget

Answer 10

C++ solution:

int main(){

    int n;
    cin>>n;
    int arr[n];
    for(int i = 0; i < n; i++)
    {
        cin>>arr[i];
    }
    int k;
    cin>>k;
    int t = false;
    for(int i = 0; i < n-1; i++)
    {
        int s = k-arr[i];
        for(int j = i+1; j < n; j++)
        {
            if(s==arr[j])
            t=true;
        }

    }       
    if (t){
        cout<<"Thank you C++, very cool";
    }
    else{
        cout<<"Damn it!";
    }
        return 0;
}

Lordship

Answer 11

Python code:

L = list(map(int,input("Enter List: ").split()))
k = int(input("Enter value: "))

for i in L:
    if (k - i) in L:
        print("True",k-i,i)

Waikiki

Answer 12

Here is Swift solution:

func checkTwoSum(array: [Int], k: Int) -> Bool {
    var foundPair = false
    for n in array {
        if array.contains(k - n) {
            foundPair = true
            break
        } else {
            foundPair = false
        }
    }

    return foundPair
}

Coulee

Answer 13

def sum_total(list, total):

    dict = {}

    for i in lista:
        if (total - i) in dict:
            return True
        else:
            dict[i] = i

    return False

Plenish

Answer 14

Here is a C implementation
For Sorting O(n²) time and space complexity.
For Solving Problem We use single pass with O(n) time and space complexity via Recursion.
/* Given a list of numbers and a number k , return weather any two numbers from the list add up to k. For example, given [10,15,3,7] and k of 17 , return 10 + 7 is 17 Bonus: Can You Do in one pass ? */

#include<stdio.h>
int rec(int i , int j ,int k , int n,int array[])
{
  int sum;
  for( i = 0 ; i<j ;)
  {
      sum = array[i] + array[j];
      if( sum > k)
      {
        j--;
      }else if( sum < k)
      {
        i++;
      }else if( sum == k )
      {
        printf("Value equal to sum of array[%d]  = %d and array[%d] = %d",i,array[i],j,array[j]);
        return 1;//True
      }
  }
  return 0;//False
  }
int main()
  {
  int n ;
  printf("Enter The Value of Number of Arrays = ");
  scanf("%d",&n);
  int array[n],i,j,k,x;
  printf("Enter the Number Which you Want to search in addition of Two Number = ");
  scanf("%d",&x);
  printf("Enter The Value of Array \n");
  for( i = 0 ; i <=n-1;i++)
  {
    printf("Array[%d] = ",i);
    scanf("%d",&array[i]);
  }
  //Sorting of Array
  for( i = 0 ; i <=n-1;i++)
  {
     for( j = 0 ; j <=n-i-1;j++)
     {
     if( array[j]>array[j+1])
     {
       //swapping of two using bitwise operator
       array[j] = array[j]^array[j+1];
       array[j+1] = array[j]^array[j+1];
       array[j] = array[j]^array[j+1];
    }
    }
  }
  k = x ;
  j = n-1;
  rec(i,j,k,n,array);
  return 0 ;
}

OUTPUT

Enter The Value of Number of Arrays = 4
Enter the Number Which you Want to search in addition of Two Number = 17
Enter The Value of Array
Array[0] = 10
Array[1] = 15
Array[2] = 3
Array[3] = 7
Value equal to sum of array[1]  = 7 and array[2] = 10
Process returned 0 (0x0)   execution time : 54.206 s
Press any key to continue.

Mollusc

Answer 15

Here's Python. O(n). Need to remove the current element whilst looping because the list might not have duplicate numbers.

def if_sum_is_k(list, k):
i = 0
list_temp = list.copy()
match = False
for e in list:
    list_temp.pop(i)
    if k - e in list_temp:
        match = True
    i += 1
    list_temp = list.copy()
return match

Belaud

Answer 16

I came up with two solutions in C++. One was a naive brute force type which was in O(n^2) time.

int main() {
int N,K;
vector<int> list;
cin >> N >> K;
clock_t tStart = clock();   
for(int i = 0;i<N;i++) {
    list.push_back(i+1);
}

for(int i = 0;i<N;i++) {
    for(int j = 0;j<N;j++) {
        if(list[i] + list[j] == K) {
            cout << list[i] << " " << list[j] << endl;
            cout << "YES" << endl;
            printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
            return 0;
        }
    }
}
cout << "NO" << endl;

printf("Time taken: %f\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

return 0;}

This solution as you could imagine will take a large amount of time on higher values of input.

My second solution I was able to implement in O(N) time. Using an unordered_set, much like the above solution.

#include <iostream>
#include <unordered_set>
#include <time.h>

using namespace std;

int main() {
    int N,K;
    int trig = 0;
    int a,b;
    time_t tStart = clock();
    unordered_set<int> u;
    cin >> N >> K;
    for(int i =  1;i<=N;i++) {
        if(u.find(abs(K - i)) != u.end()) {
            trig = 1;
            a = i;
            b = abs(K - i);
        }
        u.insert(i);
    }
    trig ? cout << "YES" : cout << "NO";
    cout << endl;
    cout << a << " " << b << endl;
    printf("Time taken %fs\n",(double) (clock() - tStart)/CLOCKS_PER_SEC);
    return 0;
}

Calamint

Quick Edit, For this to work with negative numbers in the second example, you just need to remove the abs function. – Calamint

Answer 17

Python Implementation: The code would execute in O(n) complexity with the use of dictionary. We would be storing the (desired_output - current_input) as the key in the dictionary. And then we would check if the number exists in the dictionary or not. Search in a dictionary has an average complexity as O(1).

def PairToSumK(numList,requiredSum):
    dictionary={}
    for num in numList:
        if requiredSum-num not in dictionary:
            dictionary[requiredSum-num]=0
        if num in dictionary:
            print(num,requiredSum-num)
            return True
    return False

arr=[10, 5, 3, 7, 3]
print(PairToSumK(arr,6))

Inexecution

This doesn't account for the case of the sum being twice a number in the list. ie: PairToSumK([1,2],2) should be False but it's True. – Paroicous

Answer 18

Javascript

const findPair = (array, k) => {
  array.sort((a, b) => a - b);
  let left = 0;
  let right = array.length - 1;

  while (left < right) {
    const sum = array[left] + array[right];
    if (sum === k) {
      return true;
    } else if (sum < k) {
      left += 1;
    } else {
      right -= 1;
    }
  }

  return false;
}

Redeeming

Thanks for this solution. Looks great! – Rogozen

Answer 19

Using HashSet in java we can do it in one go or with time complexity of O(n)

import java.util.Arrays;
import java.util.HashSet;

public class One {
    public static void main(String[] args) {
        sumPairsInOne(10, new Integer[]{8, 4, 3, 7});
    }


    public static void sumPairsInOne(int sum, Integer[] nums) {
        HashSet<Integer> set = new HashSet<Integer>(Arrays.asList(nums));

        //adding values to a hash set
        for (Integer num : nums) {
            if (set.contains(sum - num)) {
                System.out.print("Found sum pair => ");
                System.out.println(num + " + " + (sum - num) + " = " + sum);
                return;
            }
        }

        System.out.println("No matching pairs");


    }
}

Schoolman

Please refer to that set.contains internally has O(1) so problem complexity must by O(n) – Dorset

Answer 20

Python

def add(num, k):
for i in range(len(num)):
    for j in range(len(num)):
        if num[i] + num[j] == k:
            return True
return False

Carnatic

How would you improve your solution if is asked to an interview session :)? – Howling

It will return true by adding number to itself also. – Plenish

Answer 21

C# solution:

bool flag = false;
            var list = new List<int> { 10, 15, 3, 4 };
            Console.WriteLine("Enter K");
            int k = int.Parse(Console.ReadLine());

            foreach (var item in list)
            {
                flag = list.Contains(k - item);
                if (flag)
                {
                    Console.WriteLine("Result: " + flag);
                    return;
                }
            }
            Console.WriteLine(flag);

Stigmatism

Answer 22

My C# Implementation:

 bool  isPairPresent(int[] numbers,int value)
 {
        for (int i = 0; i < numbers.Length; i++)
        {
            for (int j = 0; j < numbers.Length; j++)
            {
                if (value - numbers[i] == numbers[j])
                    return true;
            }
        }
        return false;
 }

Gombosi

Answer 23

Here's a javascript solution:

function ProblemOne_Solve()
{
    const k = 17;
    const values = [10, 15, 3, 8, 2];
    for (i=0; i<values.length; i++) {
        if (values.find((sum) => { return k-values[i] === sum} )) return true;
    }
    return false;
}

Thorny

Answer 24

I implemented with Scala

  def hasSome(xs: List[Int], k: Int): Boolean = {
    def check(xs: List[Int], k: Int, expectedSet: Set[Int]): Boolean = {
      xs match {
        case List() => false
        case head :: _ if expectedSet contains head => true
        case head :: tail => check(tail, k, expectedSet + (k - head))
      } 
    }
    check(xs, k, Set())
  }

Trace

Answer 25

I have tried the solution in Go Lang. However, it consumes O(n^2) time.

package main

import "fmt"

func twoNosAddUptoK(arr []int, k int) bool{
    // O(N^2)
    for i:=0; i<len(arr); i++{
        for j:=1; j<len(arr);j++ {
            if arr[i]+arr[j] ==k{
                return true
            }
        }
    }
    return false
}

func main(){
    xs := []int{10, 15, 3, 7}
    fmt.Println(twoNosAddUptoK(xs, 17))
}

Ice

Answer 26

Here's two very quick Python implementations (which account for the case that inputs of [1,2] and 2 should return false; in other words, you can't just double a number, since it specifies "any two").

This first one loops through the list of terms and adds each term to all of the previously seen terms until it hits the desired sum.

def do_they_add(terms, result):
    first_terms = []
    for second_term in terms:
        for first_term in first_terms:
            if second_term + first_term == result:
                return True
        first_terms.append(second_term)
    return False

This one subtracts each term from the result until it reaches a difference that is in the list of terms (using the rule that a+b=c -> c-a=b). The use of enumerate and the odd list indexing is to exclude the current value, per the first sentence in this answer.

def do_they_add_alt(terms, result):
    for i, term in enumerate(terms):
        diff = result - term
        if diff in [*terms[:i - 1], *terms[i + 1:]]:
            return True
    return False

If you do allow adding a number to itself, then the second implementation could be simplified to:

def do_they_add_alt(terms, result):
    for term in terms:
        diff = result - term
        if diff in terms:
            return True
    return False

Paroicous

Answer 27

solution in javascript

this function takes 2 parameters and loop through the length of list and inside the loop there is another loop which adds one number to other numbers in the list and check there sum if its equal to k or not

const list = [10, 15, 3, 7];
const k = 17;

function matchSum(list, k){
 for (var i = 0; i < list.length; i++) {
  list.forEach(num => {
   if (num != list[i]) {
    if (list[i] + num == k) {
     console.log(`${num} + ${list[i]} = ${k} (true)`);
    }
   }
  })
 }
}

matchSum(list, k);

Tervalent

Hi, welcome to SO. Your answer will be much more useful if you include an explanation of how your code answers the question. – Ostiole

Answer 28

My answer to Daily Coding Problem

# Python 2.7
def pairSumK (arr, goal):
  return any(map(lambda x: (goal - x) in arr, arr))

arr = [10, 15, 3, 7]
print pairSumK(arr, 17)

Alienism

Answer 29

Here is the code in Python 3.7 with O(N) complexity :

            def findsome(arr,k):
                if  len(arr)<2:
                    return False;
                for e in arr:
                    if k>e and (k-e) in arr:
                        return True
                return False

and also best case code in Python 3.7 with O(N^2) complexity :

            def findsomen2 (arr,k):
                if  len(arr)>1:
                    j=0
                    if arr[j] <k:
                        while j<len(arr):
                            i =0
                            while i < len(arr):
                                if arr[j]+arr[i]==k:
                                    return True
                                i +=1
                            j +=1
                return False

Fairlie

The first solution is not O(N) at all! Checking of existence of element in unsorted array involves linear operation, i.e. scanning array one by one. And you do it in a loop. Thus the complexity is still O(N^2) – Vacate

Answer 30

Javascript Solution

function matchSum(arr, k){
  for( var i=0; i < arr.length; i++ ){
    for(var j= i+1; j < arr.length; j++){
       if (arr[i] + arr[j] === k){
        return true;
      }
     }
    }
    return false;
  }

Kenley

Answer 31

Using vavr library it can be done in pretty concise way:

List<Integer> numbers = List(10, 15, 3, 7);
int k = 17;
boolean twoElementsFromTheListAddUpToK = numbers
                .filter(number -> number < k)
                .crossProduct()
                .map(tuple -> tuple._1 + tuple._2)
                .exists(number -> number == k);

Doublestop

Answer 32

C++ solution.

Note: requires C++20 (as 'contains' is used)

Complexity O(N) (because complexity of inserting and searching in hashmap is O(1))

Working link to Wandbox: https://wandbox.org/permlink/KPlzNIlKnTrV5z4X

#include <iostream>
#include <vector>
#include <unordered_map>
#include <optional>

using opt = std::optional<std::pair<int, int> >;

template <class T, class U>
std::ostream& operator<<(std::ostream& out, const std::pair<T, U>& p)
{
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}

opt check(std::vector<int> nums, int k)
{
    std::unordered_map<int, int> ht;
    for (const auto& n : nums) {
        if (ht.contains(n)) {
            return opt({ ht[n], n });
        }
        ht[k - n] = n;
    }
    return std::nullopt;
}

int main()
{
    auto res = check({ 10, 15, 3, 7 }, 17);
    if (res)
        std::cout << *res << std::endl;
    else
        std::cout << "Not found" << std::endl;
}

Vacate

Answer 33

Daily Coding Problem released a version of the problem in your question...

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

Here is a Ruby implementation based on your second suggestion. I am unsure if optimisations can be made.

Assumption: "list of numbers" is actually a set of numbers.

def one_pass_solution
    k = 17
    arr = [10, 15, 3, 7]
    l = 0
    r = arr.length-1
    arr.sort!
    while l < r do
        if arr[l] + arr[r] < k
            l += 1
        elsif arr[l] + arr[r] > k
            r -= 1
        else
            return true
        end
    end
    return false
end

Subgenus

Answer 34

Most of the posted solutions doesn't account for k to be twice of any of the numbers in list, then their solutions would generate false-positives. The following code accounts for that case as well. Since operations involving set is O(1), Our final solution is a single-pass O(N) solution.

from typing import Optional, List


def add_upto_k(k: int, array: Optional[List] = None) -> bool:
    assert array, "Non array input"
    assert len(array) != 0, "Array is empty"

    diff_set = set()

    for iterator in array:
        diff = k - iterator
        if iterator in diff_set:
            return True
        diff_set.add(diff)
    return False


if __name__ == "__main__":
    print(add_upto_k(k=17, array=[10, 15, 3, 7])) # True
    print(add_upto_k(k=15, array=[10, 15, 3, 7])) # False
    print(add_upto_k(k=20, array=[10, 15, 3, 10])) # True
    print(add_upto_k(k=20, array=[10, 15, 3, 7])) # False

Contend

Answer 35

My answer using Set in Swift to make search time O(n)

func twoNumbersEqualToK(array: [Int], k: Int) -> Bool {
  let objectSet = Set(array)

  for element in objectSet {
    let x = k - element

    if objectSet.contains(x) {
      return true
    }
  }

  return false
}

Melina

Answer 36

With O(N) complexity

private static boolean check_add_up(int[] numbers, int total) {
        Set<Integer> remainders = new HashSet<>();
        int remainder;
        for (int number : numbers ) {
            if (remainders.contains(number)) {
                return true;
            }

            remainder = total - number;

            if(!remainders.contains(remainder)){
                remainders.add(remainder);
            }
        }

        return false;
    }

Felike

Answer 37

Javascript answer with O(n)

function checkPair(arr, n) {
  for (var i in arr) {
    if (arr.includes(n - arr[i])) {
      return true;
    }
  }
  return false;
}

var a = [4,2,8,7,5,77,6,3,22];
var n = 99;
var m = 100;

console.log(checkPair(a, n));
console.log(checkPair(a, m));

Sewerage

Answer 38

Here is a scala solution that goes beyond the boolean result and returns the pair if it exists:

def thereIs(list2check: List[Int], k: Int): List[Int] =  list2check match {
    case Nil => Nil
    case x :: tail => tail.flatMap{
        case element if (element+ x)==k =>List(element,x)
        case element if (element+ x)!=k => Nil
    } ++ thereIs(tail,k)
}

Racklin

Answer 39

package ArrayPractice;

import java.util.Scanner;

public class Question5 {
    public boolean cons(int[] test) {
        for (int i = 0; i < test.length; i++) {
            for (int j = i + 1; j < test.length; j++) {
                if (test[i] == test[j]) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the array range: ");
        int x = sc.nextInt();
        int[] testing = new int[x];
        for (int y = 0; y < testing.length; y++) {
            System.out.println("Enter the Array number: " + y);
            testing[y] = sc.nextInt();
        }
        Question5 question5 = new Question5();
        System.out.println(question5.cons(testing));
    }
}

Outhouse

Answer 40

In Swift This method runs in O(n log n) because we’re using the built in sorted()

func findTwoSumSorted(inputArray: [Int], sum: Int) {
    let sortedArray = inputArray.sorted()
    var leftIndex = 0
    var rightIndex = sortedArray.count - 1
    
    while leftIndex < rightIndex {
        let leftElement = sortedArray[leftIndex]
        let rightElement = sortedArray[rightIndex]
        let currentSum = leftElement + rightElement
        
        if currentSum == sum {
            print("(\(leftElement), \(rightElement))")
            return
        } else if currentSum < sum {
            leftIndex += 1
        } else {
            rightIndex -= 1
        }
    }
}

Corcyra

Answer 41

simple checking (k - arrayValue) will not work because if k = 4 and there is one 2 in array - it will be false positive
so you need to exclude cheked values from further loops
it can be done with pop function for arrays

php solution:

$answer = function (int $k, array $arr) {
    $inarray = false;
    while (($value = array_pop($arr))) {
        if (in_array(($k - $value), $arr, true)) {
            $inarray = true;
            break;
        }
    }
    return $inarray;
};
var_dump($answer(17, [10, 15, 3, 7]));

python solution:

def ListCheck():
    number = 11
    nums = [10, 15, 3, 7, 9, 6, 4, 8]
    found = 0
    while found == 0:
        if len(nums) < 2: # check if array has at least 2 numbers
            break
        while len(nums) > 1:
            comparenum = nums.pop() # removes comparable number from array to avoid false true if nums has item == number*2 
            if (number - comparenum) in nums:
                print(True)
                found = 1
                break

    if found == 0:
        print(False)
        

ListCheck()
exit

Girlish

Answer 42

The approaches you mentioned are valid, but they have a time complexity of O(n^2) and O(nlogn), respectively. It seems like you're looking for a more efficient solution.

A better approach to solve this problem with a time complexity of O(n) can be achieved by using a hash set to store the elements of the array as we traverse it. Here's the outline of the algorithm:

Initialize an empty hash set. Traverse the array from left to right: For each element num in the array, compute the target value as k - num. If the target value is already present in the hash set, it means we have found a subsequence of length 2 with the sum k. Return "Yes" and exit. Add the current element num to the hash set. If we have traversed the entire array without finding a subsequence of length 2 with the sum k, return "No". This approach works because as we traverse the array, we check if the complement of the current element (target) exists in the hash set. If it does, it means we have already encountered an element whose sum with the current element is equal to k. Since we're looking for subsequences of length 2, this approach will give the correct result.

def has_subsequence_with_sum_k(nums, k):
    num_set = set()
    for num in nums:
        target = k - num
        if target in num_set:
            return "Yes"
        num_set.add(num)
    return "No"

This approach has a time complexity of O(n) because the hash set allows constant-time average case lookup and insertion.

Exponible

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Stour

I see a miniscule difference to Saurabh's 2018/10 answer - care to spell it out? (The function name is odd for just mentioning subsequence - I'd prefer pair.) – Twoseater

Answer 43

    function check(arr,k){
    var result = false;
    for (var i=0; i < arr.length; i++){
        for (var j=i+1; j < arr.length; j++){
            result = arr[i] + arr[j] == k;
            console.log(`${arr[i]} + ${arr[j]} = ${arr[i] + arr[j]}`);      
        if (result){
            break;
        }
    }
    return result;
}

Javascript.

Jablon

Answer 44

Python:

l1 = [10, 15, 3, 7]

k = 18

[True for i in l1 if (k - i) in l1]

Zoography