Code in cpp

Question

Code in cpp

Answer 1

Here’s a clean C++ solution for “Minimum Absolute Distance Between Mirror Pairs”:

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Reverse digits of a non-negative integer, dropping leading zeros
    int reverseNum(int x) {
        int rev = 0;
        while (x > 0) {
            rev = rev * 10 + (x % 10);
            x /= 10;
        }
        return rev;
    }

    int minMirrorPairDistance(vector<int>& nums) {
        unordered_map<int,int> lastIndexOfReversed; // value -> last index i with reverse(nums[i]) == value
        int n = nums.size();
        int ans = INT_MAX;

        for (int i = 0; i < n; ++i) {
            // Treat current i as j in (i_prev, i):
            // need reverse(nums[i_prev]) == nums[i]  <=>  nums[i] is in map
            auto it = lastIndexOfReversed.find(nums[i]);
            if (it != lastIndexOfReversed.end()) {
                ans = min(ans, i - it->second);   // i > it->second always
            }

            // Now treat current index as the "i" of future pairs
            int r = reverseNum(nums[i]);
            lastIndexOfReversed[r] = i;  // keep closest (largest) index
        }

        return ans == INT_MAX ? -1 : ans;
    }
};

Idea in one line:
Scan from left to right, keep for each value v the last index where reverse(nums[index]) == v; when at position i, if nums[i] is already in the map, we’ve found a mirror pair ending at i, and we update the minimum distance.

Answer 2

Here’s a C++ solution for “Q4. Minimum Operations to Equalize Subarrays”.

Idea in short:

For a subarray [l, r] to be equalizable using ±k:
- All elements must be congruent modulo k.
If they are, write each nums[i] = k * q[i] + rem (same rem).
- Operations needed on nums[i] to reach target T = k * t + rem is |q[i] - t|.
- So we just need to make the q[i]’s equal, and the minimum sum of |q[i] - t| is achieved at the median of q[i].
Thus, for each query:
1. Check that all nums[l..r] have the same remainder modulo k.
  (Using a prefix array over “remainder changes”.)
2. If yes, compute sum of absolute deviations from median of q[i] = (nums[i] - rem)/k in that range.
3. To do this fast for many queries, use a persistent segment tree over the q[i] values:
  - supports k-th smallest (median) and range sum over [l, r] in O(log n).

Complexities:

