CODEWITHSUNDEEP
algorithmdynamic-programming
lkahtz
lkahtz

Reputation: 4796

Erroneous dynamic programming algorithm

Transferred from Code Review. If this question is not suitable for SO either, please let me know. I will remove it.

I am working on an algorithm puzzle here at: https://www.hackerrank.com/challenges/hackerland-radio-transmitters/forum

It cannot pass all of the test cases. Some test cases have such large arrays that it gets so hard to debug. Simple cases from my end seem all work fine. Can anyone look into this and share what is wrong with this algorithm? Basically it just loops through the array and find every furthest covered station (as origin). A counter-like variable result record the origins (radio stations).

def solution(k, arr, origin=0):
    arr = sorted(list(set(arr)))
    result = 1
    cur = 0
    origin = 0

    for i in range(1, len(arr)):
        if arr[i] - arr[origin] <= k:
            pass
        else:
            origin = i - 1
            j = 1
            while origin + j < len(arr):
                if arr[origin + j] - arr[origin] <= k:
                    pass
                else:
                    origin = origin + j
                    i = origin + j + 1
                    result += 1
                    continue
                j += 1
    return result

Upvotes: 2

Views: 106

Answers (2)

arunk2
arunk2

Reputation: 2416

Most of your code is correct. Only problem is with the usage of For range outer loop and continue in the inner loop.

  • For range loop doesn't change the i value @ runtime (it is more like a ForEach loop).
  • The continue will not terminate the inner loop - you may want to use break.

The following code passed all the test cases

def solution(k, arr, origin=0):
    arr = sorted(list(set(arr)))
    print arr
    result = 1 
    cur = 0
    origin = 0
    i = 0 

    while (i < len(arr)):
        if arr[i] - arr[origin] <= k:
        i = i + 1
            pass
        else:
            origin = i - 1
            j = 1
            while origin + j < len(arr):
                if arr[origin + j] - arr[origin] <= k:
                    pass
                else:
                    # Start for next station position from this point
                    i = origin + j
                    origin = i
                    # need another radio station
                    result += 1
                    break
                j += 1
    return result

hope it helps!

Upvotes: 2

four_lines
four_lines

Reputation: 503

You're placing the first object on the first index. The first object in the optimal solution can be placed later too.

solution(1,[1,2,3,4,5,6]) prints 3, when it should be 2 (by placing the two objects on 2 and 5). You place your first object on 1, then 3 and then 5. It should ideally be placed on 2, then 5.

Upvotes: 1

Related Questions