O(n) original algorithm || 10x faster than using sort || Beats 100% in Rust
Intuition\n\nFor an asteroid to combine, it has to be smaller than the planet, hence, your new planet mass will at least be 2 * asteroid.\nUsing this fact, you 
# Intuition\n\nFor an asteroid to combine, it has to be smaller than the planet, hence, your new planet mass will at least be 2 * asteroid.\nUsing this fact, you can create groups of asteroids in a way that if the smallest is combined, all the others will follow. And you can represent these groups by an interval.\n\n# Approach\n\nThe start of the interval is the smallest asteroid and the end of it is the smallest reachable weight, which equals to the smallest asteroid + the sum of all the asteroids of the group.\nSince a group cover at least a power of two (the smallest range is (x, 2 * x)), there are a maximum of log2(max_reachable_weight) ranges; which we can consider O(1).\nAnd as adding a new asteroids and checking at the end if the planet will collect all the asteroids is O(1), in the end we reach O(n) complexity.\n\nI also naively tried binary_search to find the first larger interval but there were too few intervals to make it worthwhile. \n\nI did some benchmarks, I rarely reached more than 5 ranges at the same times on random inputs (vec of length (0..10_000_000) containing i32 in (0..2^31 - 1)). It would be interesting to explore the behavior on more input variety. In average, this version was 10 times faster than the version using sort.\n\n\n![image.png](https://assets.leetcode.com/users/images/9674eaa4-60e2-4542-89cf-afc88b71da1f_1710346091.8435764.png)\n\nHere is the log log graph:\n![image.png](https://assets.leetcode.com/users/images/b828fbe7-ab3e-43f9-a2ec-cd7aad603b8f_1710346248.0718603.png)\nWe can see an average 10x performance difference on randomized inputs when the input size is greater than 100 - 1000 elements.\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nimpl Solution {\n    pub fn asteroids_destroyed(mass: i32, mut asteroids: Vec<i32>) -> bool {\n        let mut ranges = Vec::with_capacity(100);\n        let mut last_ranges = Vec::with_capacity(100);\n        last_ranges.push((0, mass as u64));\n        for asteroid in asteroids.into_iter().map(|x| x as u64) {\n            // let first_greater = last_ranges.iter().position(|&(_, high)| asteroid <= high);\n            let mut first_greater = None;\n            for (curr_idx, &(low, high)) in last_ranges.iter().enumerate() {\n                if asteroid <= high {\n                    first_greater = Some(curr_idx);\n                    break;\n                }\n                ranges.push((low, high));\n            }\n\n            if let Some(idx) = first_greater {\n                let fold_result = last_ranges[idx..].iter().enumerate().try_fold(\n                    (asteroid, 2 * asteroid),\n                    |(curr_low, curr_high), (idx, &(low, high))| {\n                        if low <= curr_low && curr_low <= high {\n                            Ok((low, curr_high - curr_low + high))\n                        } else if low <= curr_high && curr_high <= high {\n                            Ok((curr_low, high - low + curr_high))\n                        } else {\n                            Err((idx, (curr_low, curr_high)))\n                        }\n                    },\n                );\n                match fold_result {\n                    Ok(range) => ranges.push(range),\n                    Err((offset, range)) => {\n                        ranges.push(range);\n                        ranges.extend(&last_ranges[idx + offset..]);\n                    }\n                }\n            } else {\n                ranges.push((asteroid, 2 * asteroid));\n            }\n            last_ranges.clear();\n            std::mem::swap(&mut ranges, &mut last_ranges);\n        }\n        last_ranges.len() == 1\n    }\n}\n        \n```\n\n-----------\n\nSame for C++, it is a direct translation. Please, feel free to give advice on the C++ version, I have very little experience.\n\n```\n\nclass Solution {\npublic:\n    bool asteroidsDestroyed(int mass, std::vector<int>& asteroids) {\n        std::vector<std::pair<unsigned long long, unsigned long long>> ranges;\n        std::vector<std::pair<unsigned long long, unsigned long long>> last_ranges;\n        last_ranges.push_back(std::make_pair(0, static_cast<unsigned long long>(mass)));\n        for (auto asteroid : asteroids) {\n            unsigned long long asteroid_ull = static_cast<unsigned long long>(asteroid);\n            int i;\n            for (i = 0; i < last_ranges.size(); i++) {\n                auto range = last_ranges[i];\n                if (asteroid_ull <= range.second) {\n                    break;\n                }\n                ranges.push_back(range);\n            }\n            if (i < last_ranges.size()) {\n                std::pair<unsigned long long, unsigned long long> fold_result = std::make_pair(asteroid_ull, 2 * asteroid_ull);\n                for (; i < last_ranges.size(); i++) {\n                    auto range = last_ranges[i];\n                    if (range.first <= fold_result.first && fold_result.first <= range.second) {\n                        fold_result = std::make_pair(range.first, fold_result.second - fold_result.first + range.second);\n                    } else if (range.first <= fold_result.second && fold_result.second <= range.second) {\n                        fold_result = std::make_pair(fold_result.first, range.second - range.first + fold_result.second);\n                    } else {\n                        break;\n                    }\n                }\n                ranges.push_back(fold_result);\n\n                for (; i < last_ranges.size(); i++) {\n                    ranges.push_back(last_ranges[i]);\n                }\n\n            } else {\n                ranges.push_back(std::make_pair(asteroid_ull, 2 * asteroid_ull));\n            }\n            last_ranges.clear();\n            std::swap(ranges, last_ranges);\n        }\n        return last_ranges.size() == 1;\n    }\n};\n```
['Math', 'Brainteaser', 'C++', 'Rust']