Kotlin | Sliding Window Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe smallest subsequence of a or is the smallest possible one, where all bits that came
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe smallest subsequence of a or is the smallest possible one, where all bits that came before is at least included once. Since there are only 32 Bits in an Integer it can be calculated in linear time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThis solution uses the slinding window technique. The bits are counted in an array dp. If a value in the array is zero, that means this bit wasn\'t used before. The algorithm goes from right to left in order to store the numbers.\n\nA number can be removed from the subsequence if all bits of the number are at least two times in the array. This can be used to check if the number of the outer right can be removed. If it is the case then remove the number and repeat the process. The smallest subsequence is the difference of the position of the number and the position of the right most number plus one. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```\nclass Solution {\n    fun addElement(num:Int, dp:IntArray){\n        for(i:Int in 0..31) if((1 shl i) and num > 0) dp[i] += 1\n    }\n    \n    fun removeElement(num:Int, dp:IntArray): Boolean {\n        for(i:Int in 0..31) if(dp[i] == 1 && (1 shl i) and num > 0) return false\n        for(i:Int in 0..31) if((1 shl i) and num > 0) dp[i] -= 1\n\n        return true\n    }\n\n    fun smallestSubarrays(nums: IntArray): IntArray {\n        val n:Int = nums.size\n        val dp:IntArray = IntArray(32){0}\n        var r:Int = n-1\n\n        val sol:IntArray = IntArray(n){0}\n\n        for(i:Int in n-1 downTo 0){\n            addElement(nums[i], dp)\n\n            while(i<r && removeElement(nums[r], dp)) r--\n            \n            sol[i] = r-i+1\n        }\n\n        return sol\n    }\n}\n```
['Kotlin']