Math problem O(N) solution IF given A[i] itself is arithmetic


  • 0

    Note: this is NOT a solution to the original problem, only a reduced case.

    Initially I misunderstood the problem by taking the given vector<int> A itself as an arithmetic array, which is only a reduced case of the original problem. However, I think the reduced case is still an interesting problem since it becomes a math problem with O(N) solution.

    If vector<int> A itself is an arithmetic array, the problem will have nothing to do with the values but only the indices. For edge case when vector<int> A is a constant array, obviously it has n-2 distinct sub arithmetic arrays. Now we consider the non-trivial case.

    Note that a sub arithmetic array is uniquely determined by its initial index i and common index difference d. Then we have length of longest sub arithmetic array starting from index i with common index difference d is

    • L(i, d) = [(n-1-i)/d] + 1 ("[ ]" is the floor function),

    then the count of all distinct sub arithmetic arrays is

    • Count = Σi, d (L(i, d) - 2), sum only for those L(i, d) ≥ 3.

    The range is 0 ≤ i ≤ n-1-2d, so

    • Count = Σd=1:[(n-1)/2]i=2d:n-1 ([i/d]-1)}
      = Σd=1:[(n-1)/2] { d(2+3+...+(q-1)) + q(r+1) - (n-2d) }
      = Σd=1:[(n-1)/2] { d(q+1)(q-2)/2 + q(r+1) - (n-2d) },

    where q = [(n-1)/d] and r = (n-1)%d.

        int numberOfArithmeticSlices(vector<int>& A) {
          int n = A.size(), res = 0; 
          if (n < 3) return 0; else if (A[0] == A[1]) return n - 2;
          for (int d = 1; d <= (n-1)/2; ++d) {
            int q = (n-1)/d, r = (n-1)%d;
            res += (d*(q-2)*(q+1)/2 + (r+1)*q - n + 2*d);
          }
          return res;
    
    

Log in to reply
 

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