Coursera hackerrank question - Min discount


  • 1
    M

    Min discount problem -
    In simple words, there is an array - prices array : [5, 4, 5, 1, 3, 3, 8, 2]
    The discount on the price is the first equal to or lowest element on the right side of current price. Output the total in the end and also list of items index that will not get any discount.
    For example -
    5 - 4 = 1
    4 - 1 = 3
    5 - 1 = 4
    1 - 0 = 1 (This element didn't got any discount)
    3 - 3 = 0
    3 - 2 = 1
    8 - 2 = 6
    2 - 0 = 2 (This element will also not get discount as no equal to or less than price on right).

    Output -
    Total = 18
    Elements ID not getting discount - 3, 7

    Approaches I tried -

    1. Brute force - Timed out for 3 test cases (They expect lower time complexity)
    2. Keep a minimum index stored, so only find minIndex when current index is equal to or less than minIndex but it fails in test case like [3, 4, 4, 3].
      It will do 3 - 3, 4 - 3 (incorrect as it should be 4 - 4 as 4 is next equal to or less element available in first right).

    Any O(n) or better solution than O(n^2)?


  • 0

    N log N. Hint, how would you find the first discount of [X, 100, 99, 98, 97, ..., 2, 1] for different X ?


  • 0
    M

    @awice The array is not sorted so we cannot apply binary search.


  • 0

    @mithunjmistry If you have [X, (90 91 92 ... 99), (80, 81, 82, ...., 89), (70, 71, 72 ..., 79), (60, 61, ..., 69), ...., (10, 11, 12, ..., 19) ], what are the possible answers for the discount of X?


  • 0
    M

    @awice If my X is greater than 90 or equal to 90, the first right element less than or equal to X is 90, so my algorithm should stop there and subtract 90 - X.
    If X is less than 90, there will be no discount on that item and I have to put index of it in an array which is required in output in items that didn't got discount.
    So I really couldn't think of any logN algorithm to search the FIRST RIGHTMOST less than or equal element than X which is O(n) worst case. So O(n) for n elements makes this O(n^2) algorithm. Also cannot maintain minIndex because of the test case I mentioned in example. Can you please provide a n log N solution on what you are thinking?


  • 0

    @mithunjmistry If X is say 85, the discount is 5 (X - 80). In general, the "discount neighbor" can only be 90, 80, 70, ..., 10.

    This leads to the following idea: work through the array from right to left, and keep a list of candidate discount neighbors. You can prove they must be decreasing numbers (In the previous example, after parsing all numbers except X, the candidates are [90, 80, ..., 10]). Since these are sorted, you can binary search the candidates to find the correct discount neighbor.


  • 0
    M

    @awice Can you please code a solution for the original question?
    [5, 4, 5, 1, 3, 3, 8, 2]
    I don't see anything sorted here on the left. Also, we cannot change the array in any way by sorting because we need to output index number of items that will not get a discount as well.

    So, right to 5 is subarray [4,5,1,3,3,8,2]. I can no way relate or apply the logic you mean to say. They are not sorted, no range specified and I cannot see a way for logN solution.
    For example, for [5,6,6,6,6,6,6,6,6,4]
    Here, 5 will get discount of 4, but 6 should get discount of 6. So, I cannot think of anything but brute force. If you can provide code about your idea which would work in these test cases in N log N would be appreciated.


  • 2

    @mithunjmistry

    from bisect import bisect
    
    def brute(A):
        ans = []
        for i, x in enumerate(A):
            for j, y in enumerate(A[i+1:], i+1):
                if y <= x:
                    ans.append(x - y)
                    break
            else:
                ans.append(x)
        return ans
    
    def solve(A):
        N = len(A)
        ans = [None] * N
        C = [] #increasing candidates
        for i in xrange(N - 1, -1, -1):
            while C and C[-1] > A[i]: C.pop()
            ans[i] = A[i] - C[max(bisect(C, A[i])-1, 0)] if C else A[i]
            C.append(A[i])
        return ans
    
    
    from itertools import permutations
    for A in permutations(range(8)):
        assert brute(A) == solve(A)
        
    for A in permutations(range(4) + range(4)):
        assert brute(A) == solve(A)
    

  • 0
    H

    @awice Can you please explain your "solve" method?

    And what is its time complexity?


  • 0

    @hundiwala N log N. Make N push/pops to C, and binary search N times.
    The loop invariant is, C is a increasing sequence of values from A[N-1], A[N-2], ..., A[i+1] where each element chosen has no equal or lesser value occurring later in that sequence.
    You can use print statements if you want to debug the code.


  • 0
    M

    @awice Great solution! Kudos


  • 2

    Is this not same as this question?

    Just use stack?

    https://leetcode.com/problems/daily-temperatures/description/
    Here's it asks for next higher temperature, but for discount it's just next equal/lower


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.