algoadvance

Leetcode 2154. Keep Multiplying Found Values by Two

Problem Statement

You are given an integer array nums. You are also given an integer original which is guaranteed to be one of the elements in nums.

You should do the following operation as long as you can:

Return the final value of original.

Example 1:

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

Example 2:

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

Clarifying Questions

  1. Q: What is the size limit of the input array nums? A: There is no explicit size limit given, but we may assume typical constraints like up to 10^4 elements.

  2. Q: Is nums always a non-empty array? A: Yes, it’s stated in the problem description.

  3. Q: Are there any constraints on the values within nums? A: The problem doesn’t specify, but typically array elements can range from -10^4 to 10^4.

  4. Q: Can original be a negative number? A: Technically yes, but it’s mentioned that original is guaranteed to be one of the elements in nums.

Strategy

  1. We’ll use a HashSet to store the elements of nums for O(1) average-time complexity checks to see if original is in nums.

  2. We iterate while original is found in the set. Every time it’s found, we multiply original by 2.

  3. We continue this process until original no longer exists in nums.

  4. Finally, we return the value of original.

Code

import java.util.HashSet;

public class Solution {
    public int findFinalValue(int[] nums, int original) {
        // Step 1: Create a HashSet from the elements of nums
        HashSet<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        // Step 2: Multiply 'original' by 2 until it's no longer in the set
        while (numSet.contains(original)) {
            original *= 2;
        }
        
        // Step 3: Return the final value of 'original'
        return original;
    }
}

Time Complexity

  1. HashSet Creation: O(n) where n is the number of elements in nums (each insertion is O(1) amortized time).

  2. Checking in HashSet: In the worst case, we might check log(N) times (each check O(1)).

    • Suppose original starts with the minimum element and needs to be doubled until a maximum possible value within the range of given constraints (like say 32,768).

    • Max multiplications needed will be bounded by the number of bits, usually less than or equal to 14 (log2 (10^4)).

  3. Overall Complexity: O(n)

This method ensures both time and space efficiency while solving the problem effectively.

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