Watch 10 video solutions for Keep Multiplying Found Values by Two, a easy level problem involving Array, Hash Table, Sorting. This walkthrough by NeetCodeIO has 2,582 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |