Leetcode Weekly Contest 476

Leetcode Weekly Contest 476

Thumbnail
https://lh3.googleusercontent.com/d/1_9_YsgknfnuXV0mzzZlBF_VCWpcMfkKy=w2480?authuser=0
Author
Anuj Joshi
Tags
Leetcode
Contest
Category
Blog
Project
Published
August 30, 2025
Contest - LeetCode
LeetCode hosts coding contests regularly, including weekly contests and specialized events like university coding competitions.
Contest - LeetCode
https://leetcode.com/contest/weekly-contest-477/
Contest - LeetCode
Weekly Contest 477 revolves heavily around prefix sums, prefix XOR, and efficient suffix extraction techniques such as difference arrays and modulus arithmetic.
This guide covers all prerequisite concepts followed by clear solutions to the three contest problems, including constraints, hints, and example test cases to ensure complete understanding.

Prerequisites

Prefix sums are widely used in competitive programming to reduce the time complexity for handling multiple range-based operations.

2D Prefix Sum

Concatenate non-zero digits and multiply Sum I

Concatenate Non-Zero Digits and Multiply by Sum I - LeetCode
Can you solve this real interview question? Concatenate Non-Zero Digits and Multiply by Sum I - You are given an integer n. Form a new integer x by concatenating all the non-zero digits of n in their original order. If there are no non-zero digits, x = 0. Let sum be the sum of digits in x. Return an integer representing the value of x * sum.   Example 1: Input: n = 10203004 Output: 12340 Explanation: * The non-zero digits are 1, 2, 3, and 4. Thus, x = 1234. * The sum of digits is sum = 1 + 2 + 3 + 4 = 10. * Therefore, the answer is x * sum = 1234 * 10 = 12340. Example 2: Input: n = 1000 Output: 1 Explanation: * The non-zero digit is 1, so x = 1 and sum = 1. * Therefore, the answer is x * sum = 1 * 1 = 1.   Constraints: * 0 <= n <= 109
Concatenate Non-Zero Digits and Multiply by Sum I - LeetCode
https://leetcode.com/problems/concatenate-non-zero-digits-and-multiply-by-sum-i/
Concatenate Non-Zero Digits and Multiply by Sum I - LeetCode
You are given an integer n. Form a new integer x by concatenating all the non-zero digits of n in their original order. Then, compute x * (sum of digits in x) If no non-zero digits exist, x = 0.

Constraints

0 ≤ n ≤ 10^9
Input
Output
Explanation
10203004
12340
x=1234, sum=10 → 1234×10
1000
1
x=1, sum=1
0
0
No digits
909
162
x=99, sum=18 → 99×18

Hint

Track two variables, sum and nonZero, for collecting the non-zero digits and computing their sum.

Code

class Solution {
public:
    long long sumAndMultiply(int n) {
        string s = to_string(n);
        long long sum = 0, nonZero = 0;

        for(char c : s) {
            int num = c - '0';
            if(num != 0) {
                nonZero = nonZero * 10 + num;
                sum += num;
            }
        }
        return nonZero * sum;
    }
};

Complexity

  • Time: O(N)
  • Space: O(1)

Find the maximum balanced xor subarray length

Find Maximum Balanced XOR Subarray Length - LeetCode
Can you solve this real interview question? Find Maximum Balanced XOR Subarray Length - Given an integer array nums, return the length of the longest subarray that has a bitwise XOR of zero and contains an equal number of even and odd numbers. If no such subarray exists, return 0.   Example 1: Input: nums = [3,1,3,2,0] Output: 4 Explanation: The subarray [1, 3, 2, 0] has bitwise XOR 1 XOR 3 XOR 2 XOR 0 = 0 and contains 2 even and 2 odd numbers. Example 2: Input: nums = [3,2,8,5,4,14,9,15] Output: 8 Explanation: The whole array has bitwise XOR 0 and contains 4 even and 4 odd numbers. Example 3: Input: nums = [0] Output: 0 Explanation: No non-empty subarray satisfies both conditions.   Constraints: * 1 <= nums.length <= 105 * 0 <= nums[i] <= 109
Find Maximum Balanced XOR Subarray Length - LeetCode
https://leetcode.com/problems/find-maximum-balanced-xor-subarray-length/
Find Maximum Balanced XOR Subarray Length - LeetCode
Given an array, return the length of the longest subarray such that: XOR of all elements = 0 and the number of even and odd elements is equal

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • 0 ≤ nums[i] ≤ 10^9
Input
Output
Explanation
[3,1,3,2,0]
4
[1,3,2,0] works
[3,2,8,5,4,14,9,15]
8
Full array valid
[0]
0
No valid subarray
[1,2,3,4]
2
[1,2] works

Hint

