I am getting WA, but can’t find the bug myself. Please help.
Used Meet in the middle and Binary Search approach.
Here is my code if anyone want to have a look.
import java.util.;
import java.lang.;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in2);
int size = sc.nextInt(), A = sc.nextInt(), B = sc.nextInt();
int arr_1_len = size/2, arr_2_len = (int)Math.ceil(size/2.0);
int[] arr_1 = new int[arr_1_len];
int[] arr_2 = new int[arr_2_len];
for(int i=0; i<arr_1_len; i++) {
arr_1[i] = sc.nextInt();
}
for(int i=0; i<arr_2_len; i++) {
arr_2[i] = sc.nextInt();
}
Solution sol = new Solution();
System.out.println(sol.getCountOfSubsets(arr_1, arr_2, arr_1_len, arr_2_len, A, B));
}
}
class Solution {
public long getCountOfSubsets(int[] arr_1, int[] arr_2, int size_1, int size_2, int A, int B) {
long ans = 0;
ArrayList<Integer> subsets_1 = new ArrayList<>();
ArrayList<Integer> subsets_2 = new ArrayList<>();
getAllSubsets(arr_1, subsets_1, size_1, 0, 0);
getAllSubsets(arr_2, subsets_2, size_2, 0, 0);
Collections.sort(subsets_2);
for(int i=0; i<1 << size_1; i++) {
int num_1 = A - subsets_1.get(i), num_2 = B - subsets_1.get(i);
int temp_1 = lowerBound(subsets_2, num_1, 1 << size_2), temp_2 = upperBound(subsets_2, num_2, 1 << size_2);
ans += (temp_2 - temp_1);
}
return ans;
}
public void getAllSubsets(int[] arr, ArrayList<Integer> list, int size, int sum, int index) {
if(index == size) {
list.add(sum);
return;
}
sum += arr[index];
getAllSubsets(arr, list, size, sum, index + 1);
sum -= arr[index];
getAllSubsets(arr, list, size, sum, index + 1);
}
public int lowerBound(ArrayList<Integer> arr, int num, int size) {
int low = 0, high = size - 1, ans = -1;
while(low <= high) {
int mid = (low + high)/2;
if(arr.get(mid) >= num) {
ans = mid;
high = mid - 1;
}
else low = mid + 1;
}
return ans == -1 ? 0 : ans;
}
public int upperBound(ArrayList<Integer> arr, int num, int size) {
int low = 0, high = size - 1, ans = -1;
while(low <= high) {
int mid = (low + high)/2;
if(arr.get(mid) > num) {
ans = mid;
high = mid - 1;
}
else low = mid + 1;
}
return ans == -1 ? 0 : ans;
}
}
created
last reply
- 2
replies
- 410
views
- 2
users
- 2
links