# Keep Multiplying Found Values by Two
**Difficulty:** EASY
[External](https://leetcode.com/problems/keep-multiplying-found-values-by-two)
Canonical: https://scaleengineer.com/dsa/problems/keep-multiplying-found-values-by-two
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs)
---
## Problem
You are given an array of integers `nums`. You are also given an integer `original` which is the first number that needs to be searched for in `nums`.

You then do the following steps:

1. If `original` is found in `nums`, **multiply** it by two (i.e., set `original = 2 * original`).
2. Otherwise, **stop** the process.
3. **Repeat** this process with the new number as long as you keep finding the number.

Return _the **final** value of_ `original`.

**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 obtain 6.
- 6 is found in nums. 6 is multiplied by 2 to obtain 12.
- 12 is found in nums. 12 is multiplied by 2 to obtain 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`

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. We use a loop that continues as long as we can find the current `original` value in the `nums` array. Inside the loop, we perform a linear search through the `nums` array to check for the existence of `original`.
**Time:** O(N * K), where N is the number of elements in `nums` and K is the number of times we find `original` and double it. Since K is small and logarithmically bounded by the value range, this is often acceptable but less efficient than other approaches. · **Space:** O(1), as we only use a few variables to store the state.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Inefficient due to repeated linear scans of the entire array. For each successful find, we rescan the array from the beginning.
### Explanation
Start with the given `original` value. Enter a loop that will run as long as we keep finding the number. Inside the loop, we need to determine if the current `original` exists in `nums`. We use a flag, say `found`, initialized to `false`, and a `for` loop to iterate through each element of `nums`. If an element `num` is equal to `original`, we set `found` to `true`, update `original` by multiplying it by 2, and break the inner `for` loop to restart the search with the new `original`. If the inner loop completes without finding the number (`found` remains `false`), we break the outer loop. Finally, we return the last value of `original`.

```java
class Solution {
    public int findFinalValue(int[] nums, int original) {
        boolean foundInLoop = true;
        while (foundInLoop) {
            foundInLoop = false;
            for (int num : nums) {
                if (num == original) {
                    original *= 2;
                    foundInLoop = true;
                    break; // Found the number, restart search with new original
                }
            }
        }
        return original;
    }
}
```
### Algorithm
*   Initialize a loop that continues as long as a number is found.
*   In each iteration, perform a linear scan of the `nums` array to search for the current `original`.
*   If `original` is found, double its value and continue the loop.
*   If `original` is not found after scanning the entire array, exit the loop.
*   Return the final `original` value.

## Sorting with Binary Search
To optimize the search process, we can first sort the input array `nums`. Once the array is sorted, we can use the much more efficient binary search algorithm to check for the existence of `original` in each step.
**Time:** O(N log N + K * log N). The initial sort takes O(N log N). Each of the K searches takes O(log N). The sorting step dominates the overall complexity, making it O(N log N). · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm used. `Arrays.sort` in Java for primitive types has a space complexity of O(log N) on average for its recursion stack.
**Pros:** Significantly faster than the brute-force approach for large arrays.
**Cons:** The cost of sorting the array might be unnecessary if the number of searches is very small.; It modifies the input array (if sorting in-place).
### Explanation
The core idea is to replace the O(N) linear search with an O(log N) binary search. First, sort the `nums` array in ascending order. Then, enter a loop. In each iteration, perform a binary search for the current `original` value within the sorted `nums` array. Java's `Arrays.binarySearch()` is a convenient way to do this. It returns a non-negative index if the element is found, and a negative value otherwise. If the binary search finds `original`, we double `original` and continue the loop to search for the new value. If the binary search does not find `original`, we stop the process and break the loop. The final value of `original` is the result.

```java
import java.util.Arrays;

class Solution {
    public int findFinalValue(int[] nums, int original) {
        Arrays.sort(nums);
        // Keep searching as long as original is found
        while (Arrays.binarySearch(nums, original) >= 0) {
            original *= 2;
        }
        return original;
    }
}
```
### Algorithm
*   Sort the input array `nums`.
*   Start a loop that continues as long as `original` is found in `nums`.
*   In each iteration, use binary search to check for the presence of `original`.
*   If found, update `original = original * 2`.
*   If not found, exit the loop.
*   Return the final `original` value.

## Optimized Search with a Hash Set
This is the most efficient approach. We can trade space for time by pre-processing the `nums` array and storing all its unique elements into a hash set. A hash set provides, on average, constant time O(1) for lookups (checking for the existence of an element).
**Time:** O(N + K). It takes O(N) to build the hash set. The `while` loop runs K times, and each check is O(1) on average. This gives a total time complexity that is linear with respect to the size of the input array, effectively O(N). · **Space:** O(N) in the worst case, where all elements in `nums` are unique and are stored in the hash set.
**Pros:** The fastest approach asymptotically.; The lookup time is constant on average, making the simulation part very quick.
**Cons:** Uses extra space proportional to the number of unique elements in the input array.
### Explanation
First, create a `HashSet` of integers. Iterate through the `nums` array once and add every element to the hash set. This step effectively creates a quick-lookup table for all numbers present in `nums`. After building the set, start with the initial `original` value. Enter a `while` loop that continues as long as the hash set contains the current `original` value. The `set.contains()` method is an O(1) average time operation. Inside the loop, if `original` is found, simply double its value: `original *= 2`. The loop terminates when `set.contains(original)` returns `false`. The final value of `original` is the answer.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findFinalValue(int[] nums, int original) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        while (numSet.contains(original)) {
            original *= 2;
        }
        
        return original;
    }
}
```
### Algorithm
*   Create a hash set and populate it with all elements from the `nums` array.
*   Start a loop that checks if the current `original` is in the hash set.
*   The `contains` operation on a hash set is O(1) on average.
*   If `original` is in the set, double its value.
*   Repeat until `original` is not found in the set.
*   Return the final `original` value.

# Solutions
### Java

```java
class Solution {
public
  int findFinalValue(int[] nums, int original) {
    Set<Integer> s = new HashSet<>();
    for (int num : nums) {
      s.add(num);
    }
    while (s.contains(original)) {
      original <<= 1;
    }
    return original;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findFinalValue(vector<int> &nums, int original) {
    unordered_set<int> s;
    for (int num : nums)
      s.insert(num);
    while (s.count(original))
      original <<= 1;
    return original;
  }
};

```

### Python

```python
class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int: s = set(nums) while original in s: original <<= 1 return original

```