Python with explanation. 62ms Time O(min(n, k)) mostly


  • 10
    Z
    • if k == 0
      If there are two continuous zeros in nums, return True
      Time O(n).
    • if n >= 2k and k > 0
      There will be at least three numbers in sum with the same remainder divided by k. So I can return True without any extra calculation.
      Time O(1).
    • if n < 2k and k > 0
      If I can find two numbers in sum with the same remainder divided by k and the distance of them is greater than or equal to 2, return True.
      Time O(n) <= O(k).
    • k < 0
      same as k > 0.
    class Solution(object):
        def checkSubarraySum(self, nums, k):
    
            
            if k == 0:
                # if two continuous zeros in nums, return True
                # time O(n)
                for i in range(0, len(nums) - 1):
                    if nums[i] == 0 and nums[i+1] == 0:
                        return True
                return False
            
            k = abs(k)
            if len(nums) >= k * 2:
                return True
            
            #if n >= 2k: return True
            #if n < 2k:  time O(n) is O(k)  
    
            sum = [0]
            for x in nums:
                sum.append((sum[-1] + x) % k)
            
            Dict = {}
            for i in range(0, len(sum)):
                if Dict.has_key(sum[i]):
                    if i - Dict[sum[i]] > 1:
                        return True
                else:
                    Dict[sum[i]] = i
            
            return False
    

  • 1

    I'd say O(min(n,k)), as O(k) looks bad for small n and large k.


  • 0
    Z

    @StefanPochmann Thanks, I have changed the title.


  • 0
    C

    I have trouble understanding your argument about the second case:

    if n >= 2k and k > 0
    There will be at least three numbers in sum with the same remainder divided by k. So I can return True without any extra calculation.

    Can you enlighten me?
    Thanks.


  • 2
    Z

    @CS-ganster

    x % k can be an integer from 0 to k-1.

    array nums has more than 2*k numbers, so array sum has more than 2*k + 1 numbers.

    Because of pigeonhole principle, we can find at least three numbers in sum with the same remainder divided by k.

    Distance of the first one and the third one is greater than or equal to 2. It means there are at least two consecutive numbers in nums which sums up to the multiple of k.


  • 1

    @zym_ustc Just an idea for the k == 0 case:

        if k == 0:
            return (0, 0) in zip(nums, nums[1:])

  • 0

    Brilliant pigeonhole principle idea.


  • 1
    L

    The sums can be computed on the fly, no need to precompute and store them. Kudos for the pigeonhole part.

    class Solution(object):
        def checkSubarraySum(self, nums, k):
            if k == 0: return any(a==b==0 for a, b in zip(nums, nums[1:]))
            k = abs(k)
            s, t = 0, {0: -1}
            for i, v in enumerate(nums):
                s = (s + v) % k
                j = t.get(s)
                if j == None:
                    t[s] = i
                elif i - j >= 2:
                    return True
            return False
    

  • 5

    To deal with the case k=0, in my version, I don't calculate the remainder divided by k.

    def checkSubarraySum(self, nums, k):
            r = 0
            seen = {0: -1}
            for i, num in enumerate(nums):
                r = (r + num) % k if k else r + num
                if r not in seen: seen[r] = i
                if i - seen[r] > 1: return True
            return False
    

    @StefanPochmann : Thanks for your reminder


  • 1

    @lee215 Reminder: It's "remainder" :-P


  • 0
    M

    That's a really clever use of pigeonhole principle :)


  • 0

    @zym_ustc I have a question about the sum, it is true the sum array will have 2k + 1 numbers when the nums length is 2k. The sum need to be at least the sum of at least two numbers, but the first two in sum do not count for this scenario. Does this mean we need 2k + 2 numbers to have 2k + 1 sum numbers?


  • 0
    Z

    @JohnWick It is enough that the distance of two sum in sum[] is greater than or equal to 2. It means the length of the subarray between these two sum is at least two. Sum don't need to be the sum of at least two numbers.

    num[] = {1, 2}   k = 3
    sum[] = {0, 1, 0}    (mod k)
    

    sum[0] and sum[2] is OK.


  • 0

    @zym_ustc Yes, you are right, thank you for your explanation!


  • 0
    F
    for x in nums:
        sum.append((sum[-1] + x) % k) <- we used n steps to build sum
    

    why O(min(n,k))? why not O(n)?


  • 0
    Z

    @fuyangzhen They are same here. n < 2k means O(min(n, k)) = O(n) = O(k).


  • 0
    F

    @zym_ustc Thank U for the explain for rookie question :D
    Ps. I don't know why just ask a question can let someone give me one '-1' Reputation···


  • -1
    A
    This post is deleted!

  • 0
    S

    @zym_ustc said in Python with explanation. 62ms Time O(min(n, k)) mostly:

    It means there are at least two consecutive numbers in nums which sums up to the multiple of k.

    It means there are at least two consecutive numbers in nums which sums up to the multiple of k.
    how can we conclude this?


Log in to reply
 

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