Develop a code to store n numbers in the list and find if there any 2 numbers in the list whose sum is equal to the number passed to the method.
And that method will return true if such 2 numbers exist in the list else will return false.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
/**
* @author Nitin Agrawal
* Below class contains 2 methods to find if any 2 numbers exist in the created
* list whose sum is equal to the passed value.
*/
public class TwoSumImpl {
private ArrayList<Integer> list = new ArrayList<>();
private boolean isSorted = false;
private int size;
private int lastValue;
/**
* Below method adds the numbers to the list.
* Currently this method is not synchronized, so if multiple threads try to
* insert the numbers in the list then it will impact the performance to find
* the result. So for multiple threaded environment, this method can be made
* synchronized at the object level.
*/
public void store(int value) {
list.add(value);
/**
* Below will determine if the sorting is required after the addition of
* new number to the list.
*/
// if(isSorted && value < list.get(list.size()-2))
if(isSorted && value < lastValue)
isSorted = false;
lastValue = value;
size++;
}
/**
* @param value
* @return boolean
* Below method determines if any two numbers are present in the list whose
* sum is equal to the value passed. In worst case its complexity will be nlogn.
* In case of multiple thread environment, it may give wrong results,
* so for such scenarios synchronize the method.
* It should perform faster than other methods given below.
*/
public boolean isSumFastest(int value) {
/**
* Below condition is to stop sort() to execute every time this method is
* called.
*/
if(!isSorted) {
Collections.sort(list);
isSorted = true;
}
int last = size - 1;
if(value < list.get(0) || value > list.get(last) + list.get(last-1))
return false;
// Integer[] array = list.subList(0, size).toArray(new Integer[size]);
int i = 0;
int rem = 0;
while(i < last) {
rem = value - list.get(i);
if(Collections.binarySearch(list, rem) > i)
return true;
i++;
}
return false;
/**
* @param value
* @return boolean
* Below method determines if any two numbers are present in the list whose
* sum is equal to the value passed.
* In case of multiple thread environment, it may give wrong results,
* so for such scenarios synchronize the method.
* It is slower than isSum2() and even slower than isSum1() sometimes
* but sometimes it surprises for some values to be the fastest method.
* and needs correction to give the correct results for large lists.
* It is also not suggested for use till its issue is resolved.
*/
public boolean isSum(int value) {
boolean isSwitch = false;
/**
* Below condition is to stop sort() to execute every time this method is
* called.
*/
if(!isSorted) {
Collections.sort(list);
isSorted = true;
}
// int last = list.size()-1;
int last = size - 1;
int start = 0;
if(value < list.get(0) || value > list.get(last) + list.get(last-1))
return false;
while(last > start) {
if(!isSwitch) {
int rem = value - list.get(last);
Integer[] array = list.subList(0, last).toArray(new Integer[last]);
/**
* Binary search is used to find the second number, if present
* in the remaining list in logn time.
*/
if(rem > array[0] && rem < array[--last] && Arrays.binarySearch(array, rem) >= 0) {
return true;
}
isSwitch = true;
} else {
int rem = value - list.get(start);
Integer[] array = list.subList(++start, last).toArray(new Integer[last]);
/**
* Binary search is used to find the second number, if present
* in the remaining list in logn time.
*/
try {
if(rem > array[start] && Arrays.binarySearch(array, rem) >= 0) {
return true;
}
} catch(NullPointerException e) {
return false;
}
isSwitch = false;
}
}
return false;
}
/**
* @param value
* @return boolean
* Below method determines if any two numbers are present in the list whose
* sum is equal to the value passed.
* In case of multiple thread environment, it may give wrong results,
* so for such scenarios synchronize the method.
* It is the fastest method among the 3 here in general but can be slower than isSum()
* sometimes. It can be suggested to use for large lists with stable performance.
*/
public boolean isSum2(int value) {
/**
* Below condition is to stop sort() to execute every time this method is
* called.
*/
if(!isSorted) {
Collections.sort(list);
isSorted = true;
}
int last = size - 1;
/**
* Below condition has to check all n-1 elements in worst case scenario
*/
for(int i = last; i > 0; i--) {
int rem = value - list.get(i);
Integer[] array = list.subList(0, i).toArray(new Integer[i]);
/**
* Binary search is used to find the second number, if present
* in the remaining list in logn time.
*/
if(Arrays.binarySearch(array, rem) >= 0) {
return true;
}
}
return false;
}
/**
* @param value
* @return boolean
* Below method determines if any two numbers are present in the list whose
* sum is equal to the value passed. In worst case its complexity will be n*n.
* In case of multiple thread environment, it may give wrong results,
* so for such scenarios synchronize the method.
* It is the slowest and you will not get the result in time for large lists,
* so not suggested to use except to test for small lists.
*/
public boolean isSum1(int value) {
if(!isSorted) {
Collections.sort(list);
isSorted = true;
}
int last = size - 1;
int rem = 0;
int count = last;
while(count > 0) {
rem = value - list.get(count);
if(rem >= list.get(0) && rem < list.get(last)) {
for(int i = last; i >= 0; i--) {
int temp = 0;
while(rem >= list.get(temp)) {
for(int j = temp; j < i; j++) {
if(rem == list.get(temp)) {
return true;
}
}
temp++;
}
}
}
count--;
}
return false;
}
public static void main(String[] args) {
TwoSumImpl twoSum = new TwoSumImpl();
for(int i = 1; i < 100000; i++) {
twoSum.store(i);
}
long start = System.currentTimeMillis();
System.out.println(twoSum.isSum(3));
System.out.println("Time taken by isSum() : " + (System.currentTimeMillis() - start) + " ms");
start = System.currentTimeMillis();
System.out.println(twoSum.isSum1(3));
System.out.println("Time taken by isSum1() : " + (System.currentTimeMillis() - start) + " ms");
start = System.currentTimeMillis();
System.out.println(twoSum.isSum2(3));
System.out.println("Time taken : by isSum2() " + (System.currentTimeMillis() - start) + " ms");
}
}
Better way to search in sorted Array -
int s1 = 0;
int l1 = size-1;
while(s1 < l1 && !result) {
if(data[s1]+data[l1] == sum)
result = true;
else if(data[s1]+data[l1] > sum)
l1--;
else if(data[s1]+data[l1] < sum)
s1++;
}
Best way to check if such 2 numbers exist -
public static boolean doesExist(int[] arr, int sum) {
boolean result = false;
HashSet<Integer> hs = new HashSet<>();
for(int num : arr) {
if(result = hs.contains(sum-num))
break;
hs.add(num);
}
return result;
}
And that method will return true if such 2 numbers exist in the list else will return false.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
/**
* @author Nitin Agrawal
* Below class contains 2 methods to find if any 2 numbers exist in the created
* list whose sum is equal to the passed value.
*/
public class TwoSumImpl {
private ArrayList<Integer> list = new ArrayList<>();
private boolean isSorted = false;
private int size;
private int lastValue;
/**
* Below method adds the numbers to the list.
* Currently this method is not synchronized, so if multiple threads try to
* insert the numbers in the list then it will impact the performance to find
* the result. So for multiple threaded environment, this method can be made
* synchronized at the object level.
*/
public void store(int value) {
list.add(value);
/**
* Below will determine if the sorting is required after the addition of
* new number to the list.
*/
// if(isSorted && value < list.get(list.size()-2))
if(isSorted && value < lastValue)
isSorted = false;
lastValue = value;
size++;
}
/**
* @param value
* @return boolean
* Below method determines if any two numbers are present in the list whose
* sum is equal to the value passed. In worst case its complexity will be nlogn.
* In case of multiple thread environment, it may give wrong results,
* so for such scenarios synchronize the method.
* It should perform faster than other methods given below.
*/
public boolean isSumFastest(int value) {
/**
* Below condition is to stop sort() to execute every time this method is
* called.
*/
if(!isSorted) {
Collections.sort(list);
isSorted = true;
}
int last = size - 1;
if(value < list.get(0) || value > list.get(last) + list.get(last-1))
return false;
// Integer[] array = list.subList(0, size).toArray(new Integer[size]);
int i = 0;
int rem = 0;
while(i < last) {
rem = value - list.get(i);
if(Collections.binarySearch(list, rem) > i)
return true;
i++;
}
return false;
/**
* @param value
* @return boolean
* Below method determines if any two numbers are present in the list whose
* sum is equal to the value passed.
* In case of multiple thread environment, it may give wrong results,
* so for such scenarios synchronize the method.
* It is slower than isSum2() and even slower than isSum1() sometimes
* but sometimes it surprises for some values to be the fastest method.
* and needs correction to give the correct results for large lists.
* It is also not suggested for use till its issue is resolved.
*/
public boolean isSum(int value) {
boolean isSwitch = false;
/**
* Below condition is to stop sort() to execute every time this method is
* called.
*/
if(!isSorted) {
Collections.sort(list);
isSorted = true;
}
// int last = list.size()-1;
int last = size - 1;
int start = 0;
if(value < list.get(0) || value > list.get(last) + list.get(last-1))
return false;
while(last > start) {
if(!isSwitch) {
int rem = value - list.get(last);
Integer[] array = list.subList(0, last).toArray(new Integer[last]);
/**
* Binary search is used to find the second number, if present
* in the remaining list in logn time.
*/
if(rem > array[0] && rem < array[--last] && Arrays.binarySearch(array, rem) >= 0) {
return true;
}
isSwitch = true;
} else {
int rem = value - list.get(start);
Integer[] array = list.subList(++start, last).toArray(new Integer[last]);
/**
* Binary search is used to find the second number, if present
* in the remaining list in logn time.
*/
try {
if(rem > array[start] && Arrays.binarySearch(array, rem) >= 0) {
return true;
}
} catch(NullPointerException e) {
return false;
}
isSwitch = false;
}
}
return false;
}
/**
* @param value
* @return boolean
* Below method determines if any two numbers are present in the list whose
* sum is equal to the value passed.
* In case of multiple thread environment, it may give wrong results,
* so for such scenarios synchronize the method.
* It is the fastest method among the 3 here in general but can be slower than isSum()
* sometimes. It can be suggested to use for large lists with stable performance.
*/
public boolean isSum2(int value) {
/**
* Below condition is to stop sort() to execute every time this method is
* called.
*/
if(!isSorted) {
Collections.sort(list);
isSorted = true;
}
int last = size - 1;
/**
* Below condition has to check all n-1 elements in worst case scenario
*/
for(int i = last; i > 0; i--) {
int rem = value - list.get(i);
Integer[] array = list.subList(0, i).toArray(new Integer[i]);
/**
* Binary search is used to find the second number, if present
* in the remaining list in logn time.
*/
if(Arrays.binarySearch(array, rem) >= 0) {
return true;
}
}
return false;
}
/**
* @param value
* @return boolean
* Below method determines if any two numbers are present in the list whose
* sum is equal to the value passed. In worst case its complexity will be n*n.
* In case of multiple thread environment, it may give wrong results,
* so for such scenarios synchronize the method.
* It is the slowest and you will not get the result in time for large lists,
* so not suggested to use except to test for small lists.
*/
public boolean isSum1(int value) {
if(!isSorted) {
Collections.sort(list);
isSorted = true;
}
int last = size - 1;
int rem = 0;
int count = last;
while(count > 0) {
rem = value - list.get(count);
if(rem >= list.get(0) && rem < list.get(last)) {
for(int i = last; i >= 0; i--) {
int temp = 0;
while(rem >= list.get(temp)) {
for(int j = temp; j < i; j++) {
if(rem == list.get(temp)) {
return true;
}
}
temp++;
}
}
}
count--;
}
return false;
}
public static void main(String[] args) {
TwoSumImpl twoSum = new TwoSumImpl();
for(int i = 1; i < 100000; i++) {
twoSum.store(i);
}
long start = System.currentTimeMillis();
System.out.println(twoSum.isSum(3));
System.out.println("Time taken by isSum() : " + (System.currentTimeMillis() - start) + " ms");
start = System.currentTimeMillis();
System.out.println(twoSum.isSum1(3));
System.out.println("Time taken by isSum1() : " + (System.currentTimeMillis() - start) + " ms");
start = System.currentTimeMillis();
System.out.println(twoSum.isSum2(3));
System.out.println("Time taken : by isSum2() " + (System.currentTimeMillis() - start) + " ms");
}
}
Better way to search in sorted Array -
int s1 = 0;
int l1 = size-1;
while(s1 < l1 && !result) {
if(data[s1]+data[l1] == sum)
result = true;
else if(data[s1]+data[l1] > sum)
l1--;
else if(data[s1]+data[l1] < sum)
s1++;
}
Best way to check if such 2 numbers exist -
public static boolean doesExist(int[] arr, int sum) {
boolean result = false;
HashSet<Integer> hs = new HashSet<>();
for(int num : arr) {
if(result = hs.contains(sum-num))
break;
hs.add(num);
}
return result;
}
