Given a sorted array, write a program to decide if two elements sum up to a third.

Question

OtherAnon · Accepted Answer

Assuming each number only appears once:

//Java code
public static void targetsum(int[] arr, int target)
  {
    if(arr == null)
      return;
    
    int start = 0;
    int end = arr.length -1;
    
    while(start target
        end--;
    }
  }

light · Answer

the algorithm for 3 elements sum up to a given number is also the same; the only change one needs to make is replace line
target=array[i];
with
target=total-array[i];

is there an algorithm with a lower order? says O( nlogn ); I am not able to think of anything!

Anon · Answer

Did you coded a solution < O(n^2 + logn) ?

Hesh · Answer

we can modify the 3sum algorithm for this.

Pal · Answer

It is possible to do it in O(n)
create a binary tree from the sorted array in O(n)
subtract each value in array  from target and find if its  there in the tree, 
if found push to hash map, with the array item as key and the subtracted value as key
 next time before subtracting value in the array from target check if it is in the hash map

light · Answer

typedef vector vint;
bool check_element_sum(vint &array)
{
   // n^2 algorithm
   sort(array.begin(),array.end()); //general case : nlogn

   copy(array.begin(),array.end(),ostream_iterator(cout," "));
   cout=0;--i) //n^2
   {
      start=0;
      end=i-1;
      target=array[i];
      //note a<=b<=c for the tuples formed here hence check for c=a+b only
      while(start

kungi · Answer

@Pal the hash map gives a lower constan because /2 elements need to be checked but the lookup is still n*logn

Ker · Answer

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;

public class SumOfTwoElements {

	public static void main(String[] args) {
		final Scanner in = new Scanner(System.in);
		final Random random = new Random();
		while (true) {
			System.out.println("Enter array size : ");
			int size = in.nextInt();

			int[] array = new int[size];
			for (int i = 0; i > findSummingTriplets2(int[] array) {
		final Set> summingTriplets = new HashSet>();

		for (int k = 2; k  array[k]) {
					j--;
				} else if (sum > findSummingTriplets(int[] array) {
		final Set> summingTriplets = new HashSet>();

		for (int i = 0; i  end) {
			return false;
		}
		int mid = start + (end - start) / 2;

		if (array[mid] > value) {
			return contains(array, start, mid - 1, value);
		} else if (array[mid] < value) {
			return contains(array, mid + 1, end, value);
		} else {
			return true;
		}
	}

}

O(n) time, O(1) space, C++ · Answer

bool sumExists(vector nums, int target) {
auto front = nums.begin();
auto back = nums.end() - 1;

while (front != back) {
if (*front + *back == target) return true;
else if (*front + *back < target) front++;
else back--;
}

return false;
}

Meta

Pregunta de entrevista de Meta

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo