Repeated Mirror XOR
Updated
Problem statement
You are given an integer array arr of length n and an integer k. Perform k steps, numbered 0 through k - 1.
In step i, let j = i % n. Replace arr[j] with arr[j] ^ arr[n - j - 1], where ^ is bitwise XOR. Each step uses the array as it is after all earlier steps.
Return the array after all k steps. Doing the steps one by one is too slow when k is large, so find a faster way.
Function
findFinalArray(arr: int[], k: long) → int[]Examples
Example 1
arr = [5,6,7,8]k = 3return = [13,1,6,8]Step 0 replaces arr[0] with 5 ^ 8 = 13. Step 1 replaces arr[1] with 6 ^ 7 = 1. Step 2 replaces arr[2] with 7 ^ 1 = 6, using the new value at index 1. Index 3 is not reached.
Example 2
arr = [6,1,9]k = 7return = [6,0,15]The steps visit indices 0, 1, 2, 0, 1, 2, 0. Index 1 is its own mirror, so its first step gives 1 ^ 1 = 0 and it stays 0. Indices 0 and 2 go through [15, 9], [15, 6], [9, 6], [9, 15], and finally [6, 15].
Example 3
arr = [1,2]k = 2return = [3,1]Step 0 sets arr[0] = 1 ^ 2 = 3. Step 1 sets arr[1] = 2 ^ 3 = 1.
Example 4
arr = [5,6,7,8]k = 1000000000000return = [13,1,6,5]The pair at indices 0 and 3 and the pair at indices 1 and 2 each return to their starting values every 3 rounds of 4 steps, so only 10^12 mod 12 = 4 steps matter. Four steps from the start give [13, 1, 6, 8] after the first three, and then arr[3] = 8 ^ 13 = 5.
Constraints
1 <= arr.length <= 10^51 <= arr[i] <= 10^71 <= k <= 10^12
Source note: Photos of the original assessment screen, in order: the statement with the worked example, the function description and limits, and the two samples. Margins were cropped and a forum watermark in empty background was covered.
More MathWorks Online Assessment questions
- Earliest Time to Schedule a MeetingOA · Seen Nov 2026
- Minimum Cost to Serve Requests on a RingOA · Seen Nov 2026
- Minimum Tree Diameter After Removing K LeavesOA · Seen Nov 2026
- Cities on Shortest Delivery RoutesOA · Seen Nov 2026
- Balancing TeamsOA · Seen Nov 2025
- Largest Sub-GridOA · Seen Nov 2025
- Discount TagsOA · Seen Oct 2024
- Odd One OutOA · Seen Oct 2024
- Alloy ProductionOA · Seen Sep 2024
- Has VowelsOA · Seen Sep 2024
Similar questions at other companies
- Capping Portfolio WeightsCapstone Investment Advisors · OA
- Count Subarrays with a Perfect-Square ProductMicrosoft · OAMicrosoft interview questions
- Stacked Item and Category DiscountsPalantir · OAPalantir interview questions
- Minimum Power-of-Two Removal OperationsIBM · OAIBM interview questions
- Macaron Order PriceOpenAI · OAOpenAI interview questions
- Daily Settlement for Long and Short PositionsBelvedere Trading · OA
- Minimum Power-of-Two Removal OperationsVisa · OAVisa interview questions
- Prime Factor VisitationMaven Securities · OAMaven Securities interview questions
- Proportional Momentum Investment StatisticsOptiver · OAOptiver interview questions
- Sort an Array with Rotate and FlipAmazon · OA