DEV Community

Tanuja V
Tanuja V

Posted on • Edited on

3 1

Successful Pairs of Spells and Potions | LeetCode | Java

Approach 1 : Brute Force

This approach will give TLE(Time Limit Exceed). So, it forces us the optimize the solution.

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {

        int sLen = spells.length;
        int pLen = potions.length;

        int res[] = new int[sLen];

        for(int i=0; i<sLen; i++){
            int num = spells[i];
            int mul = 0;
            int count = 0;
            for(int j=0; j<pLen; j++){
                mul = num * potions[j];
                if(mul>=success){
                    count++;
                }
                mul = 0;
            }

            res[i] = count;
        }

        return res;
    }
}
Enter fullscreen mode Exit fullscreen mode

Approach 2 : Binary Search

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {

        int sLen = spells.length;

        int pLen = potions.length;

        int res[] = new int[sLen];

        Arrays.sort(potions);

        for(int i=0; i<sLen; i++){
            int getCount = getCount(potions, spells[i], pLen, success);
            res[i] = getCount;
        }

        return res;
    }

    int getCount(int potions[], int num, int n, long success){
        int low = 0;
        int high = n-1;
        int mid = 0;

        while(low<=high){
             mid = low + (high-low)/2;

            long mul = (long)num * potions[mid];

            if(mul<success)
                low = mid+1;

            else
                high = mid-1;
        }

        return n-low;
    }
}
Enter fullscreen mode Exit fullscreen mode

Thanks for reading 🥰
Feel free to comment ✍️
Follow for more 🤝 && Happy Coding 🚀

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs