class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] pairs = new int[spells.length];

        Arrays.sort(potions);

        for (int i = 0; i < spells.length; i++) {
            int count = potions.length;

            int left = 0;
            int right = potions.length - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2;

                if ((long)potions[mid] * spells[i] < success) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }

            pairs[i] = count - left;
        }

        return pairs;
    }
}

# @param {Integer[]} spells
# @param {Integer[]} potions
# @param {Integer} success
# @return {Integer[]}
def successful_pairs(spells, potions, success)
  pairs = Array.new spells.length

  potions.sort!

  spells.each_with_index do |spell, index|
      count = potions.length

      # binary search
      left = 0
      right = potions.length - 1
      while left <= right
          mid = left + (right - left) / 2
          if potions[mid] * spell < success
              left = mid + 1
          else
              right = mid - 1
          end
      end

      pairs[index] = count - left
  end

  pairs
end