Python TypeError: 'type' object does not support item assignment

Question

I have to design and implement a TwoSum class. It should support the following operations:

• add - Add the number to an internal data structure.
• find - Find if there exists any pair of numbers which sum is equal to the value.

Here is my code:

class TwoSum(object):

    dict = {}

    def add(self,n):
        dict[n] = n #TypeError: 'type' object does not support item assignment

    def find(self,n):
        for i in range(0,len(dict)+1):
            if dict[i] == None:
                continue

            val = n - dict[i]
            if dict[val] != None and val != i+1:
                return True
        return False

test = TwoSum()
test.add(1)
test.add(3)
test.add(5)
print(test.find(4))  # True
print(test.find(7))  # False

I got error message

TypeError: 'type' object does not support item assignment for "dict[n] = n"

Any help or suggestion? Thank you so much!

Answer 1

Lot of issues here, I'll try to go through them one by one

The data structure

dict = {}

Not only is this overwriting python's dict, (see mgilson's comment) but this is the wrong data structure for the project. You should use a list instead (or a set if you have unique unordered values)

Using the data structure

The data structure is an instance variable, it needs to be defined with self and inside the __init__ function. You should be using something like this:

class TwoSum(object):
    def __init__(self):
        self.numbers = []

def add

def add(self,n):
        dict[n] = n

Assigning items to a dictionairy is not the way to do it. You should instead append to your list. Additionally you need to append to the list for that instance using self.variableName = value

def find

That range is wrong, and you would need a nested range, or itertools.combinations since you have to check for any two numbers that sum to a certain value, pythons sum() is handy here.

To loop through the numbers you can use two ranges or itertools.combinations

The code

import itertools

class TwoSum(object):
    def __init__(self):
        self.numbers = []

    def add(self, num):
        self.numbers.append(num)

    def find(self, desiredSum):
        for nums in itertools.combinations(self.numbers, 2):
            if sum(nums) == desiredSum:
                return True
        return False


test = TwoSum()
test.add(1)
test.add(3)
test.add(5)
print(test.find(4))
print(test.find(7))
#True
#False

Def find without itertools

def find(self, desiredSum):
        for num1 in self.numbers:
            for num2 in self.numbers:
                if num1 + num2 == desiredSum and num1 != num2:
                    return True
        return False

Answer 2

The dict at the class level and the dict in the method are different

In the method, dict is the builtin python type. If you want to modify the dict on the class, you could try something like type(self).dict[n] = n

Also, for what it's worth, if your dict is always going to have the value == key, you might want to consider using a set instead.

Finally, you'd probably be better off defining dict as an instance attribute rather than a class attribute:

class TwoSum(object):
    def __init__(self):
        self.added_items = set()  # Make the `dict` -> `set` swap here too...
    def add(self, n):
        self.added_items.add(n)

Answer 3

class TwoSum(object):
    def __init__(self):
        self.__data = []

    def __repr__(self):
        return repr(self.__data)

    def add(self, n):
        self.__data.append(n)

    def find(self, n):
        for i, v in enumerate(self.__data):
            for x, v2 in enumerate(self.__data):
                if i!= x and v + v2 == n:
                    return True
        return False

Answer 4

Here is my solution, just another reference for any potential people who may see this question. Basically, I combined all above answers to get this solution. Credits to @Keatinge, @mgilson, @TheLazyScripter. Thank you guys all.

class TwoSum(object):
    def __init__(self):
        self.added_items = set()  # Make the `dict` -> `set` swap here too...
    def add(self, n):
        self.added_items.add(n)
    def find(self, n):
        for nums in itertools.combinations(self.added_items, 2):
            if sum(nums) == n:
                return True
        return False

test = TwoSum()
test.add(1)
test.add(3)
test.add(5)
print(test.find(4))
print(test.find(7))

Answer 5

I know I'm answering this late but I wanted to add some input after reading the other posts. Especially @keathige and anyone else that tells you not to use a dictionary for this problem.

The easiest way for me to explain this would be exploring the solution to this problem if you use a list as your ADT in your class.

let's say you call the find function and your list as N items in it. each item in the list would potentially have to compare itself with every other item in the list to see if there's a pair of numbers. So worst case you would have to check each element of the list N time and compare that with each other element in the list N times. In other words your function would have to do N * N operations to find a solution, which is O(N^2) [I'm not gonna dive to much into time complexity but having a O(N^2) is typically really bad!!].

On the other hand if you use a dictionary you could cut down the operations by the power of (1/2), aka taking the square root.

if you loop through each element in the dictionary one time you can check if a solution exists with math.

sum (the sum you're trying to check is possible with the numbers in your class)

item ( the current element in the dict you're looking over)

x ( if you add x to item it equals sum)

sum and item are given. So to find x, you can do (x = sum - item) then check if x is in your dictionary.