Problem:
For a given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
Solution:
package com.basics;
import java.util.Scanner;
public class FindExactSum {
static int[] array;
int arrayLimit;
int x;
public static void main(String[] args) {
FindExactSum findExactSum = new FindExactSum();
findExactSum.initializeTheArrays();
System.out.println("is the array contains two elements whose sum is exactly equal to given x?? " + findExactSum.isExactSumAvaiableInTheArray());
}
public void initializeTheArrays(){
Scanner scanner = new Scanner(System.in);
System.out.println("enter the array limit");
arrayLimit = scanner.nextInt();
array = new int[arrayLimit];
System.out.println("enter the array elements");
for (int i = 0; i < array.length; i++) {
System.out.println("enter the element");
array[i] = scanner.nextInt();
}
System.out.println("enter the x value");
x = scanner.nextInt();
scanner.close();
}
public boolean isExactSumAvaiableInTheArray(){
boolean flag = false;
for (int i = 0; i < array.length; i++) {
for (int j = i; j < array.length; j++) {
if(array[i] + array[j] == x){
flag = true;
break;
}
}
}
return flag;
}
}
Output:
enter the array limit
3
enter the array elements
enter the element
12
enter the element
12
enter the element
3
enter the x value
14
is the array contains two elements whose sum is exactly equal to given x?? false
For a given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
Solution:
package com.basics;
import java.util.Scanner;
public class FindExactSum {
static int[] array;
int arrayLimit;
int x;
public static void main(String[] args) {
FindExactSum findExactSum = new FindExactSum();
findExactSum.initializeTheArrays();
System.out.println("is the array contains two elements whose sum is exactly equal to given x?? " + findExactSum.isExactSumAvaiableInTheArray());
}
public void initializeTheArrays(){
Scanner scanner = new Scanner(System.in);
System.out.println("enter the array limit");
arrayLimit = scanner.nextInt();
array = new int[arrayLimit];
System.out.println("enter the array elements");
for (int i = 0; i < array.length; i++) {
System.out.println("enter the element");
array[i] = scanner.nextInt();
}
System.out.println("enter the x value");
x = scanner.nextInt();
scanner.close();
}
public boolean isExactSumAvaiableInTheArray(){
boolean flag = false;
for (int i = 0; i < array.length; i++) {
for (int j = i; j < array.length; j++) {
if(array[i] + array[j] == x){
flag = true;
break;
}
}
}
return flag;
}
}
Output:
enter the array limit
3
enter the array elements
enter the element
12
enter the element
12
enter the element
3
enter the x value
14
is the array contains two elements whose sum is exactly equal to given x?? false
enter the array limit
4
enter the array elements
enter the element
12
enter the element
33
enter the element
2
enter the element
33
enter the x value
35
is the array contains two elements whose sum is exactly equal to given x?? true
time Complexity is O(N^2) where N is length of array. This can be improve as below :
ReplyDeleteMap map = new HashMap<>();
public boolean isExactSumAvaiable(int[] array, int sum) {
int n = array.length;
int result = 0;
int value = 0;
for(int i = 0; i < n; i++) {
value = array[i];
result = sum - value;
if(map.get(result) != null) {
return true;
} else {
/** map.put(result, map.get(result) == null ? 1 : map.get(result) +1); */
//I am hard coding the value in map
map.put(result, 1);
}
}
return false;
}
Time Complexity is O(N) and Space Complexity is O(N)