Array Reduction: Possible Final Positions
Updated
Problem statement
Start with positive nums values in distinct positions. Choose any two currently positive entries a and b. You may replace a by a+b and mark b removed only when 2*a >= b; symmetrically, you may keep the sum at b only when 2*b >= a. Continue until one position remains positive.
Count the distinct original positions that can hold the final positive value under some valid sequence. Different operation orders with the same final position count once. Equal initial values in different positions remain distinct possibilities.
Function
finalPositions(nums: int[]) → intExamples
Example 1
nums = [1,10]return = 1Only the position initially holding 10 can survive.
Example 2
nums = [1,4,10]return = 2The 4 can absorb 1, then 10; the 10 can also survive, while the 1 cannot absorb 4.
Constraints
- For this exercise, assume 1 <= nums.length <= 200000 and 1 <= nums[i] <= 10^9. Use 64-bit intermediate sums.
More Intuit Online Assessment questions
- Employee Promotion OpportunitiesOA · Seen Oct 2026
- Next Pascal Row CoefficientOA · Seen Oct 2026
- Parse Router LogsOA · Seen Oct 2026
- Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
- Maximum Square-Free DivisorOA · Seen Oct 2026
- Two Tribes from Taller-Person CountsOA · Seen Oct 2026
- Shortest Path from an Encoded GraphOA · Seen Sep 2026
- Oldest and Youngest EmployeesOA · Seen Sep 2026
- Pressure-Isolation Shutdown OrderOA · Seen Sep 2026
- Submask Sum QueriesOA · Seen Sep 2026
Similar questions at other companies
- Find Minimum TimeAlphaSense · OA
- Find Minimum TimeBlackRock · OABlackRock interview questions
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Minimum Cost of Every K-Capable Model SetTikTok · OATikTok interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Minimum Distinct Prefix CostGoldman Sachs · OAGoldman Sachs interview questions
- Maximum Alternating-Index Packet ValueInfosys · OAInfosys interview questions
- Maximize Minimum Deployment DifficultyJP Morgan Chase · OAJP Morgan Chase interview questions