Help | Different time complexity between a ** 2 and a * a in python?
38

Question: https://leetcode.com/problems/count-lattice-points-inside-a-circle/

For this question, when we calculate the distance between a point and a circle center, if we use (i - x) * (i - x) + (j - y) * (j - y) <= r * r then everything is ok. But if we use (i - x) ** 2 + (j - y) ** 2 <= r ** 2 then we will get time limit exceeded. I guess this is caused by differnet time complexity between a**2 and a * a in python. Anyone can explain it? Thanks a lot

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        result = set()
        
        for circle in circles:
            x, y, r = circle
            for i in range(x - r, x + r + 1):
                for j in range(y - r, y + r + 1):
                    if (i - x) * (i - x) + (j - y) * (j - y) <= r * r:
                        result.add((i, j))
                        
        return len(result)
Comments (1)