Find Four Elements that Sums to a given value in Java
A computer science problem called "Find Four Elements that Sums to a given value" gives us an array of integers and a target sum. The objective is to search the array for four unique elements whose sum equals the specified target value.
The goal is to identify four different indices (i, j, k, l) such that, given an array A of size n made up of integers and a target sum S :
A[i] + A[j] + A[k] + A[l] = S
Example 1:
Input: A = [1, 2, 3, 4, 5, 6, 7, 8] and target sum S = 20.
Output: 1, 3, 5, 7
Explanation: In the array, we are looking for four different elements whose sum equals S.
A[1] + A[3] + A[5] + A[7] = 2 + 4 + 6 + 8 = 20
Example 2:
Input: A = [-2, -1, 0, 1, 2, 3] and target sum S = 0.
Output: 0, 1, 3, 5
Explanation: In the array, we are looking for four different elements whose sum equals S.
A[0] + A[1] + A[3] + A[5] = -2 + (-1) + 1 + 3 = 0
Approach: Naive
Creating every possible combination of four elements from the array and comparing each combination's sum to the desired value is the naive method of determining which four elements add up to a given value.
Here is the implementation of the naive approach:
FileName: NaiveFourElementSum.java
import java.util.ArrayList;
import java.util.List;
public class NaiveFourElementSum {
public static void main(String args[]) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int targetSum = 20;
List<List<Integer>> result = findFourElements(arr, targetSum);
if (result.isEmpty()) {
System.out.println("No four elements found with the given sum.");
} else {
System.out.println("Four elements found: " + result);
}
}
public static List<List<Integer>> findFourElements(int[] arr, int targetSum) {
// Initialize a list to store the combinations of four elements that sum up to the target
List<List<Integer>> result = new ArrayList<>();
// Iterate through all possible combinations of four elements
int n = arr.length;
for (int i = 0; i < n - 3; i++) {
for (int j = i + 1; j < n - 2; j++) {
for (int k = j + 1; k < n - 1; k++) {
for (int l = k + 1; l < n; l++) {
// Check if the sum of the current combination equals the target sum
if (arr[i] + arr[j] + arr[k] + arr[l] == targetSum) {
// If so, add the combination to the result list
List<Integer> combination = new ArrayList<>();
combination.add(arr[i]);
combination.add(arr[j]);
combination.add(arr[k]);
combination.add(arr[l]);
result.add(combination);
}
}
}
}
}
// Return the list of combinations that satisfy the condition
return result;
}
}
Output:
Four elements found: [[1, 4, 7, 8], [1, 5, 6, 8], [2, 3, 7, 8], [2, 4, 6, 8], [2, 5, 6, 7], [3, 4, 5, 8], [3, 4, 6, 7]]
Complexity analysis: The time complexity of the naive method for locating four elements in an array that add up to a given value is O(n^4), where n is the array's size. Since it doesn't require any additional data structures that scale with the size of the input array, the naive approach to finding four elements that sum to a given value in an array has an O(1) space complexity.
Approach: Optimized
Sorting the array and applying the two-pointer technique together is an efficient way to find four elements in Java that add up to a given value.
FileName:OptimizedFourElementSum.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class OptimizedFourElementSum {
public static void main(String args[]) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int targetSum = 20;
List<List<Integer>> result = findFourElements(arr, targetSum);
if (result.isEmpty()) {
System.out.println("No four elements found with the given sum.");
} else {
System.out.println("Four elements found: " + result);
}
}
public static List<List<Integer>> findFourElements(int[] arr, int targetSum) {
// Initialize a list to store the combinations of four elements that sum up to the target
List<List<Integer>> result = new ArrayList<>();
int n = arr.length;
Arrays.sort(arr);
for (int i = 0; i < n - 3; i++) {
for (int j = i + 1; j < n - 2; j++) {
// Use two pointers approach to find the remaining two elements
int left = j + 1;
int right = n - 1;
// Move the pointers based on the sum of elements
while (left < right) {
int sum = arr[i] + arr[j] + arr[left] + arr[right];
if (sum == targetSum) {
List<Integer> combination = new ArrayList<>();
combination.add(arr[i]);
combination.add(arr[j]);
combination.add(arr[left]);
combination.add(arr[right]);
result.add(combination);
left++;
right--;
} else if (sum < targetSum) {
left++;
} else {
right--;
}
}
}
}
// Return the list of combinations that satisfy the condition
return result;
}
}
Output:
Four elements found: [[1, 4, 7, 8], [1, 5, 6, 8], [2, 3, 7, 8], [2, 4, 6, 8], [2, 5, 6, 7], [3, 4, 5, 8], [3, 4, 6, 7]]
Complexity analysis: Because of sorting and nested loops, the optimal method for locating four elements in Java that add up to a given value has a time complexity of O(n^3), where n is the array's size. Since the result list only needs constant additional space, its space complexity is O(1).