2154. Keep Multiplying Found Values by Two
Approach
Store nums in a HashSet; repeatedly double original while it exists in the set.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
Simulation problems require implementing the described process step by step. Focus on correctly handling edge cases and state transitions. Common in geometry, game problems, and string manipulation. Optimize only if the naive simulation exceeds the time limit.
// Approach: Store nums in a HashSet; repeatedly double original while it exists in the set.
// Time: O(n + log(max)) Space: O(n)
public class Solution
{
public int FindFinalValue(int[] nums, int original)
{
// Create a HashSet to store all unique values from the array for O(1) lookup
HashSet<int> numSet = new HashSet<int>(nums);
// Keep doubling the original value while it exists in the set
while (numSet.Contains(original))
// Double the original value using left shift operation (equivalent to multiplying by 2)
original <<= 1;
// Return the final value that is not present in the set
return original;
}
}