We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Destroying Asteroids

Number: 2245

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an initial planet mass and a list of asteroid masses, determine if all asteroids can be destroyed. The planet can destroy an asteroid if its mass is greater than or equal to the asteroid's mass, and upon doing so, the planet's mass increases by the mass of the asteroid. You are allowed to choose any order to collide with the asteroids.

Key Insights

  • Sorting the asteroid array in increasing order maximizes the planet's mass gain early.
  • By destroying the smallest asteroids first, the planet accumulates mass and is more likely to successfully destroy larger asteroids later on.
  • The simulation terminates early if the planet cannot destroy a current asteroid.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the asteroids. Space Complexity: O(1) (ignoring the space taken by input data).

Solution

The approach is to sort the asteroids by their mass in ascending order. By doing so, we ensure that the smallest asteroids are destroyed first, which helps in increasing the planet's mass gradually. For each asteroid in the sorted list, we check if the planet's current mass is greater than or equal to the asteroid's mass:

  • If it is, the asteroid is destroyed and its mass is added to the planet's mass.
  • If it is not, then it becomes impossible to destroy this asteroid, so the function returns false. If the loop finishes successfully, then all asteroids have been destroyed and the function returns true.

Code Solutions

# Function to determine if all asteroids can be destroyed.
def can_destroy_all_asteroids(mass, asteroids):
    # Sort asteroids in non-decreasing order.
    asteroids.sort()
    # Iterate through each asteroid
    for asteroid in asteroids:
        # Check if the current planet mass can destroy the asteroid
        if mass >= asteroid:
            # Increase the planet mass by the mass of the asteroid
            mass += asteroid
        else:
            # If the asteroid cannot be destroyed, return False.
            return False
    # All asteroids have been destroyed.
    return True

# Example test
print(can_destroy_all_asteroids(10, [3,9,19,5,21]))  # Output: True
print(can_destroy_all_asteroids(5, [4,9,23,4]))        # Output: False
← Back to All Questions