Given an array arr[] of N integers, the task is to find the minimum number of moves to sort the array in non-decreasing order by splitting any array element into two parts such that the sum of the parts is the same as that element.

Constraints

N/A

Example 1

Input:

arr = [3, 4, 2]

Output:

2

Explanation: The moves are:

• Split 4 into two parts (2, 2). Array becomes arr[] = {3, 2, 2, 2}
• Split 3 into two parts (1, 2). Array becomes arr[] = {1, 2, 2, 2, 2}

Example 2

Input:

arr = [3, 2, 4]

Output:

1

Explanation: Split 3 into two parts (1, 2). Array becomes (1, 2, 2, 4).

Example 3

Input:

arr = [5, 6, 5, 7, 9]

Output:

2

Explanation: At Index = 0, 5 breaks into 2, 3 so array becomes (2, 3, 6, 5, 7, 9). At Index = 1, 6 breaks into 3, 3 so array becomes (2, 3, 3, 3, 5, 7, 9). Now the array is sorted (2, 3, 3, 3, 5, 7, 9), so the count is 2. Hence the function returns 2.

解法

与上题方法相同：从右往左扫，维护后缀允许的上界 cap。每次若 arr[i] > cap 则需分 k = arr[i]/cap 段，操作 += k-1，新 cap = arr[i] / k。复杂度 O(n)。

from typing import List

def minimum_moves_to_sort_array(arr: List[int]) -> int:
    n = len(arr)
    cap = arr[-1]
    ops = 0
    for i in range(n - 2, -1, -1):
        if arr[i] <= cap:
            cap = arr[i]
        else:
            k = (arr[i] + cap - 1) // cap
            ops += k - 1
            cap = arr[i] // k
    return ops

class Solution {
    int minimumMovesToSortArray(int[] arr) {
        int n = arr.length;
        long cap = arr[n - 1], ops = 0;
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] <= cap) cap = arr[i];
            else {
                long k = (arr[i] + cap - 1) / cap;
                ops += k - 1;
                cap = arr[i] / k;
            }
        }
        return (int) ops;
    }
}

class Solution {
public:
    int minimumMovesToSortArray(vector<int>& arr) {
        int n = arr.size();
        long long cap = arr[n - 1], ops = 0;
        for (int i = n - 2; i >= 0; --i) {
            if (arr[i] <= cap) cap = arr[i];
            else {
                long long k = (arr[i] + cap - 1) / cap;
                ops += k - 1;
                cap = arr[i] / k;
            }
        }
        return (int) ops;
    }
};

Write a Java program with a function named numberOfBalancedStrings that counts the number of ways we can make a balanced string of size n and difference d. A Balanced string is a string where the difference between adjacent characters does not exceed d.

Constraints

N/A

Example 1

Input:

n = 3
d = 3

Output:

224

Explanation: There are 224 ways to create a balanced string of size 3 with a maximum adjacent character difference of 3.

Example 2

Input:

n = 2
d = 2

Output:

124

Explanation: There are 124 ways to create a balanced string of size 2 with a maximum adjacent character difference of 2.

解法

同 1：DP dp[i][c] = 长度 i 末尾为 c 的合法串数，转移枚举上一位 c' 满足 |c' - c| ≤ d。总答 = Σ dp[n][c]。复杂度 O(n · 26²)。

def number_of_balanced_strings(n: int, d: int) -> int:
    MOD = 10**9 + 7
    dp = [1] * 26
    for _ in range(n - 1):
        nxt = [0] * 26
        for c in range(26):
            for cp in range(max(0, c - d), min(25, c + d) + 1):
                nxt[c] = (nxt[c] + dp[cp]) % MOD
        dp = nxt
    return sum(dp) % MOD

class Solution {
    int numberOfBalancedStrings(int n, int d) {
        final int MOD = 1_000_000_007;
        long[] dp = new long[26];
        Arrays.fill(dp, 1);
        for (int it = 0; it < n - 1; it++) {
            long[] nxt = new long[26];
            for (int c = 0; c < 26; c++)
                for (int cp = Math.max(0, c - d); cp <= Math.min(25, c + d); cp++)
                    nxt[c] = (nxt[c] + dp[cp]) % MOD;
            dp = nxt;
        }
        long s = 0; for (long v : dp) s = (s + v) % MOD;
        return (int) s;
    }
}

class Solution {
public:
    int numberOfBalancedStrings(int n, int d) {
        const long long MOD = 1'000'000'007;
        vector<long long> dp(26, 1);
        for (int it = 0; it < n - 1; ++it) {
            vector<long long> nxt(26, 0);
            for (int c = 0; c < 26; c++)
                for (int cp = max(0, c - d); cp <= min(25, c + d); cp++)
                    nxt[c] = (nxt[c] + dp[cp]) % MOD;
            dp = nxt;
        }
        long long s = 0;
        for (long long v : dp) s = (s + v) % MOD;
        return (int) s;
    }
};

You call a number beautiful if it contains at least 1 bit '0' and at most 3 bits '0' in its binary representation. For example, 5 (101) and 8 (1000) are beautiful numbers but numbers like 15 (1111), and 16 (10000) are not. Strings in parentheses are the corresponding binary representations. You are given Q queries of the type L, R. Consider all beautiful numbers between the range L and R (inclusive). Find the sum of cubes of all such beautiful numbers. Since the sum can be very large, output it modulo 998244353. Note: Assume 1-based indexing. Do not count leading zeros in binary representation. x modulo y means the remainder when x is divided by y. In particular, if x modulo y = z, then (x-z) is divisible by y and 0 ≤ z Function Description Complete the function sumOfCubesOfBeautifulNumbers in the editor. sumOfCubesOfBeautifulNumbers has the following parameters:

• long[][] queries: a 2D array of queries with each query containing two integers L and R Returns long integer: the sum of cubes of beautiful numbers in range L and R (inclusive) modulo 998244353 Input Format The first line contains a single integer Q denoting the number of queries. The next Q lines follow. For each line: The first line contains two space-separated integers denoting L and R. Output Format Print Q space-separated integers, where the integer represents the sum of cubes of beautiful numbers in range L and R (inclusive). Do not forget to take modulo 998244353.

Constraints

• 1 ≤ Q ≤ 2*10⁵
• 1 ≤ L ≤ R ≤ 10¹⁸

Example 1

Input:

queries = [[5, 8], [10, 15]]

Output:

[153, 0]

Explanation: For the first query, the beautiful numbers between 5 and 8 are 5 (101) and 8 (1000). Their cubes are 125 and 512 respectively. The sum of cubes is 637. Taking modulo 998244353, the result is 637. For the second query, there are no beautiful numbers between 10 and 15 as all numbers have either no '0' bits or more than 3 '0' bits in their binary representation. Hence, the sum is 0.