algoadvance

You are given an array of integers nums. Your task is to find a value, original, which is in the nums array and keep multiplying it by 2 as long as it is present in the array. Once the value does not exist in the array, return the final value.

Clarifying Questions

1. Duplicity in nums:
   • Q: Can there be duplicate values in the nums array?
   • A: Yes, it’s possible.
2. Array Properties:
   • Q: Are there any restrictions on the size or range of the numbers in nums?
   • A: The problem does not specify, so we assume typical integer values.
3. Initial Value:
   • Q: Should the original value always be chosen from the nums array?
   • A: Yes, original must be a value from the nums array.

Strategy

1. Initial Setup:
   • Start with a given initial value, original.
2. Set for Fast Lookup:
   • Convert nums into a set to allow O(1) average-time complexity for checking the presence of values.
3. Multiplication Loop:
   • While original is in the set, multiply it by 2.
   • Once original is not found in the set, break the loop and return the current value of original.

This ensures that the solution is efficient and leverages fast membership testing.

Time Complexity

• Converting nums to a set: O(n)
• Each lookup operation in the set: O(1) on average
• In the worst case, if original starts very small and doubles many times before it is not found, the loop can run multiple times, but still, this would be much fewer operations compared to any linear or quadratic approach.

Hence, the overall time complexity would be approximately O(n).

Code

Here’s how you can implement this in Python:

def findFinalValue(nums, original):
    nums_set = set(nums)
    while original in nums_set:
        original *= 2
    return original

Example Walkthrough:

• Given nums = [5, 3, 6, 1, 12] and original = 3:
  • original = 3 is in nums_set -> multiply original by 2 -> original = 6.
  • original = 6 is in nums_set -> multiply original by 2 -> original = 12.
  • original = 12 is in nums_set -> multiply original by 2 -> original = 24.
  • original = 24 is not in nums_set, return original = 24.

This approach ensures we find the correct value efficiently.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?