Leetcode 2154: Keep Multiplying Found Values by Two

Input: The input consists of an array of integers 'nums' and an integer 'original'.

Example: nums = [4, 2, 8, 1, 16], original = 4

Constraints:

• 1 <= nums.length <= 1000

• 1 <= nums[i], original <= 1000

Output: Return the final value of 'original' after performing the described operations.

Example: Output: 64

Constraints:

• The final value of 'original' should be returned after the process stops.

Goal: Check if 'original' is in the array, and if so, multiply it by two. Repeat this process until 'original' is no longer found in the array.

Steps:

• Create a frequency map to count occurrences of each number in 'nums'.

• Check if 'original' is present in 'nums' and multiply it by two if found.

• Repeat the process until 'original' is not found.

Goal: The array 'nums' will contain valid integers, and the value of 'original' will be within the given bounds.

Steps:

• 1 <= nums.length <= 1000

• 1 <= nums[i], original <= 1000

Assumptions:

• The input array contains integers within the specified range, and the number 'original' is also within the valid bounds.

• Input: Example 1: nums = [4, 2, 8, 1, 16], original = 4

• Explanation: The number 4 is found and doubled to 8, then 8 is found and doubled to 16, and so on until 64 is obtained, which is not found in the array.

• Input: Example 2: nums = [1, 3, 5], original = 2

• Explanation: The number 2 is not found in the array, so the process stops immediately, and the final value remains 2.

Approach: The approach involves checking if the number 'original' is in the array, and multiplying it by 2 whenever it is found, repeating the process until it is no longer found.

Observations:

• The algorithm needs to check for the presence of a number and keep multiplying it until it is no longer found.

• A frequency map can be useful to quickly check if a number exists in the array.

Steps:

• Build a frequency map for all numbers in 'nums'.

• While 'original' is found in the map, double its value and continue.

• Return 'original' when it is no longer found in the map.

Empty Inputs:

• Empty input arrays are not allowed by the problem constraints.

Large Inputs:

• The solution should efficiently handle large arrays with a length of up to 1000.

Special Values:

• If 'original' is not found initially, the algorithm should return the unchanged value of 'original'.

Constraints:

• The array 'nums' and the value 'original' are within specified bounds.

  int findFinalValue(vector<int>& nums, int o) {
    int h[1001]={};
    for(auto i:nums) h[i]++;
		
    while(o<=1000 && h[o])
        o*=2;
    
    return o;
}

1 : Function Declaration

  int findFinalValue(vector<int>& nums, int o) {

The function 'findFinalValue' takes an array 'nums' and an integer 'o'. It calculates a final value by repeatedly doubling 'o' if the value exists in 'nums'.

2 : Array Initialization

    int h[1001]={};

Initialize a frequency array 'h' of size 1001 to store the frequency of each integer in 'nums'. The array is initially set to zero.

3 : Frequency Counting

    for(auto i:nums) h[i]++;

Iterate over each element in the 'nums' array and update the frequency of that element in the array 'h'.

4 : Loop Control

    while(o<=1000 && h[o])

While 'o' is less than or equal to 1000 and the value 'o' exists in the frequency array 'h', keep doubling 'o'.

5 : Doubling

        o*=2;

Double the value of 'o'. This continues until 'o' is not present in the frequency array or exceeds 1000.

6 : Return Statement

    return o;

Return the final value of 'o' after the loop terminates.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) due to the need to iterate through the array once to build the frequency map.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the storage required for the frequency map.

Leetcode 2154: Keep Multiplying Found Values by Two

Explore →