Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Why isnt this recursive algorithm working properly

Ive written a recursive algorithm to delete any duplicates from a sorted list

def removeDuplicates(nums):
        def helper(nums,value=1):
            if value == len(nums):
                return nums
            if(nums[value] == nums[value-1]):
                del nums[value]
                return helper(nums,value+1)
            else:
                return helper(nums,value+1)
        return helper(nums)

For an input of [0,0,1,1,1,2,2,3,3,4],
an output of [0,1,2,3,4] is expected.
But instead an output of [0,1,1,2,3,4] is supplied
Why isnt it working for triplets

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>Solution :

When you delete a value from the list the size changes so you do not need to increment value:

def removeDuplicates(nums):
        def helper(nums,value=1):
            if value == len(nums):
                return nums
            if(nums[value] == nums[value-1]):
                del nums[value]
                return helper(nums,value) #notice the change here
            else:
                return helper(nums,value+1)
        return helper(nums)

This section of code:

del nums[value]
return helper(nums,value+1)

Causes the function to "skip" a value because an element is removed (changing the item at the index value) and value is incremented (also changing which item is at index value.)

So it should be:

del nums[value]
return helper(nums,value)

New code output:

[0, 1, 2, 3, 4]

However the best way to get the unique values would be:

list(set(my_list)) #best
#or
list({k: '' for k in test}.keys())
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading