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 <= 1000Using 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.
Java
JavaScript
C
C++
C#
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'.
Java
JavaScript
C
C++
C#
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.
| 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. |
2154 Keep Multiplying Found Values by Two || Weekly Contest 278 || LeetCode 2154 || Easy || C++ • Bro Coders • 611 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