Skip to main content
Talentd

Keep Multiplying Found Values by Two - Solution & Explanation

EasyArrayHash TableSortingSimulation12 min readAsked at: Goldman Sachs, Meta, Google +1
Practice this problem

Problem Statement

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:

  1. If original is found in nums, multiply it by two (i.e., set original = 2 * original).
  2. Otherwise, stop the process.
  3. 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 <= 1000
  • 1 <= nums[i], original <= 1000

Approach Overview

Problem Overview: You receive an integer original and an integer array nums. If original exists in the array, double it. Repeat the process while the new value still exists in the array. Return the final value once the doubled number is no longer present.

Approach 1: Hash Set for Quick Lookup (Time: O(n), Space: O(n))

Convert the array into a HashSet so membership checks become constant time. Insert every element from nums into the set, then repeatedly check if original exists using set.contains(original). Each time it exists, multiply the value by two and continue the lookup. The key insight is that the algorithm never scans the array again after building the set—each step is just a hash lookup. This approach works well for general cases and is the expected solution in interviews when working with hash tables and arrays.

Approach 2: Sorting and Binary Search (Time: O(n log n), Space: O(1) or O(log n))

First sort the array so you can apply binary search for fast lookups. After sorting, repeatedly search for original using binary search. If found, double the value and search again. The process stops when binary search fails to locate the number. Sorting dominates the runtime with O(n log n) complexity, while each lookup costs O(log n). This method is useful when the array is already sorted or when working within patterns related to sorting and binary search.

Recommended for interviews: The hash set approach is typically expected. It reduces the lookup operation from linear search to constant time and keeps the logic simple. Sorting plus binary search demonstrates understanding of ordered data and search strategies, but the extra O(n log n) sorting step makes it less optimal. Showing both approaches during discussion highlights awareness of tradeoffs between preprocessing (sorting) and direct hashing.

Approach 1: Approach 1: Hash Set for Quick Lookup

Using 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.

Code

PythonJavaJavaScriptCC++C#

Python

Java

JavaScript

C

C++

C#

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Sorting and Binary Search

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'.

Code

PythonJavaJavaScriptCC++C#

Python

Java

JavaScript

C

C++

C#

Complexity

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.

Try this approach in the editor →

Approach 3: Hash Table

We use a hash table s to record all the numbers in the array nums.

Next, starting from original, if original is in s, we multiply original by 2 until original is not in s anymore, then return original.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Hash Set for Quick Lookup

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.

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.
Space Complexity: O(1) additional space, besides the input array.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Set for Quick LookupO(n)O(n)General case when fast membership checks are needed
Sorting + Binary SearchO(n log n)O(1) to O(log n)Useful if the array is already sorted or when practicing binary search patterns

Video Solution

Keep Multiplying Found Values by Two - Leetcode 2154 - Python • NeetCodeIO • 2,689 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Keep Multiplying Found Values by Two easy or hard?
LeetCode classifies this problem as Easy with an acceptance rate above 75%. The main concept is recognizing that repeated array scans are inefficient and replacing them with constant-time lookups using a hash set.
Keep Multiplying Found Values by Two Python/Java solution
Most implementations build a hash set from the input array, then repeatedly double the value while it exists in the set. This logic is straightforward to implement in Python, Java, JavaScript, C++, and other languages using built-in set or hash set structures.
How to solve Keep Multiplying Found Values by Two in O(n)?
Store all elements from the array in a hash set. While the set contains the current value, multiply the value by two and repeat the lookup. Hash table membership checks run in O(1), so the full algorithm runs in O(n) time.
What is the best approach for Keep Multiplying Found Values by Two?
The hash set approach is the most efficient. Insert all numbers into a set, then repeatedly check if the current value exists and double it. Each lookup is O(1), giving a total time complexity of O(n) and space complexity of O(n).
Is Keep Multiplying Found Values by Two asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving hash tables and repeated lookups. Variants of similar membership-check problems appear in interviews at companies like Amazon and Google where candidates must optimize array searches using hashing.
What data structure is used in Keep Multiplying Found Values by Two?
The primary data structure is a hash set. It allows constant-time membership checks when verifying whether the current value exists in the array. An alternative approach uses a sorted array with binary search.
What is the time complexity of Keep Multiplying Found Values by Two?
The optimal solution runs in O(n) time using a hash set. Building the set takes O(n), and each membership check while doubling the value is constant time. The sorting-based alternative takes O(n log n) due to the initial sort.

Ready to solve this problem?

Practice Keep Multiplying Found Values by Two with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check If N and Its Double Exist

Next

Largest Number At Least Twice of Others