Keep Multiplying Found Values by Two
EasyPrompt
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:
- If
originalis found innums, multiply it by two (i.e., setoriginal = 2 * original). - Otherwise, stop the process.
- Repeat this process with the new number as long as you keep finding the number.
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 <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We use a loop that continues as long as we can find the current original value in the nums array. Inside the loop, we perform a linear search through the nums array to check for the existence of original.
Algorithm
- Initialize a loop that continues as long as a number is found.
- In each iteration, perform a linear scan of the
numsarray to search for the currentoriginal. - If
originalis found, double its value and continue the loop. - If
originalis not found after scanning the entire array, exit the loop. - Return the final
originalvalue.
Walkthrough
Start with the given original value. Enter a loop that will run as long as we keep finding the number. Inside the loop, we need to determine if the current original exists in nums. We use a flag, say found, initialized to false, and a for loop to iterate through each element of nums. If an element num is equal to original, we set found to true, update original by multiplying it by 2, and break the inner for loop to restart the search with the new original. If the inner loop completes without finding the number (found remains false), we break the outer loop. Finally, we return the last value of original.
class Solution { public int findFinalValue(int[] nums, int original) { boolean foundInLoop = true; while (foundInLoop) { foundInLoop = false; for (int num : nums) { if (num == original) { original *= 2; foundInLoop = true; break; // Found the number, restart search with new original } } } return original; }}Complexity
Time
O(N * K), where N is the number of elements in `nums` and K is the number of times we find `original` and double it. Since K is small and logarithmically bounded by the value range, this is often acceptable but less efficient than other approaches.
Space
O(1), as we only use a few variables to store the state.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Inefficient due to repeated linear scans of the entire array. For each successful find, we rescan the array from the beginning.
To optimize the search process, we can first sort the input array nums. Once the array is sorted, we can use the much more efficient binary search algorithm to check for the existence of original in each step.
Algorithm
- Sort the input array
nums. - Start a loop that continues as long as
originalis found innums. - In each iteration, use binary search to check for the presence of
original. - If found, update
original = original * 2. - If not found, exit the loop.
- Return the final
originalvalue.
Walkthrough
The core idea is to replace the O(N) linear search with an O(log N) binary search. First, sort the nums array in ascending order. Then, enter a loop. In each iteration, perform a binary search for the current original value within the sorted nums array. Java's Arrays.binarySearch() is a convenient way to do this. It returns a non-negative index if the element is found, and a negative value otherwise. If the binary search finds original, we double original and continue the loop to search for the new value. If the binary search does not find original, we stop the process and break the loop. The final value of original is the result.
import java.util.Arrays; class Solution { public int findFinalValue(int[] nums, int original) { Arrays.sort(nums); // Keep searching as long as original is found while (Arrays.binarySearch(nums, original) >= 0) { original *= 2; } return original; }}Complexity
Time
O(N log N + K * log N). The initial sort takes O(N log N). Each of the K searches takes O(log N). The sorting step dominates the overall complexity, making it O(N log N).
Space
O(log N) or O(N), depending on the implementation of the sorting algorithm used. `Arrays.sort` in Java for primitive types has a space complexity of O(log N) on average for its recursion stack.
Trade-offs
Pros
Significantly faster than the brute-force approach for large arrays.
Cons
The cost of sorting the array might be unnecessary if the number of searches is very small.
It modifies the input array (if sorting in-place).
This is the most efficient approach. We can trade space for time by pre-processing the nums array and storing all its unique elements into a hash set. A hash set provides, on average, constant time O(1) for lookups (checking for the existence of an element).
Algorithm
- Create a hash set and populate it with all elements from the
numsarray. - Start a loop that checks if the current
originalis in the hash set. - The
containsoperation on a hash set is O(1) on average. - If
originalis in the set, double its value. - Repeat until
originalis not found in the set. - Return the final
originalvalue.
Walkthrough
First, create a HashSet of integers. Iterate through the nums array once and add every element to the hash set. This step effectively creates a quick-lookup table for all numbers present in nums. After building the set, start with the initial original value. Enter a while loop that continues as long as the hash set contains the current original value. The set.contains() method is an O(1) average time operation. Inside the loop, if original is found, simply double its value: original *= 2. The loop terminates when set.contains(original) returns false. The final value of original is the answer.
import java.util.HashSet;import java.util.Set; class Solution { public int findFinalValue(int[] nums, int original) { Set<Integer> numSet = new HashSet<>(); for (int num : nums) { numSet.add(num); } while (numSet.contains(original)) { original *= 2; } return original; }}Complexity
Time
O(N + K). It takes O(N) to build the hash set. The `while` loop runs K times, and each check is O(1) on average. This gives a total time complexity that is linear with respect to the size of the input array, effectively O(N).
Space
O(N) in the worst case, where all elements in `nums` are unique and are stored in the hash set.
Trade-offs
Pros
The fastest approach asymptotically.
The lookup time is constant on average, making the simulation part very quick.
Cons
Uses extra space proportional to the number of unique elements in the input array.
Solutions
Solution
class Solution {public int findFinalValue(int[] nums, int original) { Set<Integer> s = new HashSet<>(); for (int num : nums) { s.add(num); } while (s.contains(original)) { original <<= 1; } return original; }}class Solution {public: int findFinalValue(vector<int> &nums, int original) { unordered_set<int> s; for (int num : nums) s.insert(num); while (s.count(original)) original <<= 1; return original; }};class Solution: def findFinalValue(self, nums: List[int], original: int) -> int: s = set(nums) while original in s: original <<= 1 return originalVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.