DEV Community: MD ARIFUL HAQUE

3312. Sorted GCD Pair Queries

MD ARIFUL HAQUE — Fri, 17 Jul 2026 14:19:54 +0000

3312. Sorted GCD Pair Queries

Difficulty: Hard

Topics: Principal, Array, Hash Table, Math, Binary Search, Combinatorics, Counting, Number Theory, Prefix Sum, Weekly Contest 418

You are given an integer array nums of length n and an integer array queries.

Let gcdPairs denote an array obtained by calculating the GCD¹ of all possible pairs (nums[i], nums[j]), where 0 <= i < j < n, and then sorting these values in ascending order.

For each query queries[i], you need to find the element at index queries[i] in gcdPairs.

Return an integer array answer, where answer[i] is the value at gcdPairs[queries[i]] for each query.

The term gcd(a, b) denotes the greatest common divisor of a and b.

Example 1:

Input: nums = [2,3,4], queries = [0,2,2]
Output: [1,2,2]
Explanation:
- gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])] = [1, 2, 1].
- After sorting in ascending order, gcdPairs = [1, 1, 2].
- So, the answer is [gcdPairs[queries[0]], gcdPairs[queries[1]], gcdPairs[queries[2]]] = [1, 2, 2].

Example 2:

Input: nums = [4,4,2,1], queries = [5,3,1,0]
Output: [4,2,1,1]
Explanation: gcdPairs sorted in ascending order is [1, 1, 1, 2, 2, 4].

Example 3:

Input: nums = [2,2], queries = [0,0]
Output: [2,2]
Explanation: gcdPairs = [2].

Example 4:

Input: nums = [6,17,1,10], queries = [5,2,3,1,4,0]
Output: [2,1,1,1,1,1]

Example 5:

Input: nums = [5,5,5,5], queries = [0,3,5]
Output: [5,5,5]

Example 6:

Input: nums = [1,50000,2,49999], queries = [0,5]
Output: [1,1]

Example 7:

Input: nums = [1,2,3,4,5], queries = [0,9]
Output: [1,2]

Example 8:

Input: nums = [6,6,10,15,15], queries = [2,5,8]
Output: [3,5,6]

Example 9:

Input: nums = [6,12,18,24], queries = [0,5]
Output: [6,6]

Constraints:

2 <= n == nums.length <= 10⁵
1 <= nums[i] <= 5 * 10⁴
1 <= queries.length <= 10⁵
0 <= queries[i] < n * (n - 1) / 2

Hint:

Try counting the number of pairs that have a GCD of g
Use inclusion-exclusion.

Solution:

We have implemented an efficient solution for the "Sorted GCD Pair Queries" problem that processes up to 100,000 numbers and queries. Our approach avoids generating all GCD pairs explicitly (which would be O(n²) and infeasible), instead using number theory and prefix sums to answer queries in O(M log M + Q log M) time, where M is the maximum value in nums (≤ 50,000).

Approach

Frequency Counting: Count occurrences of each number in nums using an array indexed by value up to max(nums)
Multiples Counting: For each possible GCD value d, count how many numbers in nums are divisible by d using a sieve-like approach
Total Pairs per Multiple: Calculate the total number of pairs where both numbers are divisible by d using combinatorial formula C(cnt, 2)
Inclusion-Exclusion: Compute exact GCD counts by iterating from largest to smallest value, subtracting multiples' exact GCD counts from the total pairs divisible by d
Prefix Sum Building: Create a prefix sum array to represent cumulative counts of pairs by GCD value
Binary Search for Queries: For each query, find the smallest GCD value where the cumulative count exceeds the query index

Let's implement this solution in PHP: 3312. Sorted GCD Pair Queries

<?php
/**
 * @param Integer[] $nums
 * @param Integer[] $queries
 * @return Integer[]
 */
function gcdValues(array $nums, array $queries): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo gcdValues([2,3,4], [0,2,2]) .  "\n";                   // Output: [1,2,2]
echo gcdValues([4,4,2,1], [5,3,1,0]) .  "\n";               // Output: [4,2,1,1]
echo gcdValues([2,2], [0,0]) .  "\n";                       // Output: [2,2]
echo gcdValues([6,17,1,10], [5,2,3,1,4,0]) .  "\n";         // Output: [2,1,1,1,1,1]
echo gcdValues([5,5,5,5], [0,3,5]) .  "\n";                 // Output: [5,5,5]
echo gcdValues([1,50000,2,49999], [0,5]) .  "\n";           // Output: [1,1]
echo gcdValues([1,2,3,4,5], [0,9]) .  "\n";                 // Output: [1,2]
echo gcdValues([6,6,10,15,15], [2,5,8]) .  "\n";            // Output: [3,5,6]
echo gcdValues([6,12,18,24], [0,5]) .  "\n";                // Output: [6,6]
?>

Explanation:

Key Insight: Instead of computing all O(n²) GCD pairs, we count how many pairs have each possible GCD value using inclusion-exclusion principle
Sieve Optimization: The multiples counting uses a harmonic series approach, taking O(M log M) time where M is the maximum value
Inclusion-Exclusion Mechanism: For each d, totalPairsMultiple[d] counts pairs where gcd is a multiple of d. By subtracting exactGCD[2d], exactGCD[3d], etc., we isolate pairs with exact gcd = d
Sorting Implicit: Since we count GCD values in ascending order and build prefix sums, we can binary search to find which GCD value corresponds to each query index
Memory Efficiency: We use O(M) space where M ≤ 50,000, making this feasible even for large inputs
Handling Edge Cases: The solution correctly handles duplicate numbers, single-pair cases (n=2), and queries that may point to the same index

Complexity Analysis

Time Complexity: O(M log M + Q log M) where M = max(nums) ≤ 50,000 and Q = len(queries) ≤ 100,000
- Multiples counting: O(M log M) due to harmonic series
- Inclusion-exclusion: O(M log M)
- Binary search per query: O(Q log M)
Space Complexity: O(M) for frequency arrays, multiples count, total pairs, exact GCD, and prefix sum arrays

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

GCD: The term gcd(a, b) denotes the greatest common divisor of a and b. ↩

3867. Sum of GCD of Formed Pairs

MD ARIFUL HAQUE — Thu, 16 Jul 2026 16:49:22 +0000

3867. Sum of GCD of Formed Pairs

Difficulty: Medium

Topics: Senior, Array, Math, Two Pointers, Sorting, Simulation, Number Theory, Biweekly Contest 178

You are given an integer array nums of length n.

Construct an array prefixGcd where for each index i:

Let mxᵢ = max(nums[0], nums[1], ..., nums[i]).
prefixGcd[i] = gcd(nums[i], mxᵢ).

After constructing prefixGcd:

Sort prefixGcd in non-decreasing order.
Form pairs by taking the smallest unpaired element and the largest unpaired element.
Repeat this process until no more pairs can be formed.
For each formed pair, compute the gcd of the two elements.
If n is odd, the middle element in the prefixGcd array remains unpaired and should be ignored.

Return an integer denoting the sum of the GCD values of all formed pairs.
The term gcd(a, b) denotes the greatest common divisor of a and b.

Example 1:

Input: nums = [2,6,4]
Output: 2
Explanation:
- Construct prefixGcd:

`i`	`nums[i]`	`mxᵢ`	`prefixGcd[i]`
0	2	2	2
1	6	6	6
2	4	6	2

prefixGcd = [2, 6, 2]. After sorting, it forms [2, 2, 6].
Pair the smallest and largest elements: gcd(2, 6) = 2. The remaining middle element 2 is ignored. Thus, the sum is 2.

Example 2:

Input: nums = [3,6,2,8]
Output: 5
Explanation:
- Construct prefixGcd:

`i`	`nums[i]`	`mxᵢ`	`prefixGcd[i]`
0	3	3	3
1	6	6	6
2	2	6	2
3	8	8	8

