Solution Explanation:

The problem asks us to repeatedly double a given integer (original) as long as it exists within a given array (nums). The process stops when the doubled number is no longer present in the array. The final value of the integer is then returned.

Approach: Using a Hash Set (or equivalent)

The most efficient approach utilizes a hash set (or a similar data structure like a dictionary in Python or a Set in Java/TypeScript/Go) to store the elements of the input array nums. A hash set provides constant-time average complexity for checking membership (contains operation).

1. Create a Hash Set: The elements of the nums array are added to a hash set. This allows for quick lookups of whether a number is present in the array.

2. Iterative Doubling: The original value is repeatedly checked against the hash set. If found, it's doubled (original *= 2 or original <<= 1 which is a bitwise left shift, equivalent to multiplying by 2). This continues until original is no longer found in the hash set.

3. Return the Final Value: Once the loop terminates (because original is not in the hash set), the final value of original is returned.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the nums array. The creation of the hash set takes O(n) time in the worst case. The while loop iterates at most a logarithmic number of times with respect to the maximum value in nums (since we are doubling original each iteration), but this is overshadowed by the initial O(n) step. Thus, the overall time complexity is dominated by the creation of the hash set, resulting in O(n).

• Space Complexity: O(n) because the hash set stores, in the worst case, all n elements from the nums array.

Code Examples (with explanations inline)

Python:

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        num_set = set(nums)  # Create a set for efficient lookups (O(n) time)
        while original in num_set:  # Check if original is in the set (O(1) average time)
            original *= 2  # Double the original value
        return original  # Return the final value

Java:

class Solution {
    public int findFinalValue(int[] nums, int original) {
        Set<Integer> numSet = new HashSet<>(); // Create a HashSet for efficient lookups
        for (int num : nums) {
            numSet.add(num); // Add each number from nums to the HashSet (O(n) time)
        }
        while (numSet.contains(original)) { // Check if original is in the set (O(1) average time)
            original *= 2; // Double the original value
        }
        return original; // Return the final value
    }
}

C++:

class Solution {
public:
    int findFinalValue(vector<int>& nums, int original) {
        unordered_set<int> numSet(nums.begin(), nums.end()); // Create an unordered_set for efficient lookups
        while (numSet.count(original)) { // Check if original is in the set (O(1) average time)
            original *= 2; // Double the original value
        }
        return original; // Return the final value
    }
};

Go:

func findFinalValue(nums []int, original int) int {
	numSet := make(map[int]bool) // Create a map (hash table) for efficient lookups
	for _, num := range nums {
		numSet[num] = true // Add each number from nums to the map (O(n) time)
	}
	for numSet[original] { // Check if original is in the map (O(1) average time)
		original *= 2 // Double the original value
	}
	return original // Return the final value
}

TypeScript:

function findFinalValue(nums: number[], original: number): number {
    const numSet = new Set(nums); // Create a Set for efficient lookups
    while (numSet.has(original)) { // Check if original is in the set (O(1) average time)
        original *= 2; // Double the original value
    }
    return original; // Return the final value
}

These code examples all implement the same core algorithm, showcasing its adaptability across different programming languages. They all achieve the optimal time complexity of O(n) due to the use of hash tables for efficient lookups.