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 _thefinal value of _original.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4

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

Solution

Method 1 – Hash Set Lookup

Intuition

To efficiently check if a value exists in the array, use a hash set. Keep multiplying the value by two as long as it is found in the set.

Approach

  1. Add all numbers in nums to a hash set for O(1) lookup.
  2. While original is in the set, multiply it by two.
  3. Return the final value of original.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    int findFinalValue(vector<int>& nums, int original) {
        unordered_set<int> s(nums.begin(), nums.end());
        while (s.count(original)) original *= 2;
        return original;
    }
};
1
2
3
4
5
6

func findFinalValue(nums []int, original int) int {
    s := map[int]bool{}
    for _, n := range nums { s[n] = true }
    for s[original] { original *= 2 }
    return original
}
1
2
3
4
5
6
7
8

class Solution {
    public int findFinalValue(int[] nums, int original) {
        Set<Integer> s = new HashSet<>();
        for (int n : nums) s.add(n);
        while (s.contains(original)) original *= 2;
        return original;
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun findFinalValue(nums: IntArray, original: Int): Int {
        val s = nums.toSet()
        var ans = original
        while (ans in s) ans *= 2
        return ans
    }
}
1
2
3
4
5
6

class Solution:
    def findFinalValue(self, nums: list[int], original: int) -> int:
        s = set(nums)
        while original in s:
            original *= 2
        return original
1
2
3
4
5
6
7
8
9

use std::collections::HashSet;
impl Solution {
    pub fn find_final_value(nums: Vec<i32>, original: i32) -> i32 {
        let s: HashSet<_> = nums.into_iter().collect();
        let mut ans = original;
        while s.contains(&ans) { ans *= 2; }
        ans
    }
}
1
2
3
4
5
6
7

class Solution {
    findFinalValue(nums: number[], original: number): number {
        const s = new Set(nums);
        while (s.has(original)) original *= 2;
        return original;
    }
}

Complexity

  • ⏰ Time complexity: O(n + logM), where n is the length of nums and M is the maximum value reached. Building the set is O(n), and each multiply/check is O(1).
  • 🧺 Space complexity: O(n), for the hash set.