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

Keep Multiplying Found Values by Two

Number: 2274

Difficulty: Easy

Paid? No

Companies: Amazon, Goldman Sachs

Problem Description

Given an array of integers and an integer "original", repeatedly check if "original" exists in the array. If it does, multiply it by two and continue the process. Stop when the current value is no longer found in the array, and return that final value.

Key Insights

  • Convert the array to a hash set to achieve constant time look-ups.
  • Use a while loop to repeatedly check and update the "original" value.
  • The simulation stops as soon as the value is not found in the set.
  • This approach leverages space for faster look-up time, ensuring efficiency given the problem constraints.

Space and Time Complexity

Time Complexity: O(n + k) where n is the size of the input array (to build the set) and k is the number of successful multiplicative steps. Space Complexity: O(n) for storing the hash set.

Solution

We solve the problem by first converting the input array into a hash set for O(1) average time look-ups. Then, using a while loop, we check if the current "original" value exists in the set. If it does, we double the value and repeat the check. This simulation continues until the current value is no longer present in the set. Finally, the resultant value is returned. The key trick is to use a set which optimizes the search operation, making the solution efficient.

Code Solutions

# Function to keep multiplying found values by 2
def find_final_value(nums, original):
    # Convert the list to a set for O(1) lookups
    num_set = set(nums)
    # Loop until the current value is not found in the set
    while original in num_set:
        # Multiply the current value by 2
        original *= 2
    # Return the final value after multiplication stops
    return original

# Example usage:
# nums = [5,3,6,1,12]
# original = 3
# print(find_final_value(nums, original))  # Output should be 24
← Back to All Questions