Keep Multiplying Found Values by Two solution and explanation
Google
9 more videos on this problem
Keep Multiplying Found Values by Two - Leetcode 2154 - PythonNeetCodeIO · 3:19 · 2K views
2154 Keep Multiplying Found Values by Two || Weekly Contest 278 || LeetCode 2154 || Easy || C++Bro Coders · 3:43 · 739 views
Keep Multiplying Found Values by Two| Leeetcode 2154 | Contest 278 | Easy 🔥🔥🔥 | Set ProblemCoding Decoded · 3:48 · 659 views
Keep Multiplying Found Values by Two | LeetCode 2154 | Brute Better Optimal SolutionSanyam IIT Guwahati · 9:18 · 402 views
2154. Keep Multiplying Found Values by Two (Leetcode Easy)Programming Live with Larry · 3:30 · 395 views
Daily Leetcode #2059: Nov 19, 2025 - 2154. Keep Multiplying Found Values by TwoProgramming Live with Larry · 4:37 · 378 views
Keep Multiplying Found Values by Two | Leetcode 2154 | DSA | HIndi Explaination | Code With DeepakCode with Deepak · 6:44 · 279 views
Keep Multiplying Found Values by Two - LeetCode 2154 - Java Solutionalgobest - Computer Science · 3:51 · 154 views
Keep Multiplying Found Values by Two | LeetCode 2154 | Sorting HashSet | Java Code | Developer CoderDeveloper Coder · 7:58 · 139 views
2154. Keep Multiplying Found Values by Two | Leetcode Daily - PythonLeetcode Daily · 8:06 · 129 views
The problem
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
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.
def find_final_value(nums, original):
nums_set = set(nums)
while original in nums_set:
original *= 2
return originalimport java.util.HashSet;
import java.util.Set;
public 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;
}
}#include <unordered_set>
#include <vector>
class Solution {
public:
int findFinalValue(std::vector<int>& nums, int original) {
std::unordered_set<int> numsSet(nums.begin(), nums.end());
while (numsSet.find(original) != numsSet.end()) {
original *= 2;
}
return original;
}
};function findFinalValue(nums, original) {
let numsSet = new Set(nums);
while (numsSet.has(original)) {
original *= 2;
}
return original;
}#include <stdio.h>
#include <stdbool.h>
bool searchArray(int nums[], int size, int target) {
for (int i = 0; i < size; i++) {
if (nums[i] == target) {
return true;
}
}
return false;
}
int findFinalValue(int nums[], int numsSize, int original) {
while (searchArray(nums, numsSize, original)) {
original *= 2;
}
return original;
}using System;
using System.Collections.Generic;
public class Solution {
public int FindFinalValue(int[] nums, int original) {
HashSet<int> numsSet = new HashSet<int>(nums);
while (numsSet.Contains(original)) {
original *= 2;
}
return original;
}
}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.
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: 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.
def find_final_value(nums, original):
nums.sort()
import bisect
while bisect.bisect_left(nums, original) < len(nums) and nums[bisect.bisect_left(nums, original)] == original:
original *= 2
return originalimport java.util.Arrays;
public class Solution {
public int findFinalValue(int[] nums, int original) {
Arrays.sort(nums);
while (true) {
int index = Arrays.binarySearch(nums, original);
if (index < 0) {
break;
}
original *= 2;
}
return original;
}
}#include <vector>
#include <algorithm>
class Solution {
public:
int findFinalValue(std::vector<int>& nums, int original) {
std::sort(nums.begin(), nums.end());
while (std::binary_search(nums.begin(), nums.end(), original)) {
original *= 2;
}
return original;
}
};function findFinalValue(nums, original) {
nums.sort((a, b) => a - b);
while (true) {
let index = nums.indexOf(original);
if (index === -1) {
break;
}
original *= 2;
}
return original;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int binarySearch(int nums[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int findFinalValue(int nums[], int size, int original) {
qsort(nums, size, sizeof(int), compare);
while (binarySearch(nums, size, original) != -1) {
original *= 2;
}
return original;
}using System;
public class Solution {
public int FindFinalValue(int[] nums, int original) {
Array.Sort(nums);
while (Array.BinarySearch(nums, original) >= 0) {
original *= 2;
}
return original;
}
}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'.
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.
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.
function findFinalValue(nums: number[], original: number): number {
const s: Set<number> = new Set([...nums]);
while (s.has(original)) {
original <<= 1;
}
return original;
}func findFinalValue(nums []int, original int) int {
s := map[int]bool{}
for _, x := range nums {
s[x] = true
}
for s[original] {
original <<= 1
}
return original
}impl Solution {
pub fn find_final_value(nums: Vec<i32>, original: i32) -> i32 {
use std::collections::HashSet;
let s: HashSet<i32> = nums.into_iter().collect();
let mut original = original;
while s.contains(&original) {
original <<= 1;
}
original
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Hash Set for Quick Lookup | Time Complexity: O(n), where n is the number of elements in 'nums'. |
| 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. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set for Quick Lookup | O(n) | O(n) | General case when fast membership checks are needed |
| Sorting + Binary Search | O(n log n) | O(1) to O(log n) | Useful if the array is already sorted or when practicing binary search patterns |
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.