[Java/C++/Python] Bit Solution with Explanation 🔥
Intuition\nAssume the array has only 0 and 1.\nThen the question changes:\nIf A[i] = 1, shortest array is [A[i]], length is 1.\nIf A[i] = 0, we need to find the
# **Intuition**\nAssume the array has only 0 and 1.\nThen the question changes:\nIf `A[i] = 1`, shortest array is `[A[i]]`, length is 1.\nIf `A[i] = 0`, we need to find the index `j` of next `1`,\nthen `j - i + 1` is the length of shortest subarray.\nIf no next 1, 1 is the length\n\nTo solve this problem,\nwe can iterate the array reversely\nand keep the index `j` of last time we saw 1.\n`res[i] = max(1, last - i + 1)`\n<br>\n\n# **Explanation**\nFor `0 <= A[i] <= 10^9`,\nwe simply do the above process for each bit.\n`res[i] = max(1, max(last) - i + 1)`\n<br>\n\n# **Complexity**\nTime `O(30n)`\nSpace `O(30)`\n<br>\n\n**Java**\n```java\n    public int[] smallestSubarrays(int[] A) {\n        int n = A.length, last[] = new int[30], res[] = new int[n];\n        for (int i = n - 1; i >= 0; --i) {\n            res[i] = 1;\n            for (int j = 0; j < 30; ++j) {\n                if ((A[i] & (1 << j)) > 0)\n                    last[j] = i;\n                res[i] = Math.max(res[i], last[j] - i + 1);\n            }\n        }\n        return res;\n    }\n```\n\n**C++**\n```cpp\n    vector<int> smallestSubarrays(vector<int>& A) {\n        int last[30] = {}, n = A.size();\n        vector<int> res(n, 1);\n        for (int i = n - 1; i >= 0; --i) {\n            for (int j = 0; j < 30; ++j) {\n                if (A[i] & (1 << j))\n                    last[j] = i;\n                res[i] = max(res[i], last[j] - i + 1);\n            }\n        }\n        return res;\n    }\n```\n\n**Python**\n```py\n    def smallestSubarrays(self, A):\n        last = [0] * 32\n        n = len(A)\n        res = [0] * n\n        for i in range(n - 1, -1, -1):\n            for j in range(32):\n                if A[i] & (1 << j):\n                    last[j] = i\n            res[i] = max(1, max(last) - i + 1)\n        return res\n```\n
['C', 'Python', 'Java']