We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Successful Pairs of Spells and Potions

Number: 2392

Difficulty: Medium

Paid? No

Companies: Amazon, Goldman Sachs

Problem Description

Given two positive integer arrays spells and potions along with an integer success, determine for each spell the number of potions that form a successful pair. A pair is considered successful if the product of a spell's strength and a potion's strength is at least success.

Key Insights

  • Sort the potions array to leverage binary search.
  • For each spell, determine the minimum required potion strength using ceiling division.
  • Use binary search to efficiently find the first potion that meets or exceeds the required strength.
  • The number of valid pairs for a spell is the number of potions to the right of (and including) that position.

Space and Time Complexity

Time Complexity: O(m log m + n log m) where m is the number of potions and n is the number of spells. Space Complexity: O(m) for the sorted potions and O(n) for the result array.

Solution

The solution sorts the potions to allow for binary searching the smallest potion that, when multiplied by a given spell, reaches the success threshold. For each spell, compute the minimum required potion strength using integer math to perform ceiling division: required = (success + spell - 1) // spell. Then, perform a binary search in the sorted potions array to find the first index of a potion that is at least the required strength. The remaining number of potions from that index to the array's end gives the count of successful pairs for that spell.

Code Solutions

# Python solution with line-by-line comments
from bisect import bisect_left

def successfulPairs(spells, potions, success):
    # Sort the potions array for binary search
    potions.sort()
    n = len(potions)
    result = []
    
    # Iterate over each spell
    for spell in spells:
        # Compute the minimum required potion strength using ceiling division
        required = (success + spell - 1) // spell
        
        # Use binary search to find the leftmost index where potion >= required
        idx = bisect_left(potions, required)
        
        # The count of successful pairs is the number of potions from idx to the end
        result.append(n - idx)
    
    return result

# Example usage:
spells = [5, 1, 3]
potions = [1, 2, 3, 4, 5]
success = 7
print(successfulPairs(spells, potions, success))  # Expected output: [4, 0, 3]
← Back to All Questions