prefixGcd = [3, 6, 2, 8]. After sorting, it forms [2, 3, 6, 8].
Form pairs: gcd(2, 8) = 2 and gcd(3, 6) = 3. Thus, the sum is 2 + 3 = 5.

Example 3:

Input: nums =[5,5,5]
Output: 5

Example 4:

Input: nums = [7]
Output: 0

Example 5:

Input: nums = [1,2,3,4]
Output: 2

Example 6:

Input: nums = [1000000000, 999999937, 1000000000]
Output: 1

Example 7:

Input: nums = [1,1,1,1]
Output: 2

Constraints:

1 <= n == nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Hint:

Maintain a running prefix maximum mxᵢ while iterating nums to compute prefixGcd[i] = gcd(nums[i], mxᵢ).
Sort prefixGcd in non-decreasing order.
Form pairs by combining the smallest unpaired and largest unpaired elements.
Compute gcd for each pair and sum them; ignore middle element if n is odd.

Solution:

We implemented a solution that constructs the prefixGcd array by maintaining a running maximum and computing GCDs, then sorts the array and pairs the smallest with the largest to sum their GCDs, ignoring the middle element when n is odd. This approach runs in O(n log n) time and uses O(n) extra space.

Approach

Iterate through the array while maintaining the maximum value seen so far.
For each index, compute the GCD of the current number and the current maximum, and store it in prefixGcd.
Sort prefixGcd in non‑decreasing order.
Use two pointers (left and right) to pair the smallest unpaired element with the largest unpaired element.
For each pair, compute the GCD and add it to the total sum.
If n is odd, the middle element is automatically ignored because the loop stops when left < right.

Let's implement this solution in PHP: 3867. Sum of GCD of Formed Pairs

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function gcdSum(array $nums): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper GCD function
 *
 * @param $a
 * @param $b
 * @return int|mixed
 */
function gcd($a, $b): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo gcdSum([2,6,4]) .  "\n";                                   // Output: 2
echo gcdSum([3,6,2,8]) .  "\n";                                 // Output: 5
echo gcdSum([5,5,5]) .  "\n";                                   // Output: 5
echo gcdSum([7]) .  "\n";                                       // Output: 0
echo gcdSum([1,2,3,4]) .  "\n";                                 // Output: 2
echo gcdSum([1000000000, 999999937, 1000000000]) .  "\n";       // Output: 1
echo gcdSum([1,1,1,1]) .  "\n";                                 // Output: 2
?>

Explanation:

Step 1 – Build prefixGcd:
- Maintain mx as the maximum value from nums[0] to nums[i].
- Compute gcd(nums[i], mx) and push it into the prefixGcd array.
Step 2 – Sort:
- Sorting ensures that the smallest and largest elements are accessible via two pointers.
Step 3 – Pairing and Summing:
- Initialize left = 0 and right = n - 1.
- While left < right:
  - Compute gcd(prefixGcd[left], prefixGcd[right]).
  - Add the result to sum.
  - Move left forward and right backward.
- When n is odd, the middle element (at left == right) is never processed, so it’s ignored as required.
GCD Helper:
- Use the Euclidean algorithm (iterative) to compute GCD efficiently.

Complexity Analysis

Time Complexity:
- Building prefixGcd: O(n)
- Sorting: O(n log n)
- Pairing: O(n)
- Overall: O(n log n)
Space Complexity:
- O(n) for storing prefixGcd.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3658. GCD of Odd and Even Sums

MD ARIFUL HAQUE — Wed, 15 Jul 2026 16:45:27 +0000

3658. GCD of Odd and Even Sums

Difficulty: Easy

Topics: Mid Level, Math, Number Theory, Weekly Contest 464

You are given an integer n. Your task is to compute the GCD (greatest common divisor) of two values:

sumOdd: the sum of the smallest n positive odd numbers.
sumEven: the sum of the smallest n positive even numbers.

Return the GCD of sumOdd and sumEven.

Example 1:

Input: n = 4
Output: 4
Explanation:
- Sum of the first 4 odd numbers sumOdd = 1 + 3 + 5 + 7 = 16
- Sum of the first 4 even numbers sumEven = 2 + 4 + 6 + 8 = 20
- Hence, GCD(sumOdd, sumEven) = GCD(16, 20) = 4.

Example 2:

Input: n = 5
Output: 5
Explanation:
- Sum of the first 5 odd numbers sumOdd = 1 + 3 + 5 + 7 + 9 = 25
- Sum of the first 5 even numbers sumEven = 2 + 4 + 6 + 8 + 10 = 30
- Hence, GCD(sumOdd, sumEven) = GCD(25, 30) = 5.

Example 3:

Input: n = 1
Output: 1

Example 4:

Input: n = 2
Output: 2

Example 5:

Input: n = 3
Output: 3

Example 6:

Input: n = 10
Output: 10

Example 7:

Input: n = 100
Output: 100

Example 8:

Input: n = 1000
Output: 1000

Constraints:

1 <= n <= 1000

Hint:

The first n odd numbers sum to n * n
First n even numbers sum to n * (n + 1)
gcd(n, n + 1) = 1, so the answer is n

Solution:

We solved the problem by recognizing that the GCD of the sum of the first n odd numbers and the sum of the first n even numbers simplifies directly to n. We identified that sumOdd = n² and sumEven = n(n+1), and since n and n+1 are consecutive integers (always coprime), their GCD is 1. Therefore, the answer is simply n, making the solution O(1) time and space complexity.

Approach

Identify the formulas for the sum of the first n odd and even numbers
Recognize that sumOdd = n² and sumEven = n(n+1)
Apply GCD properties: gcd(n², n(n+1)) = n × gcd(n, n+1)
Use the fact that consecutive integers are always coprime: gcd(n, n+1) = 1
Simplify to get the answer: n × 1 = n
Return n directly without computing large sums

Let's implement this solution in PHP: 3658. GCD of Odd and Even Sums

<?php
/**
 * @param Integer $n
 * @return Integer
 */
function gcdOfOddEvenSums(int $n): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo gcdOfOddEvenSums(4) .  "\n";       // Output: 4
echo gcdOfOddEvenSums(5) .  "\n";       // Output: 5
echo gcdOfOddEvenSums(1) .  "\n";       // Output: 1
echo gcdOfOddEvenSums(2) .  "\n";       // Output: 2
echo gcdOfOddEvenSums(3) .  "\n";       // Output: 3
echo gcdOfOddEvenSums(10) .  "\n";      // Output: 10
echo gcdOfOddEvenSums(100) .  "\n";     // Output: 100
echo gcdOfOddEvenSums(1000) .  "\n";    // Output: 1000
?>

Explanation:

Sum of first n odd numbers: The sequence is 1, 3, 5, ..., (2n-1). The sum formula is n²
Sum of first n even numbers: The sequence is 2, 4, 6, ..., 2n. The sum formula is n(n+1)
GCD calculation: We need gcd(n², n(n+1))
Factor out n: n × gcd(n, n+1) since both terms share a factor of n
Consecutive property: n and n+1 have no common factors other than 1
Final result: n × 1 = n, which matches all test cases
Optimization: No loops or array storage needed; the answer is always the input n

Complexity Analysis

Time Complexity: O(1) - constant time operation, regardless of input size
Space Complexity: O(1) - no additional memory allocation required

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3336. Find the Number of Subsequences With Equal GCD

MD ARIFUL HAQUE — Wed, 15 Jul 2026 16:40:09 +0000

3336. Find the Number of Subsequences With Equal GCD

Difficulty: Hard

Topics: Senior Staff, Array, Math, Dynamic Programming, Number Theory, Weekly Contest 421

You are given an integer array nums.

Your task is to find the number of pairs of non-empty subsequences¹ (seq1, seq2) of nums that satisfy the following conditions:

