LeetCode Problem 2154

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting, Simulation

Solution

LeetCode 2154 - Keep Multiplying Found Values by Two

Problem Understanding

This problem asks us to repeatedly search for a value inside an integer array and double that value whenever it is found. We begin with the integer original. If that number exists anywhere in the array nums, we multiply it by two and repeat the process using the new value. The process stops as soon as the current value is no longer present in the array.

The input consists of two parts. The first input, nums, is an array of integers. The second input, original, is the starting number we repeatedly search for. The expected output is the final value of original after all valid doublings have been performed.

For example, if original = 3 and the array contains 3, then we update the value to 6. If the array also contains 6, we update again to 12. If the array contains 12, we continue to 24. The process stops once the current value is missing from the array.

The constraints are relatively small:

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

These limits tell us that even straightforward solutions will work efficiently. However, the problem is still useful for practicing lookup optimization and simulation techniques.

A few important observations emerge immediately:

• The array may contain duplicates, but duplicates do not change the behavior because we only care whether a value exists at least once.
• The doubling process may continue several times in a row if the array contains a chain such as 2 -> 4 -> 8 -> 16.
• The value of original can grow beyond 1000 during execution, even though the initial inputs are bounded.
• If the starting value does not exist in the array, we immediately return the original value unchanged.

Approaches

Brute Force Approach

The most direct solution is to repeatedly scan the entire array to check whether the current value of original exists.

The algorithm works like this:

1. Search the array linearly for original.
2. If found, double original.
3. Repeat the scan with the new value.
4. Stop once the value is not found.

This approach is correct because each iteration exactly follows the rules given in the problem statement. However, every lookup requires traversing the entire array.

In the worst case, if the doubling chain is long, we repeatedly perform linear scans. Although the constraints are small enough that this solution still passes, it is inefficient compared to a hash-based lookup approach.

Optimal Approach

The key observation is that we only need fast membership checks. We do not care about element order, frequencies, or positions inside the array. A hash set is therefore the ideal data structure.

By storing all numbers from nums in a set, we can check whether a value exists in average O(1) time instead of O(n) time.

The improved algorithm becomes:

1. Convert nums into a hash set.
2. While original exists in the set:

• Double it.

3. Return the final value.

This works efficiently because every lookup is constant time on average.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × k)	O(1)	Repeatedly scans the array for each doubled value
Optimal	O(n + k)	O(n)	Uses a hash set for constant time lookups

Here, n is the length of the array and k is the number of successful doublings.

Algorithm Walkthrough

1. Create a hash set from the input array.

We store every number from nums inside a set because sets provide very fast membership testing. Instead of scanning the array repeatedly, we can instantly determine whether a value exists. 2. Start with the given value of original.

This value represents the current number we are searching for. 3. Check whether the current value exists in the set.

If it exists, the problem instructs us to multiply it by two. We then continue searching using the updated value. 4. Repeat the process until the value is missing.

As soon as the current value is not found in the set, the process terminates because the problem statement explicitly says to stop. 5. Return the final value.

This value represents the first number in the doubling sequence that does not appear in the array.

Why it works

The algorithm maintains the invariant that original always represents the current value that must be checked according to the problem rules. At each step, if the value exists in the array, we double it exactly once and continue. If it does not exist, we stop immediately. Since the algorithm precisely mirrors the required process and uses accurate membership checks through the set, the returned value is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        values = set(nums)

        while original in values:
            original *= 2

        return original

The implementation begins by converting nums into a set called values. This preprocessing step allows fast existence checks throughout the algorithm.

The while loop repeatedly checks whether the current value of original exists inside the set. If it does, we double the value using original *= 2.

Once the value no longer exists in the set, the loop terminates and the function returns the final result.

The implementation directly follows the algorithm walkthrough and remains concise because the problem logic itself is straightforward.

Go Solution

func findFinalValue(nums []int, original int) int {
    values := make(map[int]bool)

    for _, num := range nums {
        values[num] = true
    }

    for values[original] {
        original *= 2
    }

    return original
}

The Go implementation uses a map with boolean values to simulate a hash set because Go does not provide a built in set type.

The map stores each number from nums as a key. Membership checks are then performed with values[original].

Unlike Python, Go requires explicit map creation with make. Otherwise, the overall logic is identical between the two solutions.

Integer overflow is not a concern here because the constraints are small and the doubling chain is limited by the available array values.

Worked Examples

Example 1

Input:

nums = [5,3,6,1,12]
original = 3

First, we create the set:

{1, 3, 5, 6, 12}

Now we repeatedly check and double:

Step	Current original	Exists in set?	Action
1	3	Yes	Double to 6
2	6	Yes	Double to 12
3	12	Yes	Double to 24
4	24	No	Stop

Final answer:

24

Example 2

Input:

nums = [2,7,9]
original = 4

Set contents:

{2, 7, 9}

Now perform the checks:

Step	Current original	Exists in set?	Action
1	4	No	Stop

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + k)	Building the set takes O(n), each doubling lookup takes O(1) on average
Space	O(n)	The hash set stores all array elements

The dominant preprocessing cost comes from inserting all array values into the set. After that, each lookup and doubling operation is constant time on average. The variable k represents the number of successful doublings before termination.

Test Cases

sol = Solution()

# Provided example, multiple doublings
assert sol.findFinalValue([5, 3, 6, 1, 12], 3) == 24

# Provided example, original not present
assert sol.findFinalValue([2, 7, 9], 4) == 4

# Single element equal to original
assert sol.findFinalValue([1], 1) == 2

# Duplicate values should not affect behavior
assert sol.findFinalValue([2, 2, 2], 2) == 4

# Long doubling chain
assert sol.findFinalValue([2, 4, 8, 16, 32], 2) == 64

# Original missing immediately
assert sol.findFinalValue([10, 20, 30], 5) == 5

# Chain interrupted midway
assert sol.findFinalValue([3, 6, 24], 3) == 12

# Large values near constraints
assert sol.findFinalValue([1000], 1000) == 2000

# Unordered input
assert sol.findFinalValue([16, 2, 8, 4], 2) == 32

# Minimum constraints
assert sol.findFinalValue([1], 2) == 2

Test	Why
[5,3,6,1,12], 3	Validates repeated doubling
[2,7,9], 4	Validates immediate termination
[1], 1	Tests smallest valid doubling chain
[2,2,2], 2	Ensures duplicates do not matter
[2,4,8,16,32], 2	Tests long continuous chain
[10,20,30], 5	Tests missing initial value
[3,6,24], 3	Tests interrupted sequence
[1000], 1000	Tests upper constraint values
[16,2,8,4], 2	Verifies ordering is irrelevant
[1], 2	Tests minimum array size without match

Edge Cases

One important edge case occurs when the initial value of original does not exist in the array at all. A careless implementation might still attempt unnecessary processing or accidentally modify the value. The current implementation handles this naturally because the while loop condition immediately fails and the original value is returned unchanged.

Another important case involves duplicate numbers in the array. For example, nums = [2,2,2]. The problem only asks whether a number exists, not how many times it appears. A naive implementation that tracks frequencies incorrectly could overcomplicate the logic. Using a set avoids this issue because duplicates collapse into a single entry automatically.

A third edge case is a long doubling chain such as [2,4,8,16,32]. An inefficient implementation that repeatedly scans the array could perform unnecessary work many times. The hash set solution handles this efficiently because every lookup remains constant time regardless of chain length.

A final subtle edge case is when the doubled value exceeds the original input constraints. For example, starting with 1000 may produce 2000. The implementation handles this correctly because the algorithm imposes no restriction on the final value, and both Python and Go can safely store integers of this size.