Leetcode 2154. Keep Multiplying Found Values by Two

Let's understand what we're being asked to do. We have an array like [1, 3, 6, 9, 9, 9, 9] and a starting integer like 3. We need to repeatedly double the value while it exists in the array, then return the first value that doesn't exist.

Tracing through: Start with 3. Is 3 in the array? Yes! Double it to 6. Is 6 in the array? Yes! Double it to 12. Is 12 in the array? No! Return 12.

Important constraint: We keep doubling only while the current value exists in the array. The moment we hit a value that's not in the array, we stop and return it.

Edge cases to consider: What if the starting integer itself is not in the array? (return it immediately). What if we keep doubling and eventually overflow? What if the array is empty?

The straightforward approach is to repeatedly check if the current value exists by scanning through the entire array each time. Start with the original value, and for each iteration, loop through all array elements to check for membership. If found, double the value and repeat; if not found, return the current value. This approach is simple but inefficient because we scan the array multiple times.

def find_missing_doubled(original, arr):
    """
    Repeatedly double the value while it exists in the array.
    Return the first value that is not found.
    Brute force: scan entire array for each check.
    """
    current = original
    
    # Keep doubling while current value exists in array
    while True:
        # Scan entire array to check if current exists (inefficient)
        found = False
        for num in arr:
            if num == current:
                found = True
                break
        
        # If not found, return current value
        if not found:
            return current
        
        # Double the value and continue
        current = current * 2

The core operation is checking membership: does this value exist in the array? We'll be doing this check repeatedly in a loop.

If we scan through the entire array for each check, we'd waste time. But if we preprocess the array into a structure that supports instant lookups, each doubling step becomes very fast.

By converting the array into a set (hash set), we transform membership checking from O(n) per check to O(1) per check.

Since we might double many times (especially if the array contains large powers of 2), this optimization makes a huge difference. The difference between scanning 1000 elements repeatedly vs. instant hash lookups!

Think about looking up a word's definition. You could scan through a dictionary page by page (slow), or you could use an index that tells you exactly which page to turn to (instant).

A hash set is like that index - it organizes data so you can instantly check 'is this value present?' without scanning. For this problem, we build the index once (convert array to set), then use it for all our doubling checks.

The optimal approach uses a hash set for O(1) membership checking. First, convert the array into a hash set in a single pass. Then, starting with the original value, repeatedly check if the current value exists in the set (O(1) lookup). If it exists, double it and continue; if not, return the current value. This eliminates redundant array scans and makes each membership check instant.

def find_final_value(nums, original):
    """
    Repeatedly double the value while it exists in the array.
    Uses hash set for O(1) membership checking.
    """
    # Convert array to hash set for O(1) lookup
    num_set = set(nums)
    
    # Start with the original value
    current = original
    
    # Keep doubling while current value exists in set
    while current in num_set:
        current = current * 2
    
    # Return first value not found in set
    return current

• Hash set for O(1) membership checking: When a problem requires repeatedly checking if values exist in a collection, convert the array to a hash set immediately - this transforms O(n) linear searches into O(1) lookups, which is critical when performing multiple existence checks in a loop.
• Iterative doubling with existence validation: The pattern of "keep transforming a value while it meets a condition" is best implemented with a while loop that checks set membership before each iteration - this avoids recursion overhead and makes the termination condition explicit and testable.
• Preprocessing vs. repeated scanning trade-off: Spending O(n) time upfront to build a hash set pays off when you'll perform multiple lookups - even if you only check a few values, the constant-time lookup guarantee is worth the initial preprocessing cost compared to scanning the array each time.
• Integer overflow awareness: When repeatedly multiplying or doubling integers, always consider overflow boundaries - in this problem, values are constrained (typically ≤ 1000), but in general, doubling operations can quickly exceed integer limits, requiring long/BigInteger types or early termination checks.
• Set-based simulation pattern: This "simulate a process until a condition fails" approach applies broadly to problems involving state transitions with membership validation - think game states, value transformations, or sequence generation where you need to check if the next state is valid/visited.
• Space-time tradeoff for lookup optimization: Using O(n) extra space for a hash set to achieve O(1) lookups instead of O(n) array scans demonstrates the classic space-time tradeoff - recognize when spending memory to store preprocessed data dramatically improves algorithmic efficiency, especially in lookup-heavy operations.