Keep Multiplying Found Values by Two
Problem
You are given an array of integers nums and a starting integer original. Repeatedly check whether original appears in nums: if it does, replace original with original × 2 and check again; if it does not, stop. Return the final value of original once it can no longer be found in nums.
nums = [5, 3, 6, 1, 12], original = 324def find_final_value(nums, original):
seen = set(nums)
while original in seen:
original *= 2
return originalfunction findFinalValue(nums, original) {
const seen = new Set(nums);
while (seen.has(original)) {
original *= 2;
}
return original;
}class Solution {
public int findFinalValue(int[] nums, int original) {
Set<Integer> seen = new HashSet<>();
for (int x : nums) seen.add(x);
while (seen.contains(original)) {
original *= 2;
}
return original;
}
}int findFinalValue(vector<int>& nums, int original) {
unordered_set<int> seen(nums.begin(), nums.end());
while (seen.count(original)) {
original *= 2;
}
return original;
}Explanation
The task asks us to chase a value through the array: start at original, and every time that value is present we double it and look again. Doubling only stops once the current value is missing from nums.
A naive approach would re-scan the whole array on every check, which is O(n) per lookup. Instead, we drop all of nums into a hash set once. After that, asking "is this value present?" takes O(1) on average, so each doubling step is cheap.
The loop is short: while the set contains the current value, multiply it by two. Because every step at least doubles the value, it grows past the largest element of nums very quickly — after at most about log₂(max) doublings the value escapes the set and the loop ends.
Walking through the default example nums = [5, 3, 6, 1, 12], original = 3: the set is {1, 3, 5, 6, 12}. 3 is in the set → become 6; 6 is in the set → become 12; 12 is in the set → become 24; 24 is not in the set, so we return 24.
Note that if original is absent from the start, the loop never runs and we simply return original unchanged.