1 / 3
Jul 2023

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

    Jul '23
  • last reply

    Jul '23
  • 2

    replies

  • 410

    views

  • 2

    users

  • 2

    links

Thank you @simes. I was able to figure out my mistake with the test cases you have given.