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--;

}

}

9 Answers

▲

2

▼

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--;

}

}

▲

0

▼

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

▲

1

▼

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!

▲

1

▼

we can modify the 3sum algorithm for this.

▲

1

▼

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

▲

0

▼

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

▲

0

▼

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;

}

}

}

▲

0

▼

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;

}

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

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