CareerCup

static boolean hasGivenSum(int[] array, int sum) {

HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> hashMapIndexes = new HashMap<Integer, Integer>();
boolean response = false;

for(int i = 0; i < array.length; i++){
hashMap.put(i,sum - array[i]);
hashMapIndexes.put(array[i],i);
}


for(int i = 0; i < array.length; i++){

int rest = hashMap.get(i);

if(hashMapIndexes.containsKey(rest) && hashMapIndexes.get(rest) != i){
response = true;
break;
}

}

return response;

}

I think the below approach will also work.

1 . Sort the array in ascending order
2. Initialize 2 indices start = 0 and end = array.length -1
3. if sum (array[start] + array[end]) == required Sum return true
4. if sum (array[start] + array[end]) > required Sum --- > end--
5. if sum (array[start] + array[end]) < required Sum -- > start++
6. repeat step 3,4,5 till start < end
7. otherwise return false.

class IsPresent
{
        private static boolean checkPresent(int[] intArray, int k)
        {
                for(int i=0; i<intArray.length; i++)
                        for(int j=0 ; j<intArray.length ; j++)
                        {
                                if( i!=j && intArray[i] + intArray[j] == k)
                                        return true ;
                        }
                return false ;
        }
        public static void main(String args[])
        {
                int[] intArray = {1,2,3,4,5};
                int k = 96 ;
                System.out.println("\n output :"+ checkPresent(intArray,k)) ;
                k=8 ;
                System.out.println("\n output :"+ checkPresent(intArray,k)) ;
        }
}

Using a hashmap is the obvious solution for O(n) time and O(n) extra space.

Without extra space you can sort the array in O(nLogn) then the following algorithm

procedure find_sum_k 
  for i in 0..Array.length - 1
    let p = k - Array[i]
    try find `j` index of `p` in Array via binary search 
    if j return true
  }
  return false

O(nlogn) time complexity, no additional space.

return false

My solution:

static boolean hasGivenSum(int[] array, int sum) {

HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> hashMapIndexes = new HashMap<Integer, Integer>();
boolean response = false;

for(int i = 0; i < array.length; i++){
hashMap.put(i,sum - array[i]);
hashMapIndexes.put(array[i],i);
}


for(int i = 0; i < array.length; i++){

int rest = hashMap.get(i);

if(hashMapIndexes.containsKey(rest) && hashMapIndexes.get(rest) != i){
response = true;
break;
}

}

return response;

}

package main

import "fmt"

func checkSumK(m []int, K int) bool {
	if len(m) < 2 {
		return false
	}

	elms := map[int]bool{}
	for _, el := range m {
		tmp := K - el
		_, ok := elms[tmp]
		if ok {
			return true
		}
		elms[el] = true
	}

	return false
}

func main() {
	fmt.Println(checkSumK([]int{1, 4, 5, 5, 7}, 12))
}

and

def function(array,sum):
for i in array:
for x in array:
if x != i and x+i == sum:
return True
return False

and

// ZoomBA.
def has_sum( arr, K ){
  /* create a dictionary where the key is K - current_item 
    and the value is the current items index */
  subs = dict( arr ) -> { [ K - $.item , $.index ] }
  /* You would expect that when an item in the array is present
  as the key in the subs dictionary, you are good. 
  But you are wrong, what about :
     there is an element e such that : K = e + 2 = 2e ?  
  In that case, we check i am not matching the same element again 
  as I am checking the index */
  exists ( arr ) :: { $.item @ subs && subs[$.item] != $.index }  
}
// no 2*e form 
println( has_sum ( [1,0,4,10,12] , 14 ) )
// there is a 2*e form 
println( has_sum ( [1,0,4,7,12] , 14 ) )
// 2* e form, but there is a duplicate so...
println( has_sum ( [1,0,4,7,7,12] , 14 ) )

from collections import Counter
def check_sum(arr, k):
    counter = Counter(arr)
    for i, cnt in counter.items():
        rem = k-i
        if rem == i:
            if cnt > 1:
                return True
        elif rem in counter:
            return True
    return False

arr = [1, 2, 2,3,4,5]
k = 6
print check_sum(arr, k)

def self.calculate(array, k)
    i=0

    while(i < array.size) do
      val_at_i = array[i]
      array.each.with_index(i) do |value, index|
        sum = val_at_i + value
        return true if sum == k
      end
      i=i+1
    end
    return false
  end

function hasGivenSum(array, sum) {
	for (var i = 0; i < array.length; i++) {
		for (var j = i+1; j < array.length; j++) {
			console.log('sum: ', array[i], array[j], array[i] + array[j], sum);
			if (array[i] + array[j] === sum) {
				return true;
			}
		}
	}
	return false;
}

In Java, it's qutie simple with single Hashmap and with the time efficiency of O(n)

public static boolean containsSum (Integer [] inputArray, int k) {
	    if(inputArray == null || inputArray.length == 0) {
	        return false;
	    }
	     HashMap <Integer, Integer> sumMap = new HashMap <Integer, Integer>();
         for(Integer i: inputArray) {
             if(sumMap.containsKey(k-i)) {
                 return true;
             } 
             sumMap.put(i,i);
         }
         return false;
	}

how about using a Set,

Set set = new Set();
for(int i =0; i < array.size(); i ++){
	int sub = K - array[i];
	if(set.contains(sub)){
		return true;	
}else{
set.add(array[i);
}
}
return false;