Keep Multiplying Found Values by Two

Difficulty: Easy | Acceptance: 75.00% | Paid: No Topics: Array, Hash Table, Sorting, Simulation

You are given an array of positive integers nums and an integer original.

Find original in nums. If found, multiply original by 2 and repeat the process. Continue this process until original is no longer found in nums.

Return the final value of original.

• Examples
• Constraints
• Brute Force Simulation
• Hash Set Approach
• Sorting + Binary Search

Examples

Example 1:

Input: nums = [5,3,6,1,12], original = 3
Output: 24
Explanation: 
- 3 is found in nums. 3 is multiplied by 2 to get 6.
- 6 is found in nums. 6 is multiplied by 2 to get 12.
- 12 is found in nums. 12 is multiplied by 2 to get 24.
- 24 is not found in nums. Thus, 24 is returned.

Example 2:

Input: nums = [2,7,9], original = 4
Output: 4
Explanation: 
- 4 is not found in nums. Thus, 4 is returned.

Constraints

1 <= nums.length <= 1000
1 <= nums[i], original <= 1000

Brute Force Simulation

Intuition Repeatedly search for original in the array using linear search. If found, multiply by 2 and continue until not found.

Steps

• While original exists in nums (using linear search):
  • Multiply original by 2
• Return final original

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        while original in nums:
            original *= 2
        return original

Complexity

• Time: O(n × k) where n is array length and k is number of multiplications
• Space: O(1)
• Notes: Simple but inefficient due to repeated linear searches

Hash Set Approach

Intuition Use a hash set for O(1) lookups. Convert array to set once, then repeatedly check and multiply.

Steps

• Convert nums to a hash set
• While original exists in the set:
  • Multiply original by 2
• Return final original

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        s = set(nums)
        while original in s:
            original *= 2
        return original

Complexity

• Time: O(n + k) where n is array length and k is number of multiplications
• Space: O(n)
• Notes: Optimal time complexity with trade-off of extra space

Sorting + Binary Search

Intuition Sort the array and use binary search for each lookup. This avoids extra space but adds log factor.

Steps

• Sort nums array
• While binary search finds original in array:
  • Multiply original by 2
• Return final original

from bisect import bisect_left

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        nums.sort()
        n = len(nums)
        while True:
            idx = bisect_left(nums, original)
            if idx < n and nums[idx] == original:
                original *= 2
            else:
                break
        return original

Complexity

• Time: O(n log n + k log n) where n is array length and k is number of multiplications
• Space: O(1) or O(log n) for sorting recursion
• Notes: Good when space is constrained, but slower than hash set