educative.io

Isn't it more efficient to solve with dictionary/hashmap?

Courses
,
#1

The problem uses a LinkedList, as part of the lesson. Given that we don’t have the restriction to use a specific data structure, isn’t it more efficient to solve this problem using a dictionary/hashmap.

the code would look like this:

def find_happy_number(num):
	dict = {}
	while num != 1:
		# split the num by digits
		num_list = [int(i)**2 for i in str(num)]
		num = sum(num_list)
		dict[num] = dict.get(num, 0) + 1
		if dict[num] > 1:
			# found a cycle
			return False

	return True

we don’t have any recursive calls, neither have to continue calculating the squares once we detect a duplicate number.

Share your thoughts please.

#2

I think so, but using a dict will cause the Time Complexity to be O(N) instead of O(1) in their solution. Probably a good thing to understand to talk through with an interviewer.

#3

Came here to see if anyone else was asking this question. A hashmap (or a set) definitely seems like the more intuitive way to solve this. I think they should add to the prompt that they’re looking for a solution with O(1) space complexity—that would rule out the hashmap/set method.