CareerCup

I have been trying to find a solution to improve the cost but I haven't been able to. Solution with O(n^2) time and O(n) memory

def thereIsSum(seq):
     valid_sums = set(seq)
     for x in xrange(len(seq)):
         for y in xrange(x+1, len(seq)):
             if seq[x] + seq[y] in valid_sums:
                 return True
     return False

input array has only 3 elements or more.

@ChrisK I thought about that but I got stuck, I can see a linear algorithm using two counters if you have a number to guide the search. I mean given the next array

[10, 20, 35, 40, 75, 90, 180]

If you have two counters one for the lower element and one for the higher element how you do modify them? Potentially any number except the two first ones and the last one can be used to generate a solution.
I have been thinking about some other approaches but none worked.

@ChrisK
-- how about -ve numbers ?

arr = [-2,-1,0,1, 3 ]
x = sum_in_array_sort(arr,-1)
print (x)

@ChrisK that is the problem I was encountering if you have the desired sum you can guide the search using two counters but on the given problem you have length of the array - 2 possible desired sums (the two first elements of the array can't be the desired sum for obvious reasons) so you can't use the algorithm as is to solve the problem.

public class ArraySum {

public static void main(String[] args) {
checksuma ch = new checksuma();
int as[] = { 20, 40 ,20};
System.out.println(ch.methsummc(as));
;
}

}

class checksuma {
boolean b = false;

public boolean methsummc(int ex[]) {
for (int i = 0; i < ex.length; i++) {
for (int j = 0; j < ex.length; j++) {
for (int k = j + 1; k < ex.length; k++) {
if (ex[i] == ex[j] + ex[k]) {
b = true;
}
}

}

}
return b;
}

}

@Fernando, now I see, the sum is any number in the array. It seems like 3-sum and there are better solutions far beyond simple. For your solution, be careful to not reuse elements in the sum.

bool is_sum_of_two_elem_present(vector<int>&& arr) {
  sort(arr.begin(), arr.end());
  for (auto target = arr.rbegin(); target != next(arr.rend(), -2); ++target) {
    auto to_find = *target - *next(target);
    if (binary_search(next(target,2), arr.rend(), to_find, std::greater<int>())) return true;
  }
  return false;

function check(arr){
  
  var a = arr.sort()
 console.log(a) 
  for(var i = 0; i < a.length -2; i++){
    var t = ( Math.abs(a[i+2]) == Math.abs(a[i]) + Math.abs(a[i+1]) )
    if(t){
      return true
    }
  }
  return false;
  
}

console.log(check([1,2,3])) // true
console.log(check([1,7,6])) // true
console.log(check([-1,9,8])) // true
console.log(check([-1,4,8])) // false
console.log(check([-3,-5,-8])) // true

x = [10,20,30];

for(var i= 0; i < x.length; i++)
{
a =0;
b=0;
c= 0;
if(i < x.length){
a=i;
}
else{
a=0;
}
if(a < x.length-1){
b=a+1;
}
else{
b=0;
}
if(b < x.length-1){
c=b+1;
}
else{
c=0;
}
if(x[a] == x[b] + x[c]) {
console.log("true" + " " + ":" + x[a] + "=" + x[b] + "+" + x[c]);
}
else{
console.log("false" + " " + ":" + x[a] + "=" + x[b] + "+" + x[c]);
}

}

Try copy pasting in console and this will work fine for array of three numbers.

try copy pasting in console and this snippet will work for array of three int.

for(var i= 0; i < x.length; i++)
{
a =0;
b=0;
c= 0;
if(i < x.length){
a=i;
}
else{
a=0;
}
if(a < x.length-1){
b=a+1;
}
else{
b=0;
}
if(b < x.length-1){
c=b+1;
}
else{
c=0;
}
if(x[a] == x[b] + x[c]) {
console.log("true" + " " + ":" + x[a] + "=" + x[b] + "+" + x[c]);
}
else{
console.log("false" + " " + ":" + x[a] + "=" + x[b] + "+" + x[c]);
}
}

@Fernando ... Can we do better? O(n^2) is an obvious solution.