Function returns how many integer elements in a list are exact squares of other elements in the same list [duplicate]

Question

Task:

Write a Python function that returns how many integer elements in a list are exact squares of other elements in the same list. Assume that the list does not contain negative numbers and that there are no duplicates.

This function takes in a list and returns the count. For example, if x is [3,4,0,2,1,9,25] then sum returns 4 because 3*3=9 , 0*0=0 , 1*1=1 , 2*2=4.

Here is my code:

x = [3,4,0,2,1,9,25]
def count(x):
    sum = 0
    for i in x:
       if i*i in x is True:
            sum += 1
    return sum

When I run count(x) the output is 0 not 4, I think the logic is correct.

Answer 1

The operator is is a comparison operator, thus when you do i*i in x is True, Python interprets it as i*i in x and x is True. In that case x is True is always false.

Note that you do not explicitly need to compare the value to True, since in returns a boolean.

x = [3,4,0,2,1,9,25]
def count(x):
    sum = 0
    for i in x:
       if i*i in x: # Simply remove 'is True'
            sum += 1
    return sum

Although, thes above is O(n²) due to list lookup. You could use a set for constant time lookup and use the fact that True == 1 and False == 0 to use sum and get an efficient O(n) algorithm.

def count(x):
    x_set = set(x)
    return sum(i*i in x_set for i in x)