2154. Keep Multiplying Found Values by Two
Problem Description
In this problem, you start with an integer called original
and an array of integers called nums
. Your goal is to perform a series of steps in which you repeatedly check whether original
is in the array nums
. If it is, you double the value of original
and then search for the new value in the array. You continue this process of doubling and searching until original
is no longer found in nums
. The task is to return the final value of original
after you've either doubled it several times or stopped as soon as it's not found in the array.
This problem involves the use of an iterative process to repeatedly update a number based on the contents of an array. It can be seen as a game or a search operation that has the potential to alter the target number multiple times.
Intuition
The solution to this problem relies on efficiency and simplicity. Since we are searching for original
in nums
multiple times, a key insight is to use a data structure with fast lookup times. A set data structure provides O(1) average time complexity for lookups, which is ideal.
To utilize this, we first convert the list nums
into a set s
. Sets do not contain duplicate elements and allow us to check if an element is present in constant time.
The process is as follows:
- Check if
original
is in the sets
which contains ournums
. - If it is, multiply
original
by two. This is efficiently done using the left shift operator<<
, which basically doubles the number. - If it's not found, return the current value of
original
. - Repeat this process until
original
is not ins
.
The while loop in the solution keeps this process going, systematically doubling original
and checking for its presence in the set s
. This loop will eventually terminate when original
is no longer present in the set, at which point the most recent value of original
is returned as the final result.
Learn more about Sorting patterns.
Solution Approach
The solution provided is both elegant and efficient, utilizing a set data structure and a simple while loop. Below is a step-by-step walkthrough of the implementation and the reasoning behind each step:
-
Convert the list of numbers
nums
to a sets
:- The conversion is done by initializing the set with
nums
, i.e.,s = set(nums)
. - This step is crucial because it optimizes our search operation. While the lookup time for an element in a list is O(n), for a set, it's O(1) on average.
- Despite the conversion costing O(n) time where n is the number of elements in
nums
, this cost is justified since we only incur it once, and it significantly speeds up the numerous lookups that follow.
- The conversion is done by initializing the set with
-
Use a while loop to determine the final value of
original
:- The condition for the while loop is
original in s
, meaning that as long asoriginal
is found in the set, the loop continues. - Inside the loop,
original
is doubled using the left shift operator,original <<= 1
.- The left shift operator effectively multiplies the number by two. Using
<<= 1
on an integer is equivalent to multiplying it by 2. - This is a bit manipulation trick that performs the operation quickly and with less code.
- The left shift operator effectively multiplies the number by two. Using
- The condition for the while loop is
-
Return the final value of
original
when it's no longer found in the set.
The algorithm's time complexity primarily depends on the number of times original
can be doubled before it exceeds the largest number in nums
. If we denote this number of doublings as k
, then the overall time complexity is O(n + k), where n is the length of nums
. The space complexity is O(n) due to the additional set.
To understand the practical bounds of k
, consider that integers have a fixed upper limit (for example, 2^31 - 1 for 32-bit integers). The value of original
will reach this upper limit after a finite number of doublings regardless of the contents of nums
. Therefore, k
is bounded and in practice is much smaller than the maximum possible value of original
. Thus the doubling operation does not have a significant impact on the time complexity relative to the size of nums
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Suppose we have the integer original = 2
and the array nums = [1, 3, 4, 2, 8, 16]
. We are tasked with doubling original
and checking if the new value is in nums
, continuing this process until the value is not found.
-
Convert
nums
to a sets
. The sets
will be{1, 3, 4, 2, 8, 16}
. -
We start a while loop that will run as long as
original
is ins
.- First iteration:
- Check if
original
(which is 2) is ins
. It is, so we proceed. - We double
original
using the left shift operator:original <<= 1
. - Now
original
becomes 4.
- Check if
- Second iteration:
- Check if the new
original
(which is 4) is ins
. It is, so we repeat the doubling process. - Double
original
again:original
is now 8.
- Check if the new
- Third iteration:
- Check if
original
(now 8) is ins
. It is, therefore we double it again. original
after the left shift is now 16.
- Check if
- Fourth iteration:
- Check if
original
(now 16) is ins
. It is, so we double it once more. - Doubling
original
gives us 32.
- Check if
- Fifth iteration:
- Check if
original
(now 32) is ins
. It is not, so the while loop exits.
- Check if
- First iteration:
-
The value of
original
is now 32, and since it's not in the sets
, we return 32 as the final value.
Throughout this process, we have used the set for efficient lookup and doubled original
easily with the left shift operator. The final result of this example would be 32
, as that's the value of original
when it's no longer present in nums
.
Solution Implementation
1class Solution:
2 def findFinalValue(self, nums: List[int], original: int) -> int:
3 # Convert the list of numbers into a set for faster lookup
4 num_set = set(nums)
5
6 # Keep doubling the original value as long as it's found in the set
7 while original in num_set:
8 original *= 2 # Equivalent to original <<= 1 but clearer
9
10 # Once the value is not found in the set, return it
11 return original
12
1class Solution {
2
3 /**
4 * Finds the final value by doubling the original number until it's not found in the set.
5 *
6 * @param nums An array of integers.
7 * @param original The integer whose final value is to be found.
8 * @return The final value of the original integer after doubling.
9 */
10 public int findFinalValue(int[] nums, int original) {
11 // Create a set to store unique elements from the array
12 Set<Integer> numSet = new HashSet<>();
13
14 // Add all elements from the array into the set for quicker searches
15 for (int num : nums) {
16 numSet.add(num);
17 }
18
19 // Keep doubling the original value until it's no longer found in the set
20 while (numSet.contains(original)) {
21 original *= 2; // equivalent to original <<= 1; for doubling
22 }
23
24 // Return the final value of original after it couldn't be doubled any further (not found in the set)
25 return original;
26 }
27}
28
1#include <unordered_set>
2#include <vector>
3
4class Solution {
5public:
6 // Function to find the final value after doubling the original value if it is in the nums array
7 int findFinalValue(std::vector<int>& nums, int original) {
8 // Create an unordered_set to store the unique elements in 'nums'
9 std::unordered_set<int> elementsSet;
10
11 // Insert all the numbers in the 'nums' vector into the set
12 for (int num : nums) {
13 elementsSet.insert(num);
14 }
15
16 // Keep doubling the 'original' value as long as it is present in the set
17 while (elementsSet.count(original) > 0) {
18 original <<= 1; // This is equivalent to multiplying 'original' by 2
19 }
20
21 // Return the final value of 'original' after it can no longer be doubled
22 return original;
23 }
24};
25
1// Finds the final value by multiplying the original value by two as long
2// as that new value exists in the set generated from the nums array.
3function findFinalValue(nums: number[], original: number): number {
4 // Initialize a new set from the nums array to facilitate O(1) lookups.
5 let numberSet: Set<number> = new Set(nums);
6
7 // Continue doubling 'original' as long as it exists within 'numberSet'.
8 while (numberSet.has(original)) {
9 original *= 2;
10 }
11
12 // Return the final value, which is not present in 'numberSet'.
13 return original;
14}
15
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n)
where n
is the length of the nums
list. The reasoning behind this is that the conversion of the list to a set, s = set(nums)
, takes linear time relative to the number of elements in the list. Then, the while
loop runs at most until the value of original
becomes larger than the largest element in s
. In the worst-case scenario, this value could double at most n
times before exceeding the max element in nums
if the array contained a sequence of powers of 2. However, since the while
loop checks membership in a set which is done in constant time, O(1)
, the increase in original
does not significantly affect the overall time complexity.
Space Complexity
The space complexity of the code is O(n)
. The extra space is used to create the set s
from the list nums
. The set will contain at most n
unique values where n
is the number of elements in nums
. Thus, the space complexity depends linearly on the size of the input array.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first