The subsequences seq1 and seq2 are disjoint, meaning no index of nums is common between them.
The GCD² of the elements of seq1 is equal to the GCD of the elements of seq2.

Return the total number of such pairs.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [1,2,3,4]
Output: 10
Explanation:
- The subsequence pairs which have the GCD of their elements equal to 1 are:
- ([1, 2, 3, 4], [1, 2, 3, 4])
- ([1, 2, 3, 4], [1, 2, 3, 4])
- ([1, 2, 3, 4], [1, 2, 3, 4])
- ([1, 2, 3, 4], [1, 2, 3, 4])
- ([1, 2, 3, 4], [1, 2, 3, 4])
- ([1, 2, 3, 4], [1, 2, 3, 4])
- ([1, 2, 3, 4], [1, 2, 3, 4])
- ([1, 2, 3, 4], [1, 2, 3, 4])
- ([1, 2, 3, 4], [1, 2, 3, 4])
- ([1, 2, 3, 4], [1, 2, 3, 4])

Example 2:

Input: nums = [10,20,30]
Output: 2
Explanation:
- The subsequence pairs which have the GCD of their elements equal to 10 are:
  - ([10, 20, 30], [10, 20, 30])
  - ([10, 20, 30], [10, 20, 30])

Example 3:

Input: nums = [1,1,1,1]
Output: 50

Example 4:

Input: nums = [5]
Output: 0

Example 5:

Input: nums = [2,2]
Output: 2

Example 6:

Input: nums = [1,1]
Output: 2

Example 7:

Input: nums = [100,200,150]
Output: 0

Example 8:

Input: nums = [6,10,15]
Output: 0

Example 9:

Input: nums = [2,4,8]
Output: 0

Example 10:

Input: nums = [1]
Output: 0

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 200

Hint:

Use dynamic programming to store number of subsequences up till index i with GCD g1 and g2.

Similar Questions:

1979. Find Greatest Common Divisor of Array

Solution:

We present a dynamic programming solution to count pairs of disjoint non-empty subsequences with equal GCD. Our approach tracks the number of ways to form two subsequences with specific GCD values simultaneously, processing each array element sequentially while deciding whether to skip it or assign it to either subsequence.

Approach

State Definition: Use dp[g1][g2] to store the number of ways to build two subsequences where the first has GCD g1 and the second has GCD g2
Base Case: Initialize dp[0][0] = 1 representing empty subsequences for both
Transition: For each element x in nums:
- Skip the element (copy current dp state)
- Add x to first subsequence: update GCD from g1 to gcd(g1, x)
- Add x to second subsequence: update GCD from g2 to gcd(g2, x)
Result Collection: Sum all dp[g][g] for g >= 1 to count pairs with equal GCD
Modulo Operations: Apply mod = 10⁹ + 7 to prevent overflow

Let's implement this solution in PHP: 3336. Find the Number of Subsequences With Equal GCD

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function subsequencePairCount(array $nums): int
{
    $mod = 1000000007;
    $maxVal = 200;

    // dp[g1][g2] = number of ways
    $dp = array_fill(0, $maxVal + 1, array_fill(0, $maxVal + 1, 0));
    $dp[0][0] = 1; // empty subsequences

    foreach ($nums as $x) {
        $newDp = $dp; // skip current element

        for ($g1 = 0; $g1 <= $maxVal; $g1++) {
            for ($g2 = 0; $g2 <= $maxVal; $g2++) {
                if ($dp[$g1][$g2] == 0) continue;
                $val = $dp[$g1][$g2];

                // Add x to first subsequence
                $ng1 = $g1 == 0 ? $x : gcd($g1, $x);
                $newDp[$ng1][$g2] = ($newDp[$ng1][$g2] + $val) % $mod;

                // Add x to second subsequence
                $ng2 = $g2 == 0 ? $x : gcd($g2, $x);
                $newDp[$g1][$ng2] = ($newDp[$g1][$ng2] + $val) % $mod;
            }
        }

        $dp = $newDp;
    }

    $result = 0;
    for ($g = 1; $g <= $maxVal; $g++) {
        $result = ($result + $dp[$g][$g]) % $mod;
    }

    return $result;
}

/**
 * @param $a
 * @param $b
 * @return mixed
 */
function gcd($a, $b): mixed
{
    while ($b != 0) {
        $t = $b;
        $b = $a % $b;
        $a = $t;
    }
    return $a;
}

// Test cases
echo subsequencePairCount([1,2,3,4]) .  "\n";           // Output: 10
echo subsequencePairCount([10,20,30]) .  "\n";          // Output: 2
echo subsequencePairCount([1,1,1,1]) .  "\n";           // Output: 50
echo subsequencePairCount([5]) .  "\n";                 // Output: 0
echo subsequencePairCount([2,2]) .  "\n";               // Output: 2
echo subsequencePairCount([1,1]) .  "\n";               // Output: 2
echo subsequencePairCount([100,200,150]) .  "\n";       // Output: 0
echo subsequencePairCount([6,10,15]) .  "\n";           // Output: 0
echo subsequencePairCount([2,4,8]) .  "\n";             // Output: 0
echo subsequencePairCount([1]) .  "\n";                 // Output: 0
?>

Explanation:

GCD Transition Logic: When GCD is 0 (empty subsequence), adding an element sets the GCD to that element's value. Otherwise, we compute gcd(current_gcd, new_element).
Disjointness Guarantee: By processing each element once with three choices (skip, add to seq1, add to seq2), we ensure each index belongs to at most one subsequence.
Non-empty Constraint: We exclude dp[0][0] from the final result since both subsequences must be non-empty.
Time-Optimized DP: The maximum GCD value is bounded by max(nums[i]) ≤ 200, allowing a 201×201 DP table regardless of array length.
Combinatorial Counting: Each path through the DP represents a unique assignment of elements to subsequences or skip, mapping directly to a valid subsequence pair.
Edge Case Handling: Elements with value 1 work correctly since gcd(1, x) = 1 for any x.

Complexity Analysis

Time Complexity: O(n * M² * log M) where n = len(nums), M = max(nums) ≤ 200. The log M factor comes from computing gcd during transitions. With M fixed at 200, this is essentially O(n) with a constant factor of 40,000 state transitions per element.
Space Complexity: O(M²) for the DP table, which is constant at 201 × 201 = 40401 cells, independent of input size.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

Subsequence: A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements. ↩
GCD: The term gcd(a, b) denotes the greatest common divisor of a and b. ↩

1291. Sequential Digits

MD ARIFUL HAQUE — Mon, 13 Jul 2026 14:36:47 +0000

1291. Sequential Digits

Difficulty: Medium

Topics: Staff, Enumeration, Weekly Contest 167

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

Example 1:

Input: low = 100, high = 300
Output: [123,234]

Example 2:

Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

Example 3:

Input: low = 10, high = 20
Output: [12]

Example 4:

Input: low = 5, high = 9
Output: []

Example 5:

Input: low = 123, high = 123
Output: [123]

Example 6:

Input: low = 1000, high = 1100
Output: []

Example 7:

Input: low = 123456789, high = 123456789
Output: [123456789]

Constraints:

10 <= low <= high <= 10⁹

Hint:

Generate all numbers with sequential digits and check if they are in the given range.
Fix the starting digit then do a recursion that tries to append all valid digits.

Solution:

We implemented a direct generation strategy that builds all sequential-digit numbers from scratch and filters those within the given range, ensuring sorted output.

Approach

Generate all sequential-digit numbers by fixing a starting digit from 1 to 9.
Append consecutive digits one by one while the next digit is ≤ 9 and the current number does not exceed high.
Check range during generation: if the constructed number falls between low and high, store it.
Sort the final result to guarantee ascending order (though generation order is mostly increasing, sorting ensures correctness).

Let's implement this solution in PHP: 1291. Sequential Digits

