# the problem specification fools me

• 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
``````

• (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).

• 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!

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