Fewest Steps to Build an Array from Zeros
Updated
Problem statement
You start with an array of n zeros and want to turn it into the given array nums of the same length. Two kinds of steps are allowed:
- Add: pick one index and add 1 to the number there.
- Double: multiply every number in the array by 2 at once.
Return the fewest steps needed to reach nums.
Function
minOperations(nums: int[]) → intExamples
Example 1
nums = [1,6,0]return = 5Start from [0, 0, 0]. Add 1 to index 1: [0, 1, 0]. Double: [0, 2, 0]. Add 1 to index 1: [0, 3, 0]. Double: [0, 6, 0]. Add 1 to index 0: [1, 6, 0]. That is 5 steps: three add steps and two doublings. No shorter way exists.
Example 2
nums = [5,2,7]return = 8In binary the numbers are 101, 10 and 111. They hold 2 + 1 + 3 = 6 one bits, and each one bit needs its own add step. The longest number, 7, has 3 bits, so it needs 2 doublings, and every doubling works on all numbers at once. The total is 6 + 2 = 8.
Example 3
nums = [16,16,16]return = 7Add 1 to each index (3 steps) to get [1, 1, 1], then double four times: 2, 4, 8, 16. The four doublings are shared by all three numbers, so the total is 3 + 4 = 7.
Constraints
1 <= nums.length <= 50000 <= nums[i] < 10^6
More Expedia Online Assessment questions
- Balanced NumbersOA · Seen Aug 2026
- REST API: Discounted PriceOA · Seen Aug 2026
- Maximum Team SizeOA · Seen Mar 2026
- Per-Domain Request LimiterOA · Seen Oct 2025
- Count Equal-Frequency SubsequencesOA · Seen Mar 2025
- Count Increasing Stock PeriodsOA · Seen Mar 2025
- Get Minimum StepsOA · Seen Oct 2024
- Rank Songs by PopularityOA · Seen Oct 2024
- Calculate the SumOA · Seen Oct 2024
- Get Maximum EfficiencyOA · Seen Oct 2024
Similar questions at other companies
- Minimize the Maximum Array ElementChubb · OAChubb interview questions
- Minimum Halvings for Alternating ParityIBM · OAIBM interview questions
- Server SelectionPoint72 · OAPoint72 interview questions
- Minimum Servers for an Exact LoadJP Morgan Chase · OAJP Morgan Chase interview questions
- Get Max Or SumMicrosoft · OAMicrosoft interview questions
- Maximize PartitionsAmazon · OA
- Maximum XOR Elimination ScoreRippling · OARippling interview questions
- Minimum Cost for a Target WeightPace Stock Broking Services · PHONE SCREEN
- Minimum Row Deletions to Prevent a Target ORInMobi · ONSITE INTERVIEWInMobi interview questions
- Minimum Operations to Sort with Rotations Then SwapsBank of New York Mellon · OA
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)