FastPrep
Problem · Array

Sorted Absolute-Difference Sums Across Cyclic Shifts

Learn this problem
● MediumByteDance logoByteDanceNEW GRADOA

Problem statement

Given two integer arrays nums1 and nums2 of equal length n, consider every cyclic right shift of nums1.

For a shift of s positions, the value compared with nums2[i] is nums1[(i - s + n) % n]. Compute the sum of absolute pairwise differences for each shift s from 0 through n - 1.

Return all n sums sorted in nondecreasing order. Use 64-bit arithmetic for the differences and sums.

Function

sortedCyclicShiftDifferences(nums1: int[], nums2: int[]) → long[]

Examples

Example 1

nums1 = [1, 4, 2, 11]nums2 = [10, 1, 8, 4]return = [7, 13, 25, 25]

The four right shifts produce difference sums 25, 25, 13, and 7. Sorting them gives the returned array.

Example 2

nums1 = [1, 2]nums2 = [2, 1]return = [0, 2]

Without shifting, the sum is 2. Shifting right once produces [2, 1], whose sum is 0.

Constraints

  • 1 <= nums1.length == nums2.length <= 200
  • -10^9 <= nums1[i], nums2[i] <= 10^9

More ByteDance problems

drafts saved locally
public long[] sortedCyclicShiftDifferences(int[] nums1, int[] nums2) {
    // Write your code here.
}
nums1[1, 4, 2, 11]
nums2[10, 1, 8, 4]
expected[7, 13, 25, 25]
checking account