aboutsummaryrefslogtreecommitdiff
path: root/arithmetic_sequence.py
blob: e8c12304ca01fd6d3f3a59cae6ca5c6f641a5145 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# 1630. Arithmetic Subarrays

"""
a sequence of numbers is called arithmetic if it consists of at least two
elements and the difference between every two consecutive elements is the
same. more formally, a sequence 's' is arithmetic if and only if 's[i + 1] -
s[i] == s[1] - s[0]' for all valid 'i'. you are given an array of 'n'
integers 'nums' and two arrays of 'm' integers each 'l' and 'r' respectively
representingthe 'm' range queries where the i'th query isthe range '[l[i],
r[i]]'. all the arrays are 0-indexed. return a list of boolean elements 'ans'
where 'ans[i]' is true if the subarray 'nums[l[i]], nums[l[i] + 1], ...,
nums[r[i]]' can be rearrange to form an arithmetic sequence and false
otherwise
"""


class Solution(object):
    def is_arithmetic(self, nums, l, r):
        max_val, min_val = float("-inf"), float("inf")
        for i in range(l, r + 1):
            max_val = max(nums[i], max_val)
            min_val = min(nums[i], min_val)
        length = r - l + 1
        if (max_val - min_val) % (length - 1) != 0:
            return False
        diff = (max_val - min_val) // (length - 1)
        if diff == 0:
            return True
        visited = [False] * length
        for i in range(l, r + 1):
            val = nums[i]
            if (val - min_val) % diff != 0:
                return False
            else:
                pos = (val - min_val) // diff
                if visited[pos]:
                    return False
                visited[pos] = True
        return True

    def checkArithmeticSubarrays(self, nums, l, r):
        """
        :type nums: List[int]
        :type l: List[int]
        :type r: List[int]
        :rtype: List[bool]
        """
        ans = []
        for i in range(len(l)):
            ans.append(self.is_arithmetic(nums, l[i], r[i]))
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.checkArithmeticSubarrays(nums=[4, 6, 5, 9, 3, 7], l=[0, 0, 2], r=[2, 3, 5])
    )
    print(
        obj.checkArithmeticSubarrays(
            nums=[-12, -9, -3, -12, -6, 15, 20, -25, -20, -15, -10],
            l=[0, 1, 6, 4, 8, 7],
            r=[4, 4, 9, 7, 9, 10],
        )
    )