algoadvance

Leetcode 2154. Keep Multiplying Found Values by Two

Problem Statement

You’re given an integer array nums. You are also given an integer original which is the starting value. Your task is to find if the value original exists in the nums array. If it does, multiply the original value by two and repeat the process until the value original is no longer present in nums. Return the final value of original.

Example

  1. Input: nums = [5,3,6,1,12], original = 3 Output: 24

  2. Input: nums = [2,7,9], original = 4 Output: 4

Constraints

Clarifying Questions

  1. Q: Should we modify the nums array or keep it intact?
    • A: You should keep the nums array intact.
  2. Q: Are the elements in the nums array unique or can they be duplicated?
    • A: The elements can be duplicated.

Strategy

  1. Utilize a Set:
    • Convert the nums array to a set to allow O(1) time complexity checks for the presence of values.
  2. Iteration:
    • Perform a loop where you check if the original value exists in the set.
    • If it does, multiply original by 2 and continue.
    • If it doesn’t, break the loop and return the current value of original.

Code

#include <vector>
#include <unordered_set>

int findFinalValue(std::vector<int>& nums, int original) {
    std::unordered_set<int> numSet(nums.begin(), nums.end());
    
    while (numSet.find(original) != numSet.end()) {
        original *= 2;
    }
    
    return original;
}

Time Complexity

  1. Conversion from vector to set:
    • O(n), where n is the number of elements in nums.
  2. While Loop:
    • In the worst case, the value of original could double up to the maximum value possible within the integer range. However, practically, the loop will run for a limited number of iterations due to the constraints provided.

Overall, the time complexity can be considered O(n) for most practical purposes, considering the conversion to set and membership checking form the bulk of the operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI