Overcome TLE (Time Limit Exceeded) Error for python code

Question

I have tried code on GeeksforGeeks which is giving TLE error while submitting.

Here is the question:
Geek is given an array of nums of length n and two integers x and y. Geek is interested to find the total number of pairs (i,j) such that x <= a[i]*a[j] <= y (1<=i<j<=n).
Help the geek to find total number of such pairs.

Example 1:

Input: nums[] = {5,3,7,9,7,9,7,7},                                                                
x = 7, y = 19  
Output: 1   
Explanation: There is only one pair which
satisfies the given conditions. The pair is
(1,2).

Example 2:

Input: nums[] = {3,5,5,2,6},                                   
x = 8, y = 13                                                                          
Output: 3  
Explanation: Pairs which satisfiy the given
conditions are (2,4), (3,4), (4,5).

Constraints:

1<=n<=10^4   
1<=nums[i]<=10^4      
1<=x<=y<=10^8

Here is my code:

class Solution:
    def TotalPairs(self, nums, x, y):
        count = 0
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if x <= nums[i]*nums[j] <= y:
                    count += 1
        return count


#{ 
#  Driver Code Starts
if __name__ == '__main__':
    T=int(input())
    for i in range(T):
        n, x, y = map(int, input().split())
        nums = list(map(int, input().split()))
        obj = Solution()
        ans = obj.TotalPairs(nums, x, y)
        print(ans)
# } Driver Code Ends

Output after submission:
Runtime Error:
Runtime ErrorTime Limit Exceeded

Your program took more time than expected.
Expected Time Limit 7.60sec
Hint : Please optimize your code and submit again.

That's the whole point of this exercise - to write code using more efficient algorithm — mvp
– mvp, Commented Jun 11, 2021 at 8:12
Try searching on GeeksforGeeks for the same question. There might be an article explaining how to optimize it. — nobleknight
– nobleknight, Commented Jun 11, 2021 at 17:16

Shrehan Raj Singh · Accepted Answer · 2021-06-11 08:31:44Z

1

With the use of combinations we can reduce O(n^2) to O(n). Try this:

from itertools import combinations
import math
class Solution:
    def TotalPairs(self, nums, x, y):
        count = 0
        _x = [a[0] * a[1] for a in list(combinations(nums, 2))]
        for i in _x:
            if x <= i <= y:
                count += 1
        return count

Edit: You can also use lru_cache to reduce execution time

from itertools import combinations
import math
from functools import lru_cache
import functools
import time
class Solution:
    def ignore_unhashable(func): 
        uncached = func.__wrapped__
        attributes = functools.WRAPPER_ASSIGNMENTS + ('cache_info', 'cache_clear')
        @functools.wraps(func, assigned=attributes) 
        def wrapper(*args, **kwargs): 
            try: 
                return func(*args, **kwargs) 
            except TypeError as error: 
                if 'unhashable type' in str(error): 
                    return uncached(*args, **kwargs) 
                raise 
        wrapper.__uncached__ = uncached
        return wrapper
    @ignore_unhashable
    @lru_cache(maxsize = 128)
    def TotalPairs(self, nums, x, y):
        count = 0
        _x = [a[0] * a[1] for a in list(combinations(nums, 2))]
        for i in _x:
            if x <= i <= y:
                count += 1
        return count

edited Jun 11, 2021 at 8:31

answered Jun 11, 2021 at 8:09

Shrehan Raj Singh

1561 silver badge9 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Ayush Over a year ago

Not really. The complexity of combinations itself here would be N choose 2, so it's still an N^2 solution.

Shrehan Raj Singh Over a year ago

Hmm... true that

Ayush Over a year ago

Wrote the idea for an NlogN solution below.

Ayush · Accepted Answer · 2021-06-11 08:25:36Z

You've got an O(N^2) solution.

Here's what I think you can do, without trying to give away much of the code since it's an exercise after all.

Essentially, for each number num in the array,
you need to find how many numbers exist in the array which are in the range [ceil(x/num), floor(y/num)].

Take an example, if x = 7 and y = 19, and say num = 2.
Then the minimum product that will satisfy the conditions is 8, which is num * ceil(x/num) = 2 * ceil(7/2) = 4
The maximum product likewise is 18, which is num * floor(y/num) = 2 * floor(19/2) = 18.
So for 2, you need numbers in the list that lie in the range [4, 9].

Does that give you a hint on what you're supposed to do?

You sort the array first.
Then for each num:
1)You find the index of ceil(x/num) and floor(y/num), using binary search
2)The number of pairs would be the difference of the two indices + 1.

The complexity for this would be, well you take O(NlogN) time to sort, and then you run through all the numbers which takes O(N) time, for each number you perform two binary search operations, so that's O(NlogN + 2*NlogN) = O(NlogN)

Collectives™ on Stack Overflow

Overcome TLE (Time Limit Exceeded) Error for python code

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related