Should the brutal force O(N^2) solution even be accepted?


  • 0

    Since there is a way more optimized solution which takes O(n), I'm surprised that my brutal force O(n^2) solution was accepted. The solution was just to calculate all the subsequences' sum and see if it can be divided by the target...


  • 0

    BTW this is the code.

    public class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {
            if(nums.length < 2) return false;
            if(k == 1) return true;
            for(int i = 0; i < nums.length - 1; i++){
                int sum = nums[i];
                for(int j = i + 1; j < nums.length; j++){
                    sum += nums[j];
                    if(k == 0){
                        if(sum == 0) return true;
                    } else if(sum % k == 0) return true;
                }
            }
            return false;
        }
    }

  • 1

    I don't think it should be accepted. The test suite is weak. I just ran your solution with additional counting of the inner loop iterations and got these statistics:

    n = 5   k = 6   result = true   steps = 4
    n = 5   k = 6   result = true   steps = 4
    n = 5   k = -6   result = true   steps = 4
    n = 5   k = -6   result = true   steps = 4
    n = 5   k = 0   result = false   steps = 10
    n = 1   k = 0   result = false   steps = 0
    n = 2   k = 0   result = true   steps = 1
    n = 3   k = 0   result = false   steps = 3
    n = 2   k = -1   result = true   steps = 1
    n = 1   k = -1   result = false   steps = 0
    n = 1   k = 1   result = false   steps = 0
    n = 3   k = -1   result = true   steps = 1
    n = 5   k = -1   result = true   steps = 1
    n = 5   k = 1   result = true   steps = 0
    n = 6   k = 1   result = true   steps = 0
    n = 6   k = -1   result = true   steps = 1
    n = 6   k = 1   result = true   steps = 0
    n = 6   k = 0   result = false   steps = 15
    n = 1   k = 1   result = false   steps = 0
    n = 2   k = 2   result = true   steps = 1
    n = 2   k = 1   result = true   steps = 0
    n = 3   k = 6   result = true   steps = 2
    n = 3   k = 5   result = true   steps = 3
    n = 3   k = 4   result = false   steps = 3
    n = 3   k = 5   result = true   steps = 2
    n = 3   k = 5   result = false   steps = 3
    n = 2   k = 1   result = true   steps = 0
    n = 1   k = 1000000000   result = false   steps = 0
    n = 2   k = 100000000   result = true   steps = 1
    n = 100   k = 250   result = true   steps = 106
    n = 100   k = 479   result = true   steps = 391
    n = 100   k = 75   result = true   steps = 247
    n = 100   k = 337   result = true   steps = 408
    n = 100   k = 231   result = true   steps = 25
    n = 100   k = 77   result = true   steps = 267
    n = 100   k = 347   result = true   steps = 574
    n = 100   k = 338   result = true   steps = 130
    n = 100   k = 198   result = true   steps = 66
    n = 100   k = 523   result = true   steps = 488
    n = 1000   k = 274   result = true   steps = 32
    n = 1000   k = 377   result = true   steps = 169
    n = 1000   k = 85   result = true   steps = 164
    n = 1000   k = 378   result = true   steps = 63
    n = 1000   k = 253   result = true   steps = 157
    n = 1000   k = 285   result = true   steps = 28
    n = 1000   k = 493   result = true   steps = 662
    n = 1000   k = 306   result = true   steps = 347
    n = 1000   k = 520   result = true   steps = 259
    n = 1000   k = 222   result = true   steps = 168
    n = 10000   k = 3092   result = true   steps = 679
    n = 10000   k = 750   result = true   steps = 2005
    n = 10000   k = 698   result = true   steps = 620
    n = 10000   k = 2517   result = true   steps = 2254
    n = 10000   k = -2955   result = true   steps = 1277
    n = 10000   k = -3129   result = true   steps = 2772
    n = 10000   k = -2063   result = true   steps = 468
    n = 10000   k = -2445   result = true   steps = 1099
    n = 10000   k = -4753   result = true   steps = 3186
    n = 10000   k = -1908   result = true   steps = 4196
    n = 10000   k = -796   result = true   steps = 1014
    n = 10000   k = -2977   result = true   steps = 23347
    n = 10000   k = -313   result = true   steps = 124
    n = 10000   k = -193   result = true   steps = 256
    n = 10000   k = -2147483640   result = true   steps = 99946
    n = 10000   k = 2147483640   result = true   steps = 99946
    n = 1000   k = 732193917   result = false   steps = 499500
    n = 1000   k = 392878155   result = false   steps = 499500
    n = 1000   k = 787392336   result = false   steps = 499500
    n = 1000   k = 16666677   result = false   steps = 499500
    n = 1000   k = 1257549993   result = false   steps = 499500
    n = 1000   k = -1532966398   result = false   steps = 499500
    n = 1000   k = -721351345   result = false   steps = 499500
    n = 1000   k = -1668852807   result = false   steps = 499500
    n = 1000   k = -1277220540   result = false   steps = 499500
    n = 1000   k = -615201247   result = false   steps = 499500
    

    You can see that all test cases with the largest allowed nums (where n is 10,000) only take up to 99,946 steps. Far smaller than the 49,995,000 steps they can potentially take. The hardest test cases take 499,500 steps because the result is false so you don't get an early exit but go through every possible subarray, but n is only 1,000 there.

    Here's my code which generated the above statistics. My realCheckSubarraySum is your original solution, except for the added test.steps++;.

    public class Solution {
    
        class Test {
            int n, k, steps;
            boolean result;
        };
    
        static List<Test> tests = new ArrayList<>();
        static Test test;
    
        public boolean checkSubarraySum(int[] nums, int k) {
            tests.add(test = new Test());
            test.n = nums.length;
            test.k = k;
            test.result = realCheckSubarraySum(nums, k);
            if (tests.size() < 75)
                return test.result;
            for (Test test : tests)
                System.out.println("n = " + test.n + "   k = " + test.k + "   result = " + test.result + "   steps = " + test.steps);
            throw new RuntimeException();
        }
            
        public boolean realCheckSubarraySum(int[] nums, int k) {
            if(nums.length < 2) return false;
            if(k == 1) return true;
            for(int i = 0; i < nums.length - 1; i++){
                int sum = nums[i];
                for(int j = i + 1; j < nums.length; j++){
                    test.steps++;
                    sum += nums[j];
                    if(k == 0){
                        if(sum == 0) return true;
                    } else if(sum % k == 0) return true;
                }
            }
            return false;
        }
    }
    

  • 0

    @StefanPochmann Thanks dude.

    So maybe we can see if we can re-grade the test? I didn't bother implementing the brutal force solution above during the contest thinking it would hit TLE for sure.

    Also wonder how do you know the max number of steps that leetcode can take is "49,995,000", is this an insider info?


  • 0

    @DonaldTrump said in Should the brutal force O(N^2) solution even be accepted?:

    how do you know the max number of steps that leetcode can take is "49,995,000", is this an insider info?

    No, that's due to the 10,000 numbers limit stated in the problem.


  • 0
    // OJ: https://leetcode.com/problems/continuous-subarray-sum
    // Auther: github.com/lzl124631x
    // Time: O(N^2) -- 92ms 3/23/2017
    // Space: O(1)
    class Solution {
    public:
      bool checkSubarraySum(vector<int>& nums, int k) {
        for (int i = 0; i < nums.size(); ++i) {
          for (int j = 0; j < i; ++j) {
            nums[j] += nums[i];
            if (k) nums[j] %= k;
            if (!nums[j]) return true;
          }
        }
        return false;
      }
    };
    

Log in to reply
 

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