FastPrepRepeated Mirror XOR

Repeated Mirror XOR

MathWorks logoMathWorks● MediumNEW GRADOA

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^5
  • 1 <= arr[i] <= 10^7
  • 1 <= 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

Similar questions at other companies

Interview reports that mention this question

MathWorks interview experiences

All MathWorks interview questionsSee MathWorks hiring insights
Saved
class Solution {
    public int[] findFinalArray(int[] arr, long k) {
        // Write your code here.
    }
}
Checking account…