the problem specification fools me


  • 1
    Z

    in the problem description, it specially notes that 0 < nums.length <= 50000. which means O(n^2) brute force solution is not acceptable, however, it does!!
    I spent much time to figure out a fast solution, but you only need to write a brute force solution in a contest, to get 7 points, just need to be brave enough and endurable for the potential 5 minutes penalty!!

    I really hope the contest editor can seriously honor your problem specification and test cases.

    the damm brute force solution in python, it runs 375ms in contest total 64 cases, but runs 3160ms for single case which nums=[1]* 10000, k=2:

    class Solution(object):
        def numSubarrayProductLessThanK(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            ret = 0
            for i in xrange(len(nums)):
                p = 1
                for j in xrange(i, len(nums)):
                    p *= nums[j]
                    if p >= k:
                        break
                    ret += 1
            return ret
    

    the ugly but faster solution I write in contest, it only runs 6ms for nums=[1]*10000, k=2

    class Solution(object):
        def numSubarrayProductLessThanK(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            if k == 0:
                return 0
            ret = 0
            s = 0
            e = -1
            p = 1
            while s < len(nums):
                for i in xrange(e + 1, len(nums) + 1):
                    if i >= len(nums):
                        e = i - 1
                        break
                    p *= nums[i]
                    if p >= k:
                        p /= nums[i]
                        e = i - 1
                        break
                l = e - s + 1
                if l > 0:
                    ret += l * (1 + l) / 2 - (l - 1) * l / 2
                    p /= nums[s]
                s += 1
            return ret
    

  • 0

    (Edit: This is now obsolete for the above post since it got fixed)

    Good point but sadly a bit hurt by incorrectly using little-o instead of big-O. Little-o does exist and differs from big-O. Your second solution isn't o(n), since that's impossible (if with "n" you mean the length of nums). Similar problem with your "N" vs your "n". That's two different variables. Pick one and stick with it (preferably "n", since that's the standard).


  • 0
    Z

    @StefanPochmann said in the problem specification fools me:

    Good point but sadly a bit hurt by incorrectly using little-o instead of big-O. Little-o does exist and differs from big-O. Your second solution isn't o(n), since that's impossible (if with "n" you mean the length of nums). Similar problem with your "N" vs your "n". That's two different variables. Pick one and stick with it (preferably "n", since that's the standard).

    Thank you very much!


Log in to reply
 

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