Need to pay attention to a lot of corner cases...


  • 15

    This problem contributed a lot of bugs to my contest score... Let's read the description again, pay attention to red sections:

    Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

    Some damn it! test cases:

    1. [0], 0 -> false;
    2. [5, 2, 4], 5 -> false;
    3. [0, 0], 100 -> true;
    4. [1,5], -6 -> true;
      etc...
    public class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {
            // Since the size of subarray is at least 2.
            if (nums.length <= 1) return false;
            // Two continuous "0" will form a subarray which has sum = 0. 0 * k == 0 will always be true.
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] == 0 && nums[i + 1] == 0) return true;
            }
    
            // At this point, k can't be "0" any longer.
            if (k == 0) return false;
            // Let's only check positive k. Because if there is a n makes n * k = sum, it is always true -n * -k = sum.
            if (k < 0) k = -k;
    
            Map<Integer, Integer> sumToIndex = new HashMap<>();
            int sum = 0;
            sumToIndex.put(0, -1);
    
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                // Validate from the biggest possible n * k to k
                for (int j = (sum / k) * k; j >= k; j -= k) {
                    if (sumToIndex.containsKey(sum - j) && (i - sumToIndex.get(sum - j) > 1)) return true;
                }
                if (!sumToIndex.containsKey(sum)) sumToIndex.put(sum, i);
            }
    
            return false;
        }
    }
    

  • 2
    J

    I got 11 bugs... Just blown my mind. Next time I gotta read the description more carefully...


  • 4

    No doubt the edge cases were the trickiest part of this problem. I did not expect to see k being zero or negative or that a factor would be times zero. Anyhow, you definitely end up with a few more if statements!

        public bool CheckSubarraySum(int[] nums, int k) 
        {
            Dictionary<int,int> map = new Dictionary<int,int>();
            map[0] = -1;
            int sum = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                sum += nums[i];
                if (sum == 0 && i >= 1) return true;
                if (k != 0)
                {
                    int mod = sum % k;
                    if (map.ContainsKey(mod))
                    {
                        if (i - map[mod] >= 2) return true;
                    }
                    else
                    {
                        map[mod] = i;
                    }       
                }
                 
            }
            
            return false;
        }
    

  • 0
    S

    Similar solution with you (submitted in contest) in c++

    class Solution {
    public:
    
        bool hasZero(vector<int>& nums){
            for(int i=1; i<nums.size(); i++){
                if(nums[i] == 0 && nums[i-1] == 0) return true;
            }
            return false;
        }
    
        bool checkSubarraySum(vector<int>& nums, int k) {
            if(nums.size() < 2) return false;
            else if(hasZero(nums)) return true;
            
            if(k == 0) return false;
            k = abs(k);
            if(k == 1) return true;
            
            for(int i=0; i<nums.size(); i++){
                int sum = nums[i];
                for(int j=i+1; j<nums.size(); j++){
                    sum += nums[j];
                    if(sum % k == 0) return true;
                }
            }
            return false;
        }
    };
    

  • 0
    G

    A concise version in python

        def checkSubarraySum(self, nums, k):
            cache = {}
            cur = 0
            for i, x in enumerate(nums):
                if cur not in cache: cache[cur] = i
                cur = (cur + x) % k if k != 0 else cur + x
                if cur in cache and i > cache[cur]: return True
            return False
    

    PS: Got 11 bugs for modifying it, I want my acceptance rate back T_T


  • 0
    W

    Good solution, But can it handle the cases: [1,2] 2 ?


  • 0
    Y
    This post is deleted!

  • 0
    Y

    @wangv
    I don't think it does. It doesn't handle the length of the subarray.


  • 0
    Y

    It's good solution. But it doesn't handle the length of the subarray.
    I think we should use Map instead of Set to keep track of the ending index of the sum so that we could check for the length.


  • 0
    R

    [1, 1, -2], 0 ; should return true, but this function will return false?


  • 0
    X

    concise c++ using map

    class Solution {
    public:
        bool checkSubarraySum(vector<int>& nums, int k) {
            //find accumulative sums
    		vector<int>sums{0};
    		unordered_map<int, vector<int>> map;
    		map[0].push_back(-1);
    		for(int i = 0; i < nums.size(); i++){
    			int residue = (k == 0)? sums.back() + nums[i] : (sums.back() + nums[i]) % k;
    			sums.push_back(residue);
    			map[residue].push_back(i); //vector should be always sorted!
    			if(i - map[residue][0] >= 2) return true;
    		}
    		return false;
        }
    };
    

  • 0

    Handling Corner Cases
    Check in Array

    1. has_zero
    2. Two_consecutive Zero

    **If Array has Zero and K is 0, then check if it has two_zero if its has two_zero return True.
    else False.

    If Array don't have zero but k==0
    return false.**

    Rest the Problem is Piece of a Cake Use the Idea of Range Sum Query problem.

    class Solution {
    public:
        bool checkSubarraySum(vector<int>& nums, int k) {
            
            int n=nums.size();
            if(n<2)
            return false;
            bool has_zero=false;
            bool two_zero=false;
           // Handling Corner Case 
            for(int i=0;i<n;i++)
            {
                if(nums[i]==0)
                {
                    has_zero=true;
                    break;
                }
            }
            
            
            for(int i=0;i<n-1;i++)
            {
                if(nums[i]==0 && nums[i+1]==0)
                {
                    two_zero=true;
                    break;
                }
            }
            
            
            if(has_zero && k==0)
            {
                if(two_zero==true)
                return true;
                return false;
            }
            if(k==0 && has_zero==false)
            return false;
            
          //
          
            
            int dp[n+1];
            dp[0]=0;
            for(int i=1;i<=n;i++)
            {
                dp[i]=nums[i-1]+dp[i-1];
            }
            
            
            int i=n,j=0;
            while(i>0)
            {
                for(j=0;j<i-1;j++)
                {
                    if((dp[i]-dp[j])%k==0)
                    return true;
                }
                i--;
            }
            return false;
            
        }
    };
    

  • 0
    Z

    @shawngao This code gets accepted, but is incorrect for test case "[1, 2] 2"


  • 0

    @zestypanda You are right. Fixed my solution, thanks!


  • 0

    I just want to provide my understanding to this solution:
    We compute the sum for 0 to i. And we know that a sum of subarray is a sum of 0~i subtract a sum of 0~j.
    If we know the remainder(sum % k) of this two sum, that mains these two sums are n * k + remainder, and we remove the n * k part from these two sum because we don't care what is the n. If these two sum have same remainder, we can Eliminate the remainder, and the sum of subarray should be some n * k.
    alt text


Log in to reply
 

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