Track two prefix metrics: pxor = prefix XOR and diff = (#odd - #even)
Store the earliest index of each (pxor, diff) pair in a HashMap.

Code

class Solution {
public:
    int maxBalancedSubarray(vector<int>& nums) {
		    int n = nums.size();
        map<pair<int,int>, int> mp;

        int xr = 0, cnt = 0, res = 0;
        mp[{0,0}] = -1;

        for (int i = 0; i < n; i++) {
            xr ^= nums[i];
            if (nums[i]&1) cnt++;
            else cnt--;
            pair<int,int> key = {xr, cnt};
            if (mp.count(key)) res = max(res, i - mp[key]);
            else mp[key] = i;
        }
        return res;
    }
};

Complexity

  • Time: O(N)
  • Space: O(N)

Concatenate non-zero digits and multiply sum II

Concatenate Non-Zero Digits and Multiply by Sum II - LeetCode
Can you solve this real interview question? Concatenate Non-Zero Digits and Multiply by Sum II - You are given a string s of length m consisting of digits. You are also given a 2D integer array queries, where queries[i] = [li, ri]. For each queries[i], extract the substring s[li..ri]. Then, perform the following: * Form a new integer x by concatenating all the non-zero digits from the substring in their original order. If there are no non-zero digits, x = 0. * Let sum be the sum of digits in x. The answer is x * sum. Return an array of integers answer where answer[i] is the answer to the ith query. Since the answers may be very large, return them modulo 109 + 7.   Example 1: Input: s = "10203004", queries = [[0,7],[1,3],[4,6]] Output: [12340, 4, 9] Explanation: * s[0..7] = "10203004" * x = 1234 * sum = 1 + 2 + 3 + 4 = 10 * Therefore, answer is 1234 * 10 = 12340. * s[1..3] = "020" * x = 2 * sum = 2 * Therefore, the answer is 2 * 2 = 4. * s[4..6] = "300" * x = 3 * sum = 3 * Therefore, the answer is 3 * 3 = 9. Example 2: Input: s = "1000", queries = [[0,3],[1,1]] Output: [1, 0] Explanation: * s[0..3] = "1000" * x = 1 * sum = 1 * Therefore, the answer is 1 * 1 = 1. * s[1..1] = "0" * x = 0 * sum = 0 * Therefore, the answer is 0 * 0 = 0. Example 3: Input: s = "9876543210", queries = [[0,9]] Output: [444444137] Explanation: * s[0..9] = "9876543210" * x = 987654321 * sum = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 * Therefore, the answer is 987654321 * 45 = 44444444445. * We return 44444444445 modulo (109 + 7) = 444444137.   Constraints: * 1 <= m == s.length <= 105 * s consists of digits only. * 1 <= queries.length <= 105 * queries[i] = [li, ri] * 0 <= li <= ri < m
Concatenate Non-Zero Digits and Multiply by Sum II - LeetCode
https://leetcode.com/problems/concatenate-non-zero-digits-and-multiply-by-sum-ii/
Concatenate Non-Zero Digits and Multiply by Sum II - LeetCode
Given a digit string s and multiple queries (l, r):
  1. Extract substring s[l..r]
  1. Concatenate non-zero digits → x
  1. Compute sum of digits in x
  1. Return (x * sum) mod (1e9+7)

Constraints

  • 1 ≤ s.length ≤ 10^5
  • 1 ≤ queries.length ≤ 10^5
  • Output modulo 1e9 + 7
Input
Output
"10203004", [[0,7],[1,3],[4,6]]
[12340,4,9]
"1000", [[0,3],[1,1]]
[1,0]
"9876543210", [[0,9]]
[444444137]
"00000", [[0,4]]
[0]

Hint

Use prefix arrays to track:
  • sum of non-zero digits
  • modular concatenation of digits
  • powers of 10
  • count of non-zero digits
Each query resolves in O(1).

Code

class Solution {
public:
    static const int MOD = 1e9 + 7;

    vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<long long> sum(n+1, 0), pref(n+1, 0), pow10(n+1);
        vector<int> prefLen(n+1, 0);

        pow10[0] = 1;

        for(int i = 0; i < n; i++) {
            pow10[i+1] = (pow10[i] * 10) % MOD;
            int d = s[i] - '0';

            sum[i+1] = sum[i];
            pref[i+1] = pref[i];
            prefLen[i+1] = prefLen[i];

            if(d != 0) {
                sum[i+1] += d;
                pref[i+1] = (pref[i] * 10 + d) % MOD;
                prefLen[i+1]++;
            }
        }

        vector<int> res;
        res.reserve(queries.size());

        for(auto &q : queries) {
            int l = q[0], r = q[1];
            long long total = sum[r+1] - sum[l];

            if(total == 0) {
                res.push_back(0);
                continue;
            }

            int len = prefLen[r+1] - prefLen[l];
            long long val = (pref[r+1] - (pref[l] * pow10[len]) % MOD + MOD) % MOD;

            res.push_back((val * total) % MOD);
        }

        return res;
    }
};

Complexity

  • Preprocessing: O(N)
  • Query: O(1)
  • Total: O(N + Q)