<?php
/**
 * @param Integer $low
 * @param Integer $high
 * @return Integer[]
 */
function sequentialDigits(int $low, int $high): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo sequentialDigits(100, 300) .  "\n";                    // Output: [123, 234]
echo sequentialDigits(1000, 13000) .  "\n";                 // Output: [1234, 2345, 3456, 4567, 5678, 6789, 12345]
echo sequentialDigits(10, 20) .  "\n";                      // Output: [12]
echo sequentialDigits(5, 9) .  "\n";                        // Output: []
echo sequentialDigits(123, 123) .  "\n";                    // Output: [123]
echo sequentialDigits(1000, 1100) .  "\n";                  // Output: []
echo sequentialDigits(123456789, 123456789) .  "\n";        // Output: [123456789]
?>

Explanation:

We loop over every possible starting digit (1–9).
For each start, we initialize the number with that digit and set the next expected digit to start + 1.
In a loop, we repeatedly append the next digit (e.g., 1→12→123) until we either exceed 9 as the next digit or the number exceeds high.
After appending each new digit, we check if the value is within [low, high] and add it to the result array.
Since we generate numbers in a non‑decreasing order for each start, and starts increase, we call sort() at the end for a fully sorted list.
This method avoids iterating over every integer in the range, making it efficient even when high is large (up to 10⁹).

Complexity Analysis

Time Complexity: O(1) — There are at most 9 starting digits and at most 9 digits per number, so at most 9×9 = 81 numbers generated, which is constant.
Space Complexity: O(1) — apart from the output array, we use only a few variables.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3534. Path Existence Queries in a Graph II

MD ARIFUL HAQUE — Fri, 10 Jul 2026 16:30:01 +0000

3534. Path Existence Queries in a Graph II

Difficulty: Hard

Topics: Principal, Array, Two Pointers, Binary Search, Dynamic Programming, Greedy, Bit Manipulation, Graph Theory, Sorting, Weekly Contest 447

You are given an integer n representing the number of nodes in a graph, labeled from 0 to n - 1.

You are also given an integer array nums of length n and an integer maxDiff.

An undirected edge exists between nodes i and j if the absolute difference between nums[i] and nums[j] is at most maxDiff (i.e., |nums[i] - nums[j]| <= maxDiff).

You are also given a 2D integer array queries. For each queries[i] = [uᵢ, vᵢ], find the minimum distance between nodes uᵢ and vᵢ. If no path exists between the two nodes, return -1 for that query.

Return an array answer, where answer[i] is the result of the iᵗʰ query.

Note: The edges between the nodes are unweighted.

Example 1:

Input: n = 5, nums = [1,8,3,4,2], maxDiff = 3, queries = [[0,3],[2,4]]
Output: [1,1]
Explanation:
- The resulting graph is:

Query	Shortest Path	Minimum Distance
[0, 3]	0 → 3	1
[2, 4]	2 → 4	1

Thus, the output is [1, 1].

Example 2:

Input: n = 5, nums = [5,3,1,9,10], maxDiff = 2, queries = [[0,1],[0,2],[2,3],[4,3]]
Output: [1,2,-1,1]
Explanation:
- The resulting graph is:

Query	Shortest Path	Minimum Distance
[0, 1]	0 → 1	1
[0, 2]	0 → 1 → 2	2
[2, 3]	None	-1
[4, 3]	3 → 4	1

Thus, the output is [1, 2, -1, 1].

Example 3:

Input: n = 3, nums = [3,6,1], maxDiff = 1, queries = [[0,0],[0,1],[1,2]]
Output: [0,-1,-1]
Explanation:
- There are no edges between any two nodes because:
  - Nodes 0 and 1: |nums[0] - nums[1]| = |3 - 6| = 3 > 1
  - Nodes 0 and 2: |nums[0] - nums[2]| = |3 - 1| = 2 > 1
  - Nodes 1 and 2: |nums[1] - nums[2]| = |6 - 1| = 5 > 1
- Thus, no node can reach any other node, and the output is [0, -1, -1].

Example 4:

Input: n = 1, nums = [5], maxDiff = 10, queries = [[0,0]]
Output: [0]

Example 5:

Input: n = 4, nums = [1,2,3,4], maxDiff = 10, queries = [[0,3],[1,2]]
Output: [1,1]

Example 6:

Input: n = 6, nums = [10,20,15,25,5,30], maxDiff = 5, queries = [[0,1],[0,2],[2,4],[3,5]]
Output: [2,1,3,2]

Example 7:

Input: n = 6, nums = [0,2,4,6,8,10], maxDiff = 2, queries = [[0,5]]
Output: [5]

Example 8:

Input: n = 4, nums = [1,2,100,101], maxDiff = 1, queries = [[0,2],[1,3]]
Output: [-1,-1]

Example 9:

Input: n = 7, nums = [1,50,2,51,52,3,53], maxDiff = 2, queries = [[0,6],[1,2]]
Output: 2,-1]

Example 10:

Input: n = 5, nums = [5,5,5,5,5], maxDiff = 0, queries = [[0,4],[1,3]]
Output: [1,1]

Example 11:

Input: n = 4, nums = [1,2,3,4], maxDiff = 0, queries = [[0,1],[0,2]]
Output: [-1,-1]

Constraints:

1 <= n == nums.length <= 10⁵
0 <= nums[i] <= 10⁵
0 <= maxDiff <= 10⁵
1 <= queries.length <= 10⁵
queries[i] == [uᵢ, vᵢ]
0 <= uᵢ, vᵢ < n

Hint:

Sort the nodes according to nums[i].
Can we use binary jumping?
Use binary jumping with a sparse table data structure.

Solution:

We present an efficient solution for answering path existence queries in a graph where edges are defined by value differences. We transform the problem by sorting nodes by their nums values, which allows us to build a binary lifting (sparse table) structure to answer shortest path queries in logarithmic time. This approach handles up to 100,000 nodes and queries efficiently, avoiding the need to explicitly construct the graph.

Approach

Sort nodes by value: We sort nodes based on their nums[i] values while preserving original indices. This ordering creates a monotonic property where edges exist between nodes whose values differ by at most maxDiff.
Build jump table: For each sorted position i, we compute jump[i][0] as the farthest position reachable in one "jump" (edge) - this is the maximum index right such that sortedNums[right] - sortedNums[i] <= maxDiff. Since the array is sorted, we can use a two-pointer technique to compute this efficiently.
Binary lifting optimization: We build a sparse table where jump[i][k] represents the farthest position reachable by making 2ᵏ jumps from position i. This allows us to skip multiple edges at once.
Query processing with greedy descent: For each query [u, v], we map original indices to their sorted positions. We then find the minimum number of jumps needed to go from min(start, end) to max(start, end) using binary lifting. If the destination is unreachable, we return -1.

Let's implement this solution in PHP: 3534. Path Existence Queries in a Graph II

<?php
/**
 * @param Integer $n
 * @param Integer[] $nums
 * @param Integer $maxDiff
 * @param Integer[][] $queries
 * @return Integer[]
 */
function pathExistenceQueries(int $n, array $nums, int $maxDiff, array $queries): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param array $jump
 * @param int $start
 * @param int $end
 * @param int $level
 * @return int
 */
