6096. Successful Pairs of Spells and Potions

Problem Statement

Pattern: Floor Ceil

---

Solution

static class Solution {
	private int findCeil(int[] arr, long key) {
		int n = arr.length, start = 0, end = n - 1, mid = 0;
		// converge start
		while (start <= end) {
			mid = start + (end - start) / 2;
			if (key <= arr[mid]) end = mid - 1;
			else start = mid + 1;
		}
		// element not found
		if (start == n) return 0;   // if all elements smaller than key, start OOB
		return n - start;             // return no. of elements larger than key
	}
	
	public int[] successfulPairs(int[] spells, int[] potions, long success) {
		int[] res = new int[spells.length];
		Arrays.sort(potions);
		for (int i = 0 ; i < spells.length ; i++) {
			long key = (success + spells[i] - 1) / spells[i];   // ceil of division
			res[i] = findCeil(potions, key);
		}
		return res;
	}
}

Notes

• Element in Potions array will be smaller than success/spell
  • Now all you have to do is find the Ceil of that number
  • Sinc we are adding success and spells we need key to be of long since both can be 10^5 at max