Keep Multiplying Found Values by Two — Problem & Solution
Keep Multiplying Found Values by Two solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Keep Multiplying Found Values by Two is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting, Simulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Start with the number original and repeat:
- If
originaloccurs innums, double it (original = 2 * original) and go back to step 1. - Otherwise stop.
Return the final value of original.
Example 1
Input: nums = [8,2,4,9], original = 2
Output: 16
Explanation: 2 is present → 4 is present → 8 is present → 16 is not.
Example 2
Input: nums = [2,7,9], original = 4
Output: 4
Example 3
Input: nums = [1,2,4,8,16,32], original = 1
Output: 64
Constraints
1 <= nums.length <= 10001 <= nums[i], original <= 1000
Hints for Keep Multiplying Found Values by Two
Hint 1
Each step is a membership test followed by a doubling.
Hint 2
Searching the array every time costs O(n) per step; a set makes each test O(1).
Hint 3
Values never exceed 1000, so once
originalpasses 1000 it can no longer be found.
How to solve Keep Multiplying Found Values by Two
Put the values in a set and follow the chain original, 2·original, 4·original, ... until a value is missing.
Approach
- Insert every value of
numsinto a set (or a boolean array indexed up to 1000). - While
originalis in the set, double it. - Return
original.
Why it works
This is exactly the process in the statement, with each membership test answered in constant time. The loop terminates because original at least doubles each round and the set holds nothing above 1000 — at most about ten doublings.
Complexity
- Time —
O(n + log(max / original)) - Space —
O(n)
Pitfalls
- With a boolean array, check the bound before indexing:
originalcan reach 2048. - Keep doubling until a value is missing — not just once.
- Sorting and scanning once also works, since the chain only increases.
Reference solution
Python
from typing import List
def findFinalValue(nums: List[int], original: int) -> int:
present = set(nums)
while original in present:
original *= 2
return originalJava
public static int findFinalValue(int[] nums, int original) {
boolean[] present = new boolean[1001];
for (int v : nums) present[v] = true;
while (original <= 1000 && present[original]) original *= 2;
return original;
}C++
int findFinalValue(vector<int>& nums, int original) {
unordered_set<int> present(nums.begin(), nums.end());
while (present.count(original)) original *= 2;
return original;
}JavaScript
var findFinalValue = function(nums, original) {
var present = new Set(nums);
while (present.has(original)) original *= 2;
return original;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets