C++ Arithmetic progression||17 ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nNo sorting, no hash function.\nJust consider the the properties for arithmetic progress
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nNo sorting, no hash function.\nJust consider the the properties for arithmetic progression.\n\n2nd approach is a variant of 1st code by replacing `isArithmetic` by `isArithmetic0` which takes less space & less time, runs in 17ms & beats 100%.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAn arithmetic progression looks like:\n$$\na_0, a_1=a_0+d, a_2=a_0+2d, \\cdots, a_i=a_0+id,\\cdots, a_{s-1}=a_0+(s-1)d\n$$\nwhere $a_0$ is the leading term, $d$ is the difference of adjacent numbers.\n\nBuild a function `isArithmetic` to check whether the subarray is a permutation for an arithmetic progression.\n\n1. Let $a_0=$`minN`, $a_{s-1}$=`maxN` denote the min, max for this subarray.\n2. Set `diff=maxN-minN`, If `diff==0`, this is a constant subarray & return 1\n3. Build a boolean array `isElt` \n4. Consider the numbers `x=num-minN` for `num` in this subarray, set `isElt[x]=1`.\n5.  `if diff mod (s-1)!=0` cannot be an arithmetic progression return 0\n6.  Check `isElt[x]` for  x=d, 2d,...,diff-d. If any `isElt[x]==0` return 0 otherwise return 1.\n7.  2nd apporach is a slight modification. Instead of boolean array `isElt` uses other smaller boolean array `term` which is more efficient.\n8.  For comparison, the implementations using unordered_set & set as hash set are done but only showing the numerical data.\n\n|C++ implementation| Elapsed Time|\n|---|---|\n|1st code isArithmetic|23 ms|\n|2nd code isArithmetic0|17 ms|\n|unordered_set|177 ms|\n|set| 199 ms|\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(\\sum_{i=0}^{m-1} r[i]-l[i]+1)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(\\max(nums)) \\to O(\\max(r[i]-l[i]+1))$$ \n# Code 23 ms Beats 97.08%\n```\n#pragma GCC optimize("O3")\nclass Solution {\npublic:\n    bool isArithmetic(vector<int>& nums, int ll, int rr){\n        int minN=*min_element(nums.begin()+ll, nums.begin()+(rr+1));\n        int maxN=*max_element(nums.begin()+ll, nums.begin()+(rr+1));\n        int diff=maxN-minN;\n        if (diff==0) return 1;\n        vector<bool> isElt(diff+1, 0);\n        #pragma unroll\n        for(int i=ll; i<=rr; i++){            \n            int x=nums[i]-minN;\n            isElt[x]=1;\n        }\n        auto [d, r]=div(diff, rr-ll);\n        if (r!=0) return 0;\n        #pragma unroll\n        for(int x=d; x<diff; x+=d)\n            if (isElt[x]==0) return 0;\n        return 1;\n    }\n    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {\n        int n=nums.size(), m=l.size();\n        vector<bool> ans(m, 0);\n        #pragma unroll\n        for(int i=0; i<m; i++)\n            ans[i]=isArithmetic(nums, l[i], r[i]);\n        return ans;\n    }\n};\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# Using isArithmetic0 function runs 17ms & beats 100%\n```\n    bool isArithmetic0(vector<int>& nums, int ll, int rr){\n        int minN=*min_element(nums.begin()+ll, nums.begin()+(rr+1));\n        int maxN=*max_element(nums.begin()+ll, nums.begin()+(rr+1));\n        int diff=maxN-minN;\n        if (diff==0) return 1;\n        auto [d, r]=div(diff, rr-ll);\n        if (r!=0) return 0;\n        vector<bool> term(rr-ll+1, 0);\n        #pragma unroll\n        for(int i=ll; i<=rr; i++){            \n            int x=nums[i]-minN;\n            if (x%d!=0) return 0;\n            int j=x/d;\n            if (term[j]) return 0;// exact once\n            else term[j]=1;\n        }\n        return 1;\n    }\n```\n# Code using revised isArithmetic0 function also runs 17ms & beats 100%\n```\nbool isArithmetic0(vector<int>& nums, int ll, int rr){\n        auto [minN, maxN]=minmax_element(nums.begin()+ll, nums.begin()+(rr+1));\n        int diff=*maxN-*minN;\n        if (diff==0 || rr-ll<2) return 1;\n        auto [d, r]=div(diff, rr-ll);\n        if (r!=0) return 0;\n        vector<bool> term(rr-ll+1, 0);\n        #pragma unroll\n        for(int i=ll; i<=rr; i++){            \n            int x=nums[i]-*minN;\n            if (x%d!=0) return 0;\n            int j=x/d;\n            if (term[j]) return 0;// exact once\n            else term[j]=1;\n        }\n        return 1;\n    }\n```\n
['Array', 'Math', 'C++']