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.
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; }}Video 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.