function minJumps(array $jump, int $start, int $end, int $level): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo pathExistenceQueries(5, [1,8,3,4,2], 3, [[0,3],[2,4]]) .  "\n";                            // Output: [1,1]
echo pathExistenceQueries(5, [5,3,1,9,10], 2, [[0,1],[0,2],[2,3],[4,3]]) .  "\n";               // Output: [1,2,-1,1]
echo pathExistenceQueries(3, [3,6,1], 1, [[0,0],[0,1],[1,2]]) .  "\n";                          // Output: [0,-1,-1]
echo pathExistenceQueries(1, [5], 10, [[0,0]]) .  "\n";                                         // Output: [0]
echo pathExistenceQueries(4, [1,2,3,4], 10, [[0,3],[1,2]]) .  "\n";                             // Output: [1,1]
echo pathExistenceQueries(6, [10,20,15,25,5,30], 5, [[0,1],[0,2],[2,4],[3,5]]) .  "\n";         // Output: [2,1,3,2]
echo pathExistenceQueries(6, [0,2,4,6,8,10], 2, [[0,5]]) .  "\n";                               // Output: [5]
echo pathExistenceQueries(4, [1,2,100,101], 1, [[0,2],[1,3]]) .  "\n";                          // Output: [-1,-1]
echo pathExistenceQueries(7, [1,50,2,51,52,3,53], 2, [[0,6],[1,2]]) .  "\n";                    // Output: [2,-1]
echo pathExistenceQueries(5, [5,5,5,5,5], 0, [[0,4],[1,3]]) .  "\n";                            // Output: [1,1]
echo pathExistenceQueries(4, [1,2,3,4], 0, [[0,1],[0,2]]) .  "\n";                              // Output: [-1,-1]
?>

Explanation:

Graph transformation insight: The graph is defined by value differences, not original node ordering. By sorting nodes by value, edges become intervals of contiguous indices. This transforms the shortest path problem into finding the minimum number of interval jumps to go from one position to another in the sorted order.
Jump table construction: Using a two-pointer approach, we compute right[i] as the rightmost position reachable from i in one jump. Because sortedNums is sorted, as i increases, right[i] is non-decreasing, making this computation O(n).
Binary lifting mechanics: For each node and each power of two level, jump[i][k] = jump[jump[i][k-1]][k-1]. This means from position i, after 2ᵏ jumps, we can reach position jump[i][k]. This allows us to jump large distances in logarithmic time.
Query answering strategy:
- Start from the left position (start) and target the right position (end)
- Check if we can reach in 1 jump: return 1
- Find the highest level where we don't overshoot end
- Make that jump and recursively compute the remaining distance
- Sum the jump sizes to get the total distance
Unreachable detection: If even the largest possible jump from start (using all levels) doesn't reach end, the nodes are in different connected components. We detect this when jump[start][maxLevel] < end and return -1.

Complexity Analysis

Time Complexity:
- Sorting: O(n log n)
- Jump table construction: O(n log n) where maxLevel = O(log n)
- Each query: O(log n) using binary lifting
- Overall: O((n + q) log n) where q is number of queries
Space Complexity: O(n log n) for the jump table, plus O(n) for auxiliary arrays

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3532. Path Existence Queries in a Graph I

MD ARIFUL HAQUE — Thu, 09 Jul 2026 18:08:03 +0000

3532. Path Existence Queries in a Graph I

Difficulty: Medium

Topics: Senior, Array, Hash Table, Binary Search, Union-Find, Graph Theory, Weekly Contest 447

You are given an integer n representing the number of nodes in a graph, labeled from 0 to n - 1.

You are also given an integer array nums of length n sorted in non-decreasing order, and an integer maxDiff.

An undirected edge exists between nodes i and j if the absolute difference between nums[i] and nums[j] is at most maxDiff (i.e., |nums[i] - nums[j]| <= maxDiff).

You are also given a 2D integer array queries. For each queries[i] = [uᵢ, vᵢ], determine whether there exists a path between nodes uᵢ and vᵢ.

Return a boolean array answer, where answer[i] is true if there exists a path between uᵢ and vᵢ in the iᵗʰ query andfalse` otherwise.

Example 1:

Input: n = 2, nums = [1,3], maxDiff = 1, queries = [[0,0],[0,1]]
Output: [true,false]
Explanation:
- Query [0,0]: Node 0 has a trivial path to itself.
- Query [0,1]: There is no edge between Node 0 and Node 1 because |nums[0] - nums[1]| = |1 - 3| = 2, which is greater than maxDiff.
- Thus, the final answer after processing all the queries is [true, false].

Example 2:

Input: n = 4, nums = [2,5,6,8], maxDiff = 2, queries = [[0,1],[0,2],[1,3],[2,3]]
Output: [false,false,true,true]
Explanation:
- The resulting graph is:
- Query [0,1]: There is no edge between Node 0 and Node 1 because |nums[0] - nums[1]| = |2 - 5| = 3, which is greater than maxDiff.
- Query [0,2]: There is no edge between Node 0 and Node 2 because |nums[0] - nums[2]| = |2 - 6| = 4, which is greater than maxDiff.
- Query [1,3]: There is a path between Node 1 and Node 3 through Node 2 since |nums[1] - nums[2]| = |5 - 6| = 1 and |nums[2] - nums[3]| = |6 - 8| = 2, both of which are within maxDiff.
- Query [2,3]: There is an edge between Node 2 and Node 3 because |nums[2] - nums[3]| = |6 - 8| = 2, which is equal to maxDiff.
- Thus, the final answer after processing all the queries is [false, false, true, true].

Example 3:

Input: n = 1, nums = [5], maxDiff = 10, queries = [[0,0]]
Output: [true]

Example 4:

Input: n = 5, nums = [1,2,3,4,5], maxDiff = 1, queries = [[0,4],[1,3],[0,2]]
Output: [true,true,true]

Example 5:

Input: n = 3, nums = [0,10,20], maxDiff = 5, queries = [[0,1],[1,2],[0,2]]
Output: [false,false,false]

Example 6:

Input: n = 6, nums = [1,3,5,10,12,14], maxDiff = 2, queries = [[0,2],[3,5],[0,5],[2,3]]
Output: [true,true,false,false]

Example 7:

Input: n = 3, nums = [0,100,100], maxDiff = 0, queries = [[1,2],[0,1]]
Output: [true,false]

Constraints:

1 <= n == nums.length <= 10⁵
0 <= nums[i] <= 10⁵
nums is sorted in non-decreasing order.
0 <= maxDiff <= 10⁵
1 <= queries.length <= 10⁵
queries[i] == [uᵢ, vᵢ]
0 <= uᵢ, vᵢ < n

Hint:

How do the connected components look? Do they appear in segments (i.e., are they continuous)?
Preprocess the connected components.

Solution:

We solve the path existence queries problem by leveraging the fact that the graph's connected components form continuous segments in the sorted array. We preprocess the components in a single pass, assigning each node a component ID based on consecutive value differences. Then each query is answered in O(1) time by checking if both nodes belong to the same component.

Approach

Key Insight: Since the graph connects nodes based on value differences, and nums is sorted, connected components will always be contiguous segments of indices. If consecutive values differ by ≤ maxDiff, they belong to the same component; if the difference exceeds maxDiff, it creates a boundary between components.
Component Assignment: Traverse the sorted array once, extending each component as long as the gap between consecutive elements is ≤ maxDiff. Assign the same component ID to all nodes in that contiguous segment.
Query Processing: For each query [u, v], simply check if component[u] == component[v]. If they share the same component ID, a path exists; otherwise, it doesn't.
Self-Query Handling: The approach naturally handles u == v queries since both indices will have the same component ID, returning true as required.

Let's implement this solution in PHP: 3532. Path Existence Queries in a Graph I

`php
<?php
/**

@param Integer $n
@param Integer[] $nums
@param Integer $maxDiff
@param Integer[][] $queries
@return Boolean[] / function pathExistenceQueries(int $n, array $nums, int $maxDiff, array $queries): array { ... ... ... /*
- go to ./solution.php */ }

