Skip to content

4062. Transform Array Using Pair Operations

DifficultyMedium

Description

You are given two integer arrays source and target.

In one operation, you may choose two distinct indices i and j in source, along with any integer delta. Then update source as follows:

  • source[i] = source[i] + source[j] - delta
  • source[j] = delta

Return true if it is possible to make source equal to target after performing the operation any (including zero) number of times. Otherwise, return false.

 

Example 1:

Input: source = [1,2,3], target = [0,2,4]

Output: true

Explanation:

  • Choose indices i = 0 and j = 2, and set delta = 4.
  • Before operation, source[0] = 1 and source[2] = 3.
  • After the operation,
    • source[0] = 1 + 3 - 4 = 0
    • source[2] = 4
  • Hence, source becomes [0, 2, 4], which is equal to target.
  • Therefore, the answer is true.

Example 2:

Input: source = [-5,-5], target = [-15,5]

Output: true

Explanation:

  • Choose indices i = 1 and j = 0, and set delta = -15.
  • Before operation, source[1] = -5 and source[0] = -5.
  • After the operation,
    • source[1] = -5 + (-5) - (-15) = 5
    • source[0] = -15
  • Hence, source becomes [-15, 5], which is equal to target.
  • Therefore, the answer is true.

Example 3:

Input: source = [1,2,1], target = [0,2,5]

Output: false

Explanation:

It can be shown that no matter what operations are performed, source can never be made equal to target. Therefore, the answer is false.

 

Constraints:

  • 2 <= source.length == target.length <= 105
  • -109 <= source[i], target[i] <= 109

Solutions

Solution 1: Compare Array Sums

Thinking

The arrays can have length \(10^5\), so searching through sequences of operations does not finish in time. One operation replaces \(\textit{source}[j]\) by an arbitrary integer \(\textit{delta}\) and adds \(\textit{source}[j]-\textit{delta}\) to \(\textit{source}[i]\). The two positions keep the same sum, and so does the whole array.

For \(n\ge 2\), equal sums are enough. Keep the last index as the partner and rewrite the first \(n-1\) entries to the corresponding \(\textit{target}\) values from left to right. The preserved total then forces the last entry to become \(\textit{target}[n-1]\).

It is enough to compare the two sums. Each value is at most \(10^9\) in absolute value and the length is at most \(10^5\), so the sum needs a \(64\)-bit integer.

One operation chooses distinct indices \(i\) and \(j\) together with an integer \(\textit{delta}\), replaces \(\textit{source}[i]\) by \(\textit{source}[i]+\textit{source}[j]-\textit{delta}\), and replaces \(\textit{source}[j]\) by \(\textit{delta}\). The two positions still add up to their old sum, so the array sum is unchanged. Different sums cannot be transformed into each other.

Equal sums can always be transformed. Index \(n-1\) stays the partner. For \(i=0,1,\ldots,n-2\), choose

\[ \textit{delta}=\textit{source}[i]+\textit{source}[n-1]-\textit{target}[i]. \]

After the operation, \(\textit{source}[i]=\textit{target}[i]\). Once the first \(n-1\) entries match \(\textit{target}\), the equal totals force the last entry to equal \(\textit{target}[n-1]\).

Accumulate the sum in a \(64\)-bit integer. The time complexity is \(O(n)\) and the space complexity is \(O(1)\).

1
2
3
class Solution:
    def canTransform(self, source: list[int], target: list[int]) -> bool:
        return sum(source) == sum(target)

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean canTransform(int[] source, int[] target) {
        long d = 0;
        for (int i = 0; i < source.length; ++i) {
            d += source[i] - target[i];
        }
        return d == 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    bool canTransform(vector<int>& source, vector<int>& target) {
        long long s = 0;
        for (int x : source) {
            s += x;
        }
        for (int x : target) {
            s -= x;
        }
        return s == 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func canTransform(source []int, target []int) bool {
    var s, t int64
    for _, x := range source {
        s += int64(x)
    }
    for _, x := range target {
        t += int64(x)
    }
    return s == t
}

1
2
3
4
5
function canTransform(source: number[], target: number[]): boolean {
    return (
        source.reduce((s, x) => s + BigInt(x), 0n) === target.reduce((s, x) => s + BigInt(x), 0n)
    );
}

Comments