Build: O(n log n)
Each query: O(log n)

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    struct Node {
        int l = 0, r = 0;   // children indices in seg
        int cnt = 0;        // how many numbers in this range
        long long sum = 0;  // sum of numbers in this range
    };

    vector<Node> seg;       // persistent segment tree nodes
    int M;                  // number of distinct q-values

    // Build/update: return new root index based on previous root
    int update(int prev, int s, int e, int pos, long long val) {
        int cur = (int)seg.size();
        seg.push_back(seg[prev]);      // clone previous node

        if (s == e) {
            seg[cur].cnt += 1;
            seg[cur].sum += val;
            return cur;
        }

        int mid = (s + e) >> 1;
        if (pos <= mid) {
            int newL = update(seg[prev].l, s, mid, pos, val);
            seg[cur].l = newL;
        } else {
            int newR = update(seg[prev].r, mid + 1, e, pos, val);
            seg[cur].r = newR;
        }

        seg[cur].cnt = seg[seg[cur].l].cnt + seg[seg[cur].r].cnt;
        seg[cur].sum = seg[seg[cur].l].sum + seg[seg[cur].r].sum;
        return cur;
    }

    // k-th smallest value index in range using roots u (R) and v (L-1)
    int kth(int u, int v, int s, int e, int k) {
        if (s == e) return s;
        int lu = seg[u].l, ru = seg[u].r;
        int lv = seg[v].l, rv = seg[v].r;

        int leftCnt = seg[lu].cnt - seg[lv].cnt;
        int mid = (s + e) >> 1;

        if (k <= leftCnt) return kth(lu, lv, s, mid, k);
        return kth(ru, rv, mid + 1, e, k - leftCnt);
    }

    // (count, sum) of values whose indices are within [L, R]
    pair<long long,long long> rangeQuery(int u, int v, int s, int e, int L, int R) {
        if (R < s || e < L) return {0, 0};
        if (L <= s && e <= R) {
            long long cnt = seg[u].cnt - seg[v].cnt;
            long long sum = seg[u].sum - seg[v].sum;
            return {cnt, sum};
        }
        int mid = (s + e) >> 1;
        auto left  = rangeQuery(seg[u].l, seg[v].l, s, mid, L, R);
        auto right = rangeQuery(seg[u].r, seg[v].r, mid + 1, e, L, R);
        return {left.first + right.first, left.second + right.second};
    }

    vector<long long> minOperationsToEqualizeSubarrays(vector<int>& nums,
                                                       int k,
                                                       vector<vector<int>>& queries) {
        int n = (int)nums.size();
        vector<long long> ans(queries.size());

        // Special case k == 0: elements cannot change at all
        if (k == 0) {
            if (n == 0) return ans;
            vector<int> prefBad(n, 0);
            for (int i = 1; i < n; ++i) {
                prefBad[i] = prefBad[i - 1] + (nums[i] != nums[i - 1]);
            }
            for (int qi = 0; qi < (int)queries.size(); ++qi) {
                int l = queries[qi][0];
                int r = queries[qi][1];
                if (prefBad[r] - prefBad[l] > 0) ans[qi] = -1;
                else ans[qi] = 0;
            }
            return ans;
        }

        long long kk = llabs((long long)k);   // make step positive

        // rem[i] = nums[i] mod k (normalized to [0, kk-1])
        // q[i] = (nums[i] - rem[i]) / k
        vector<int> rem(n);
        vector<long long> q(n);
        for (int i = 0; i < n; ++i) {
            long long v = nums[i];
            long long mod = v % kk;
            if (mod < 0) mod += kk;           // normalize
            rem[i] = (int)mod;
            q[i] = (v - mod) / kk;
        }

        // prefix array that counts transitions of remainder
        // if any rem changes inside [l, r], impossible
        vector<int> prefBad(n, 0);
        for (int i = 1; i < n; ++i) {
            prefBad[i] = prefBad[i - 1] + (rem[i] != rem[i - 1]);
        }

        // Coordinate-compress q-values
        vector<long long> vals = q;
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        M = (int)vals.size();

        vector<int> pos(n);
        for (int i = 0; i < n; ++i) {
            pos[i] = int(lower_bound(vals.begin(), vals.end(), q[i]) - vals.begin()) + 1; // 1-based
        }

        // Build persistent segment tree over q
        seg.clear();
        seg.reserve((n + 5) * 20);            // rough upper bound
        seg.push_back(Node());                // node 0: empty

        vector<int> root(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            root[i] = update(root[i - 1], 1, M, pos[i - 1], q[i - 1]);
        }

        // Answer queries
        for (int qi = 0; qi < (int)queries.size(); ++qi) {
            int l = queries[qi][0];
            int r = queries[qi][1];

            // Check all nums[l..r] ≡ same (mod k)
            if (prefBad[r] - prefBad[l] > 0) {
                ans[qi] = -1;
                continue;
            }

            int len = r - l + 1;
            if (len == 1) {       // single element already equal
                ans[qi] = 0;
                continue;
            }

            int kpos = (len + 1) / 2;         // position of lower median
            int rootR = root[r + 1];
            int rootL = root[l];

            // find index of median in compressed coords
            int idxMed = kth(rootR, rootL, 1, M, kpos);
            long long medVal = vals[idxMed - 1];

            // sum & count of elements <= median
            auto left = rangeQuery(rootR, rootL, 1, M, 1, idxMed);
            long long cntLeft = left.first;
            long long sumLeft = left.second;

            // total sum & count in [l, r]
            auto whole = rangeQuery(rootR, rootL, 1, M, 1, M);
            long long cntTotal = whole.first;   // should equal len
            long long sumTotal = whole.second;

            long long cntRight = cntTotal - cntLeft;
            long long sumRight = sumTotal - sumLeft;

            long long cost =
                medVal * cntLeft - sumLeft +
                sumRight - medVal * cntRight;

            ans[qi] = cost;
        }

        return ans;
    }
};

You can drop this straight into the LeetCode editor and just adjust the function name/signature if their stub is slightly different.

問題

思考

Rethinking approach for C++ solution

Optimizing approach with index mapping

Approach to finding mirror pairs efficiently

Implementing safe reverseNum function and considerations

Considering mirrored pairs and implementing the solution

Refining code and confirming logic for mirror pairs

Reevaluating mirror pair check for edge cases

Reevaluating approach to mirror pair checking

Refining algorithm with pair checks

回答

問題

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

思考

Finalizing C++ code considerations

Verifying median cost logic

Converting algorithm to C++

Converting pseudo code to C++

Planning out the C++ implementation

Handling edge cases for k and overflow

Ensuring no division by zero and handling k == 0

回答

分享這個問答

Handling edge cases for `k` and overflow