// Test cases
echo json_encode(pathExistenceQueries(2, [1,3], 1, [[0,0],[0,1]])) . "\n"; // Output: [true, false]
echo json_encode(pathExistenceQueries(4, [2,5,6,8], 2, [[0,1],[0,2],[1,3],[2,3]])) . "\n"; // Output: [false, false, true, true]
echo json_encode(pathExistenceQueries(1, [5], 10, [[0,0]]) . "\n"; // Output: [true]
echo json_encode(pathExistenceQueries(5, [1,2,3,4,5], 1, [[0,4],[1,3],[0,2]])) . "\n"; // Output: [true, true, true]
echo json_encode(pathExistenceQueries(3, [0,10,20], 5, [[0,1],[1,2],[0,2]])) . "\n"; // Output: [false, false, false]
echo json_encode(pathExistenceQueries(6, [1,3,5,10,12,14], 2, [[0,2],[3,5],[0,5],[2,3]])) . "\n"; // Output: [true, true, false, false]
echo json_encode(pathExistenceQueries(3, [0,100,100], 0, [[1,2],[0,1]])) . "\n"; // Output: [true, false]
?>
`

Explanation:

Single Pass Component Detection: We iterate through the array with two pointers. The outer pointer i starts each new component, and the inner pointer j extends the component while nums[j+1] - nums[j] ≤ maxDiff. This works because nums is sorted, so the absolute difference is just the difference between consecutive elements.
Why Components are Contiguous: If node i connects to node i+1 (difference ≤ maxDiff), and node i+1 connects to node i+2, then node i connects to node i+2 through i+1. Therefore, once a connection chain breaks (difference > maxDiff), no further connections can cross that boundary because values only increase.
Constant-Time Queries: After preprocessing, each query is answered by a single array comparison, making the solution extremely efficient for large query sets.
Memory Efficiency: We only store the component array of size n and process queries on the fly, avoiding any heavy graph construction.

Complexity Analysis

Time Complexity: O(n + q) where n is the number of nodes and q is the number of queries. The preprocessing scans nums once, and each query is answered in O(1) time.
Space Complexity: O(n) for the component array. No additional data structures are needed for graph representation.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3756. Concatenate Non-Zero Digits and Multiply by Sum II

MD ARIFUL HAQUE — Wed, 08 Jul 2026 15:02:49 +0000

3756. Concatenate Non-Zero Digits and Multiply by Sum II

Difficulty: Medium

Topics: Staff, Math, String, Prefix Sum, Weekly Contest 477

You are given a string s of length m consisting of digits. You are also given a 2D integer array queries, where queries[i] = [lᵢ, rᵢ].

For each queries[i], extract the substring¹ s[lᵢ..rᵢ]. 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 iᵗʰ query.

Since the answers may be very large, return them modulo 10⁹ + 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 (10⁹ + 7) = 444444137.

Example 4:

Input: s = "000", queries = [[0,2]]
Output: [0]

Example 5:

Input: s = "5", queries = [[0,0]]
Output: [25]

Example 6:

Input: s = "10101", queries = [[0,4]]
Output: [1111 * 4 = 4444]

Example 7:

Input: s = "120340", queries = [[2,2]]
Output: [0]

Example 8:

Input: s = "9", queries = [[0,0]]
Output: [81]

Constraints:

1 <= m == s.length <= 10⁵
s consists of digits only.
1 <= queries.length <= 10⁵
queries[i] = [lᵢ, rᵢ]
0 <= lᵢ <= rᵢ < m

Hint:

Track only nonzero digits: store their values and positions and keep a prefix sum for digit sums.
Also build prefix concatenation values P, pow10, and set mod = 10⁹+7 so any compressed substring number is obtainable from prefixes.
Map each query [l, r] to the compressed list using precomputed mapping arrays (first nonzero at or after i
If the mapped range is empty return 0; otherwise get x from P, get sum from the digit-prefix, and return (x * sum) % mod.

Solution:

We have implemented an efficient prefix-based solution that avoids reconstructing substrings for each query. By precomputing the positions, concatenation values, and digit sums of all non-zero digits, we can answer each query in O(log n) or O(1) time after O(n) preprocessing.

Approach

Preprocess non-zero digits
- Iterate through the string and store only non-zero digits along with their original positions.
- Maintain two prefix arrays:
  - prefixVal: the integer formed by concatenating non-zero digits up to each index, modulo 10⁹+7.
  - prefixSum: the sum of those digits.
- Precompute powers of 10 modulo 10⁹+7 to enable range concatenation extraction.
Efficient range mapping for queries
- Use binary search on the positions array to find the first and last non-zero digit indices within [l, r].
- If no non-zero digit exists in the range, return 0.
Compute x and sum for the range
- x is obtained from prefixVal using the formula: x = (prefixVal[last] - prefixVal[first-1] * 10⁽ˡᵃˢᵗ⁻ᶠᶦʳˢᵗ⁺¹⁾) mod MOD
- sum is obtained directly from prefixSum as a simple difference.
Return the product modulo 10⁹+7.

Let's implement this solution in PHP: 3756. Concatenate Non-Zero Digits and Multiply by Sum II

<?php
/**
 * @param String $s
 * @param Integer[][] $queries
 * @return Integer[]
 */
function sumAndMultiply(string $s, array $queries): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo sumAndMultiply("10203004", [[0,7],[1,3],[4,6]]) .  "\n";       // Output: [12340, 4, 9]
echo sumAndMultiply("1000", [[0,3],[1,1]]) .  "\n";                 // Output: [1, 0]
echo sumAndMultiply("9876543210", [[0,9]]) .  "\n";                 // Output: [444444137]
echo sumAndMultiply("000", [[0,2]]) .  "\n";                        // Output: [0]
echo sumAndMultiply("5", [[0,0]]) .  "\n";                          // Output: [25]
echo sumAndMultiply("10101", [[0,4]]) .  "\n";                      // Output: 1111 * 4 = 4444
echo sumAndMultiply("120340", [[2,2]]) .  "\n";                     // Output: [0]
echo sumAndMultiply("9", [[0,0]]) .  "\n";                          // Output: [81]
?>

Explanation:

Step 1: Parse and store non-zero digits
- We traverse the string once, saving each non-zero digit and its index.
- For each saved digit, we update the prefix concatenation value and digit sum.
Step 2: Precompute powers of 10
- Powers are needed to shift the left part when extracting a substring of concatenated digits.
Step 3: Handle each query
- Use binary search to find the first and last non-zero positions within [l, r].
- If none exist, answer is 0.
- Compute x using prefix concatenation and sum using prefix sum.
- Multiply and take modulo.
Step 4: Return results
- Collect all answers in an array and return.

Complexity Analysis

Time Complexity:
- Preprocessing: O(n)
- Each query: O(log k) where k is the number of non-zero digits (via binary search).
- Overall: O(n + q log n) in the worst case.
Space Complexity:
- O(n) for storing positions, prefix values, prefix sums, and powers of 10.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

Substring: A substring is a contiguous non-empty sequence of characters within a string. ↩

3754. Concatenate Non-Zero Digits and Multiply by Sum I

MD ARIFUL HAQUE — Tue, 07 Jul 2026 13:59:04 +0000

3754. Concatenate Non-Zero Digits and Multiply by Sum I

Difficulty: Easy

Topics: Mid Level, Math, Weekly Contest 477

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.

Example 3:

Input: n = 0
Output: 0

Example 4:

Input: n = 5
Output: 25

Example 5:

Input: n = 123456789
Output: 5555555505

Example 6:

Input: n = 101010
Output: 333

Example 7:

Input: n = 1000000000
Output: 1

Constraints:

0 <= n <= 10⁹

Hint:

Simulate as described

Solution:

We implement a straightforward solution that processes the input integer n by extracting all non-zero digits, constructing a new number from them, calculating their sum, and returning their product. Our approach handles the edge case where no non-zero digits exist by returning 0.

Approach

Digit Extraction: Convert the integer n to a string and split it into an array of individual digit characters
Filter Non-Zero Digits: Remove all digit characters equal to '0' using array filtering
Edge Case Handling: If no non-zero digits remain, return 0 immediately
Construct x: Join the filtered digit characters into a string and convert to integer
Calculate Sum: Sum the numeric values of all non-zero digits
Compute Result: Return the product of x and sum

Let's implement this solution in PHP: 3754. Concatenate Non-Zero Digits and Multiply by Sum I

<?php
/**
 * @param Integer $n
 * @return Integer
 */
function sumAndMultiply(int $n): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo sumAndMultiply(10203004) .  "\n";          // Output: 12340
echo sumAndMultiply(1000) .  "\n";              // Output: 1
echo sumAndMultiply(0) .  "\n";                 // Output: 0
echo sumAndMultiply(5) .  "\n";                 // Output: 25
echo sumAndMultiply(123456789) .  "\n";         // Output: 5555555505
echo sumAndMultiply(101010) .  "\n";            // Output: 333
echo sumAndMultiply(1000000000) .  "\n";        // Output: 1
?>

Explanation:

String Conversion: We treat the number as a string to easily access each digit individually without complex arithmetic operations
Zero Filtering: We filter out '0' characters since they contribute nothing to either x (they don't change the numeric value when concatenated with other digits) or the sum
Empty Array Check: When all digits are zero, we return 0 early to avoid processing an empty array
Number Reconstruction: Joining the filtered digits creates the number formed by all non-zero digits in their original order
Sum Calculation: Using array_sum on the digit characters automatically converts them to integers, giving us the digit sum
Final Multiplication: Multiplying x by sum yields the required result per the problem specification

Complexity Analysis

Time Complexity: O(d) where d is the number of digits in n (maximum 10 digits since n ≤ 10⁹)
- String conversion and splitting: O(d)
- Array filtering: O(d)
- Array summing: O(d)
- Join and integer conversion: O(d)
Space Complexity: O(d) for storing the digit arrays
- The split array stores d characters
- The filtered array stores at most d characters
- Both are negligible as d ≤ 10

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

1288. Remove Covered Intervals

MD ARIFUL HAQUE — Mon, 06 Jul 2026 16:46:55 +0000

1288. Remove Covered Intervals

Difficulty: Medium

Topics: Senior, Array, Sorting, Biweekly Contest 15

Given an array intervals where intervals[i] = [lᵢ, rᵢ] represent the interval [lᵢ, rᵢ), remove all intervals that are covered by another interval in the list.

The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

Return the number of remaining intervals.

Example 1:

Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2:

Input: intervals = [[1,4],[2,3]]
Output: 1

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 2

Example 4:

Input: intervals = [[1,5],[2,4],[3,6]]
Output: 2

Example 5:

Input: intervals = [[0,10],[1,9],[2,8],[3,7]]
Output: 1

Example 6:

Input: intervals = [[1,2]]
Output: 1

Example 7:

Input: intervals = [[1,4],[2,5],[3,6]]
Output: 3

Constraints:

1 <= intervals.length <= 1000
intervals[i].length == 2
0 <= lᵢ < rᵢ <= 10⁵
All the given intervals are unique.

Hint:

How to check if an interval is covered by another?
Compare each interval to all others and check if it is covered by any interval.

Solution:

We implement a direct O(n²) comparison solution that checks every interval against all others to determine if it is covered. By iterating through each interval and testing the covering condition against every other interval, we count only those intervals that are not covered by any other interval.

Approach

Initialize a counter remaining to 0.
For each interval i in the input array:
- Assume it is not covered (covered = false).
- Compare it with every other interval j where j ≠ i.
- If any j satisfies c <= a and b <= d (where [a,b) is interval i and [c,d) is interval j), mark it as covered and break out of the inner loop.
- If after checking all j the interval is still not covered, increment remaining.
Return remaining.

Let's implement this solution in PHP: 1288. Remove Covered Intervals

<?php
/**
 * @param Integer[][] $intervals
 * @return Integer
 */
function removeCoveredIntervals(array $intervals): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo removeCoveredIntervals([[1,4],[3,6],[2,8]]) .  "\n";           // Output: 2
echo removeCoveredIntervals([[1,4],[2,3]]) .  "\n";                 // Output: 1
echo removeCoveredIntervals([[1,2],[2,3]]) .  "\n";                 // Output: 2
echo removeCoveredIntervals([[1,5],[2,4],[3,6]]) .  "\n";           // Output: 2
echo removeCoveredIntervals([[0,10],[1,9],[2,8],[3,7]]) .  "\n";    // Output: 1
echo removeCoveredIntervals([[1,2]]) .  "\n";                       // Output: 1
echo removeCoveredIntervals([[1,4],[2,5],[3,6]]) .  "\n";           // Output: 3
?>

Explanation:

The covering condition is directly translated: an interval [a,b) is covered by [c,d) if c starts at or before a, and d ends at or after b.
We compare every interval against every other interval, including intervals that might be identical (though the problem guarantees uniqueness, so no equal intervals exist).
If a covering interval is found, we stop checking further for that interval to save time.
The outer loop processes each interval once, and the inner loop checks all possible covering candidates.
This brute-force approach works well given the constraint n ≤ 1000, where O(n²) is acceptable.

Complexity Analysis

Time Complexity: O(n²), where n is the number of intervals. For each of the n intervals, we scan up to n−1 other intervals.
Space Complexity: O(1) additional space (excluding input storage), as we only use a few integer variables.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

1301. Number of Paths with Max Score

MD ARIFUL HAQUE — Sun, 05 Jul 2026 16:25:22 +0000

1301. Number of Paths with Max Score

Difficulty: Hard

Topics: Principal, Array, Dynamic Programming, Matrix, Biweekly Contest 16

You are given a square board of characters. You can move on the board starting at the bottom right square marked with the character 'S'.

You need to reach the top left square marked with the character 'E'. The rest of the squares are labeled either with a numeric character 1, 2, ..., 9 or with an obstacle 'X'. In one move you can go up, left or up-left (diagonally) only if there is no obstacle there.

Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect, and the second is the number of such paths that you can take to get that maximum sum, taken modulo 10⁹ + 7.

In case there is no path, return [0, 0].

Example 1:

Input: board = ["E23","2X2","12S"]
Output: [7,1]

Example 2:

Input: board = ["E12","1X1","21S"]
Output: [4,2]

Example 3:

Input: board = ["E11","XXX","11S"]
Output: [0,0]

Example 4:

Input: board = ["E99","999","99S"]
Output: [36,1]

Example 5:

Input: board = ["E11","111","11S"]
Output: [4,6]

Example 6:

Input: board = ["E1","1S"]
Output: [1,2]

Example 7:

Input: board = ["EX","XS"]
Output: [0,0]

Example 8:

Input: board = ["E99","9X9","999"]
Output: [36,2]

Constraints:

2 <= board.length == board[i].length <= 100

Hint:

Use dynamic programming to find the path with the max score.
Use another dynamic programming array to count the number of paths with max score.

Solution:

We implement a dynamic programming (DP) solution that traverses the board from bottom‑right ('S') to top‑left ('E') using only up, left, and up‑left moves. For each cell, we track two values: the maximum numeric sum achievable from that cell to the start, and the number of distinct paths that yield that maximum sum. By processing cells in reverse order (bottom‑right to top‑left) and combining results from the three possible predecessors, we efficiently compute the answer. The solution handles obstacles ('X'), ignores numeric values on 'E' and 'S', and applies modulo 10⁹+7 for path counts.

Approach

Reverse DP traversal – Start from 'S' at (n-1, m-1) with score 0 and path count 1. Process all other cells in reverse row‑major order (bottom‑right to top‑left).
Three possible moves – From current cell (i,j), we can come from:
- Down (i+1, j)
- Right (i, j+1)
- Down‑right (i+1, j+1)
Score calculation – For each valid predecessor, add the numeric value of the current cell (unless it is 'E', which contributes 0).
Selection logic – For each cell:
- Compare the three candidate scores.
- Keep the maximum score and sum the path counts of all predecessors that achieve that maximum.
Modulo handling – Path counts are stored modulo 10⁹+7.
Final check – If dp[0][0] remains NEG, no path exists → return [0,0].

Let's implement this solution in PHP: 1301. Number of Paths with Max Score

<?php
/**
 * @param String[] $board
 * @return Integer[]
 */
function pathsWithMaxScore(array $board): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(pathsWithMaxScore(["E23","2X2","12S"])) .  "\n";        // Output: [7,1]
print_r(pathsWithMaxScore(["E12","1X1","21S"])) .  "\n";        // Output: [4,2]
print_r(pathsWithMaxScore(["E11","XXX","11S"])) .  "\n";        // Output: [0,0]
print_r(pathsWithMaxScore(["E99","999","99S"])) .  "\n";        // Output: [36,1]
print_r(pathsWithMaxScore(["E11","111","11S"])) .  "\n";        // Output: [4,6]
print_r(pathsWithMaxScore(["E1","1S"])) .  "\n";                // Output: [1,2]
print_r(pathsWithMaxScore(["EX","XS"])) .  "\n";                // Output: [0,0]
print_r(pathsWithMaxScore(["E99","9X9","999"])) .  "\n";        // Output: [36,2]
?>

Explanation:

DP table dp[i][j] stores the maximum sum collected from (i,j) to 'S'.
Ways table ways[i][j] stores the number of paths that achieve dp[i][j] from (i,j) to 'S'.
Initialisation – dp[n-1][m-1] = 0, ways[n-1][m-1] = 1 because starting at 'S' collects no numbers and there is exactly one way (being already there).
Obstacle skipping – Cells with 'X' are ignored; they cannot be part of any valid path.
Numeric contribution – When moving to a cell, we add that cell’s digit to the score. For 'E', we add 0 so that the score only includes digits from intermediate cells.
Count aggregation – If a new maximum is found, the count resets to that predecessor’s count. If another predecessor ties the maximum, its count is added.
No‑path detection – If a cell cannot be reached from any valid predecessor, dp[i][j] stays NEG and ways[i][j] stays 0.

Complexity Analysis

Time complexity: O(n²) – We iterate over all n×n cells exactly once, and for each we check at most three predecessors.
Space complexity: O(n²) – Two 2D arrays of size n×n are used to store DP scores and path counts.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2492. Minimum Score of a Path Between Two Cities

MD ARIFUL HAQUE — Sat, 04 Jul 2026 16:22:19 +0000

2492. Minimum Score of a Path Between Two Cities

Difficulty: Medium

Topics: Staff, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Weekly Contest 322

You are given a positive integer n representing n cities numbered from 1 to n. You are also given a 2D array roads where roads[i] = [aᵢ, bᵢ, distanceᵢ] indicates that there is a bidirectional road between cities aᵢ and bᵢ with a distance equal to distanceᵢ. The cities graph is not necessarily connected.

The score of a path between two cities is defined as the minimum distance of a road in this path.

Return the minimum possible score of a path between cities 1 and n.

Note:

A path is a sequence of roads between two cities.
It is allowed for a path to contain the same road multiple times, and you can visit cities 1 and n multiple times along the path.
The test cases are generated such that there is at least one path between 1 and n.

Example 1:

Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Output: 5
Explanation:
- The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5.
- It can be shown that no other path has less score.

Example 2:

Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
Output: 2
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 1 -> 3 -> 4. The score of this path is min(2,2,4,7) = 2.

Example 3:

Input: n = 3, roads = [[1,2,3],[2,3,1],[1,3,2]]
Output: 1

Example 4:

Input: n = 5, roads = [[1,2,10],[2,3,5],[3,4,8],[4,5,3]]
Output: 3

Example 5:

Input: n = 6, roads = [[1,2,15],[2,3,12],[3,4,20],[4,6,8],[1,5,6],[5,6,10]]
Output: 6

Example 6:

Input: n = 4, roads = [[1,2,5],[2,4,3],[3,1,8]]
Output: 3

Constraints:

2 <= n <= 10⁵
1 <= roads.length <= 10⁵
roads[i].length == 3
1 <= aᵢ, bᵢ <= n
aᵢ != bᵢ
1 <= distancei <= 10⁴
There are no repeated edges.
There is at least one path between 1 and n.

Hint:

Can you solve the problem if the whole graph is connected?
Notice that if the graph is connected, you can always use any edge of the graph in your path.
How to solve the general problem in a similar way? Remove all the nodes that are not connected to 1 and n, then apply the previous solution in the new graph.

Solution:

We have designed an efficient solution to find the minimum possible score of a path between cities 1 and n. The key insight is that since we can traverse roads multiple times and revisit cities, the minimum score along any path from city 1 to city n is simply the minimum edge weight among all edges that are reachable from city 1 in the connected component containing city 1. This works because we can always detour through any reachable edge and return to our path, effectively including that edge's weight in our path's score.

Approach

Graph Connectivity Insight: Since we can reuse roads and revisit cities, any edge that is reachable from city 1 can be included in a path from city 1 to city n (as long as city n is also reachable from city 1).
DFS Traversal: We perform a Depth-First Search starting from city 1 to traverse the entire connected component containing city 1.
Score Tracking: While traversing, we track the minimum edge weight encountered in the connected component. This minimum value represents the answer.
Reachability Guarantee: The problem guarantees at least one path exists between city 1 and city n, so city n is in the same connected component as city 1.
Edge Case Handling: The solution works regardless of whether the graph is connected or not, as we only traverse the component containing city 1.

Let's implement this solution in PHP: 2492. Minimum Score of a Path Between Two Cities

<?php
/**
 * @param Integer $n
 * @param Integer[][] $roads
 * @return Integer
 */
function minScore(int $n, array $roads): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minScore(4, [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]) .  "\n";                                // Output: 5
echo minScore(4, [[1,2,2],[1,3,4],[3,4,7]]) .  "\n";                                        // Output: 2
echo minScore(3, [[1,2,3],[2,3,1],[1,3,2]]) .  "\n";                                        // Output: 1
echo minScore(5, [[1,2,10],[2,3,5],[3,4,8],[4,5,3]]) .  "\n";                               // Output: 3
echo minScore(6, [[1,2,15],[2,3,12],[3,4,20],[4,6,8],[1,5,6],[5,6,10]]) .  "\n";            // Output: 6
echo minScore(4, [[1,2,5],[2,4,3],[3,1,8]]) .  "\n";                                        // Output: 3

Explanation:

Why BFS/DFS works: We use DFS (or BFS) to visit all nodes in the connected component containing city 1. For each edge we traverse, we update our minimum score.
Why revisiting edges helps: The ability to traverse edges multiple times means we can go from city 1 to any reachable edge, traverse it, and return to continue our path to city n. This allows all reachable edges to contribute to the path's minimum score.
Example 1 Walkthrough: In the first example, DFS from node 1 visits nodes 2 and 4, encountering edges with weights 9, 5, and 7. The minimum among reachable edges is 5, which matches the output.
Example 3 Walkthrough: Starting from node 1, we visit nodes 2 and 3, encountering edges [1,2,2], [1,3,4], and [3,4,7]. The minimum is 2. Even though node 2 might seem like a dead end, we can go 1→2→1→3→4, incorporating the edge of weight 2 into our path.
Optimization: We don't need to check both directions of bidirectional edges separately since our adjacency list already accounts for both directions.

Complexity Analysis

Time Complexity: O(n + m), where n is the number of cities and m is the number of roads. Each node is visited at most once, and each edge is processed twice (once from each endpoint).
Space Complexity: O(n + m) for storing the adjacency list and O(n) for the visited array, resulting in O(n + m) total space.
Optimality: The solution is optimal as we must at least read all edges reachable from city 1 to find the minimum, which requires O(n + m) time in the worst case.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub