2154. Keep Multiplying Found Values by Two

EasyArrayHash TableSortingSimulation

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 set s which contains our nums.
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 in s.

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 set s:
- 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.
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 as original 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.
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 Evaluator

Example 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 set s. The set s will be {1, 3, 4, 2, 8, 16}.
We start a while loop that will run as long as original is in s.
- First iteration:
  - Check if original (which is 2) is in s. It is, so we proceed.
  - We double original using the left shift operator: original <<= 1.
  - Now original becomes 4.
- Second iteration:
  - Check if the new original (which is 4) is in s. It is, so we repeat the doubling process.
  - Double original again: original is now 8.
- Third iteration:
  - Check if original (now 8) is in s. It is, therefore we double it again.
  - original after the left shift is now 16.
- Fourth iteration:
  - Check if original (now 16) is in s. It is, so we double it once more.
  - Doubling original gives us 32.
- Fifth iteration:
  - Check if original (now 32) is in s. It is not, so the while loop exits.
The value of original is now 32, and since it's not in the set s, 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know