Keep Multiplying Found Values by Two

Easy
1122.

Keep Multiplying Found Values by Two

Keep Multiplying Found Values by Two is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

Start with the number original and repeat:

  1. If original occurs in nums, double it (original = 2 * original) and go back to step 1.
  2. 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 <= 1000
  • 1 <= nums[i], original <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} original
 * @return {number}
 */
var findFinalValue = function(nums, original) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

Problem statement

Start with the number original and repeat:

  1. If original occurs in nums, double it (original = 2 * original) and go back to step 1.
  2. 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 <= 1000
  • 1 <= nums[i], original <= 1000

Hints for Keep Multiplying Found Values by Two

  1. Hint 1

    Each step is a membership test followed by a doubling.

  2. Hint 2

    Searching the array every time costs O(n) per step; a set makes each test O(1).

  3. Hint 3

    Values never exceed 1000, so once original passes 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

  1. Insert every value of nums into a set (or a boolean array indexed up to 1000).
  2. While original is in the set, double it.
  3. 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: original can 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 original

Java

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