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;
}
}
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;
}
}
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
Top comments (0)