🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n\n---\n\n# Intuition\nThe task requires finding the longest sequence of numbers where each number is the square of the previous one. By counting such sequen
![image.png](https://assets.leetcode.com/users/images/1686f33e-5083-4b1b-a6a1-8d50d5b10e14_1730102608.2945678.png)\n\n\n---\n\n# Intuition\nThe task requires finding the longest sequence of numbers where each number is the square of the previous one. By counting such sequences for each number in the sorted list, we aim to identify the longest possible streak.\n\n# Approach\n1. **Sort the List**: Sorting `nums` allows binary search to efficiently check for subsequent square values.\n2. **Count Sequence for Each Number**: For each `n` in `nums`, call `getCounts` to calculate the streak length, squaring each time until the squared value is not found in the list.\n3. **Binary Search**: `binarySearch` locates target values within `nums`, optimizing search time with `O(log n)`.\n4. **Result**: Return the maximum count for all numbers or `-1` if no streak exceeds one element.\n\n# Complexity\n- **Time Complexity**: \\(O(n \\log n + n \\log m)\\), where \\(n\\) is the number of elements in `nums` and \\(m\\) is the number of streak elements for each number.\n- **Space Complexity**: \\(O(1)\\), no additional space is used apart from counters.\n\n---\n\n# Code\n\n\n```dart []\nclass Solution {\n  int longestSquareStreak(List<int> nums) {\n    nums.sort();\n    int ans = -1;\n    for (int n in nums) {\n      int counts = getCounts(n, nums);\n      if (counts > 1) {\n        ans = max(ans, counts);\n      }\n    }\n    return ans;\n  }\n\n  int getCounts(int target, List<int> arrays) {\n    int found = 1;\n    target = target * target;\n    while (binarySearch(target, arrays)) {\n      found++;\n      target = target * target;\n    }\n    return found;\n  }\n\n  bool binarySearch(int target, List<int> arrays) {\n    int start = 0;\n    int end = arrays.length - 1;\n    while (start <= end) {\n      int mid = start + (end - start) ~/ 2;\n      if (arrays[mid] == target) return true;\n      if (arrays[mid] > target)\n        end = mid - 1;\n      else\n        start = mid + 1;\n    }\n    return false;\n  }\n}\n```\n\n\n```java []\nimport java.util.Arrays;\n\nclass Solution {\n    public int longestSquareStreak(int[] nums) {\n        Arrays.sort(nums);\n        int ans = -1;\n        for (int n : nums) {\n            int counts = getCounts(n, nums);\n            if (counts > 1) {\n                ans = Math.max(ans, counts);\n            }\n        }\n        return ans;\n    }\n\n    private int getCounts(int target, int[] arrays) {\n        int found = 1;\n        target *= target;\n        while (binarySearch(target, arrays)) {\n            found++;\n            target *= target;\n        }\n        return found;\n    }\n\n    private boolean binarySearch(int target, int[] arrays) {\n        int start = 0, end = arrays.length - 1;\n        while (start <= end) {\n            int mid = start + (end - start) / 2;\n            if (arrays[mid] == target) return true;\n            if (arrays[mid] > target) end = mid - 1;\n            else start = mid + 1;\n        }\n        return false;\n    }\n}\n```\n\n\n```javascript []\nfunction longestSquareStreak(nums) {\n    nums.sort((a, b) => a - b);\n    let ans = -1;\n    for (let n of nums) {\n        let counts = getCounts(n, nums);\n        if (counts > 1) ans = Math.max(ans, counts);\n    }\n    return ans;\n}\n\nfunction getCounts(target, arrays) {\n    let found = 1;\n    target = target * target;\n    while (binarySearch(target, arrays)) {\n        found++;\n        target = target * target;\n    }\n    return found;\n}\n\nfunction binarySearch(target, arrays) {\n    let start = 0, end = arrays.length - 1;\n    while (start <= end) {\n        let mid = Math.floor((start + end) / 2);\n        if (arrays[mid] === target) return true;\n        if (arrays[mid] > target) end = mid - 1;\n        else start = mid + 1;\n    }\n    return false;\n}\n```\n\n```python []\nfrom typing import List\n\nclass Solution:\n    def longestSquareStreak(self, nums: List[int]) -> int:\n        nums.sort()\n        ans = -1\n        for n in nums:\n            counts = self.getCounts(n, nums)\n            if counts > 1:\n                ans = max(ans, counts)\n        return ans\n\n    def getCounts(self, target: int, arrays: List[int]) -> int:\n        found = 1\n        target *= target\n        while self.binarySearch(target, arrays):\n            found += 1\n            target *= target\n        return found\n\n    def binarySearch(self, target: int, arrays: List[int]) -> bool:\n        start, end = 0, len(arrays) - 1\n        while start <= end:\n            mid = (start + end) // 2\n            if arrays[mid] == target:\n                return True\n            elif arrays[mid] > target:\n                end = mid - 1\n            else:\n                start = mid + 1\n        return False\n```\n\n\n```cpp []\n#include <vector>\n#include <algorithm>\n\nclass Solution {\npublic:\n    int longestSquareStreak(std::vector<int>& nums) {\n        std::sort(nums.begin(), nums.end());\n        int ans = -1;\n        for (int n : nums) {\n            int counts = getCounts(n, nums);\n            if (counts > 1) {\n                ans = std::max(ans, counts);\n            }\n        }\n        return ans;\n    }\n\nprivate:\n    int getCounts(int target, const std::vector<int>& arrays) {\n        int found = 1;\n        target *= target;\n        while (binarySearch(target, arrays)) {\n            found++;\n            target *= target;\n        }\n        return found;\n    }\n\n    bool binarySearch(int target, const std::vector<int>& arrays) {\n        int start = 0, end = arrays.size() - 1;\n        while (start <= end) {\n            int mid = start + (end - start) / 2;\n            if (arrays[mid] == target) return true;\n            if (arrays[mid] > target) end = mid - 1;\n            else start = mid + 1;\n        }\n        return false;\n    }\n};\n```\n\n\n```go []\nimport "sort"\n\nfunc longestSquareStreak(nums []int) int {\n    sort.Ints(nums)\n    ans := -1\n    for _, n := range nums {\n        counts := getCounts(n, nums)\n        if counts > 1 {\n            if counts > ans {\n                ans = counts\n            }\n        }\n    }\n    return ans\n}\n\nfunc getCounts(target int, arrays []int) int {\n    found := 1\n    target = target * target\n    for binarySearch(target, arrays) {\n        found++\n        target = target * target\n    }\n    return found\n}\n\nfunc binarySearch(target int, arrays []int) bool {\n    start, end := 0, len(arrays)-1\n    for start <= end {\n        mid := start + (end - start) / 2\n        if arrays[mid] == target {\n            return true\n        }\n        if arrays[mid] > target {\n            end = mid - 1\n        } else {\n            start = mid + 1\n        }\n    }\n    return false\n}\n```\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}
['Array', 'C', 'Sorting', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']