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:
original is found in nums, multiply it by two (i.e., set original = 2 * original).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 <= 10001 <= nums[i], original <= 1000Problem Overview: You receive an integer original and an integer array nums. If original exists in the array, double it. Repeat the process while the new value still exists in the array. Return the final value once the doubled number is no longer present.
Approach 1: Hash Set for Quick Lookup (Time: O(n), Space: O(n))
Convert the array into a HashSet so membership checks become constant time. Insert every element from nums into the set, then repeatedly check if original exists using set.contains(original). Each time it exists, multiply the value by two and continue the lookup. The key insight is that the algorithm never scans the array again after building the set—each step is just a hash lookup. This approach works well for general cases and is the expected solution in interviews when working with hash tables and arrays.
Approach 2: Sorting and Binary Search (Time: O(n log n), Space: O(1) or O(log n))
First sort the array so you can apply binary search for fast lookups. After sorting, repeatedly search for original using binary search. If found, double the value and search again. The process stops when binary search fails to locate the number. Sorting dominates the runtime with O(n log n) complexity, while each lookup costs O(log n). This method is useful when the array is already sorted or when working within patterns related to sorting and binary search.
Recommended for interviews: The hash set approach is typically expected. It reduces the lookup operation from linear search to constant time and keeps the logic simple. Sorting plus binary search demonstrates understanding of ordered data and search strategies, but the extra O(n log n) sorting step makes it less optimal. Showing both approaches during discussion highlights awareness of tradeoffs between preprocessing (sorting) and direct hashing.
Using a hash set allows for constant time complexity lookups, which is efficient for checking if each multiplied value of 'original' is present in 'nums'. We will iterate, multiplying 'original' by two, as long as it is found in the set of numbers.
First, convert 'nums' to a set to allow O(1) lookup times. Then, use a while loop to multiply 'original' by two while it exists in the set. Return 'original' when it is no longer in the set.
Time Complexity: O(n), where n is the number of elements in 'nums'.
Space Complexity: O(n), because of the space used by the set.
By sorting the array, we can use binary search to look for 'original'. While this increases the initial overhead, binary search is generally more efficient for repeated lookups.
First, sort the array. Use the bisect module's bisect_left method to find the position of 'original'. If found, multiply it by 2 and repeat until 'original' is no longer found in the sorted 'nums'.
Time Complexity: O(n log n) due to sorting, and O(log n) for each lookup, though O(n log n) dominates.
Space Complexity: O(1) additional space, besides the input array.
We use a hash table s to record all the numbers in the array nums.
Next, starting from original, if original is in s, we multiply original by 2 until original is not in s anymore, then return original.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Approach 1: Hash Set for Quick Lookup | Time Complexity: O(n), where n is the number of elements in 'nums'. |
| Approach 2: Sorting and Binary Search | Time Complexity: O(n log n) due to sorting, and O(log n) for each lookup, though O(n log n) dominates. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set for Quick Lookup | O(n) | O(n) | General case when fast membership checks are needed |
| Sorting + Binary Search | O(n log n) | O(1) to O(log n) | Useful if the array is already sorted or when practicing binary search patterns |
Keep Multiplying Found Values by Two - Leetcode 2154 - Python • NeetCodeIO • 2,582 views views
Watch 9 more video solutions →Practice Keep Multiplying Found Values by Two with our built-in code editor and test cases.
Practice on FleetCode