🚀🚀🚀 magic of buckets || O(n) time || Bucket Sort
Intuition\n Describe your first thoughts on how to solve this problem. \nSort asteroids to bucket[i] where i is the minimum integer satisfying\n asteroid <= mas
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSort `asteroids` to `bucket[i]` where `i` is the minimum integer satisfying\n `asteroid <= mass * 2^i`.\n\nAnd then for each bucket in order, we can absorb all or nothing.\n(can absorb one `x` -> mass at least `2x` -> can absorb all)\n\nIf `i >= n` we early stop to ensure that the time complexity is linear.\n(You need at least `1, 2, 4, 8, 16, 32, ...` to return `true` so `i < n`.)\n\n# Complexity\n- Time complexity: $O(n)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```typescript []\nfunction asteroidsDestroyed(\n  mass: number,\n  asteroids: number[]\n): boolean {\n  const n = asteroids.length;\n\n  const bucket = asteroids.map(() => [] as number[]);\n  for (const v of asteroids) {\n    const power = Math.log2(v / mass);\n    const i = power < 0 ? 0 : Math.ceil(power);\n    if (i >= n) return false;\n    bucket[i].push(v);\n  }\n\n  return bucket.every((arr) => {\n    if (arr.length === 0) return true;\n    if (mass < Math.min(...arr)) return false;\n    mass += sum(arr);\n    return true;\n  });\n}\n\nfunction sum(arr: number[]) {\n  return arr.reduce((a, b) => a + b);\n}\n\n```\n```python []\nclass Solution:\n    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:\n        n = len(asteroids)\n\n        bucket = [[] for _ in range(n)]\n        for v in asteroids:\n            power = log2(v / mass)\n            i = 0 if power < 0 else ceil(power)\n            if i >= n:\n                return False\n            bucket[i].append(v)\n\n        for arr in bucket:\n            if arr and mass < min(arr):\n                return False\n            mass += sum(arr)\n        \n        return True\n\n```
['Divide and Conquer', 'Bucket Sort', 'TypeScript', 'Python3']