Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers. The digits must remain in the order given and the entire string must be used. Each number must be in the range 2 to 10⁸ inclusive, and may not contain leading zeros. Since the answer can be large, return the answer modulo 10⁹ + 7.

Note: The trailing string does not contain leading zeros.

Example: s = "11375" — can be split into primes 3 different ways: [11, 37, 5], [11, 3, 7, 5], [113, 7, 5].

解法

在字符串上 DP：f[i] 表示把 s[0..i-1] 切成质数的方案数。转移：枚举末段 s[j..i-1] 长度 ≤ 9(值 ≤ 10⁸ 至多 9 位)，若是无前导零的质数则 f[i] += f[j]。最坏复杂度 O(n × 9 × sqrt(10⁸))，瓶颈在素性判断。

from sympy import isprime
MOD = 10**9 + 7

def countPrimeStrings(s):
    n = len(s)
    f = [0] * (n + 1)
    f[0] = 1
    for i in range(1, n + 1):
        for j in range(max(0, i - 9), i):
            sub = s[j:i]
            if len(sub) > 1 and sub[0] == '0': continue
            v = int(sub)
            if 2 <= v <= 10**8 and isprime(v):
                f[i] = (f[i] + f[j]) % MOD
    return f[n]

class Solution {
    static final int MOD = 1_000_000_007;
    public int countPrimeStrings(String s) {
        int n = s.length();
        long[] f = new long[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = Math.max(0, i - 9); j < i; j++) {
                if (i - j > 1 && s.charAt(j) == '0') continue;
                long v = Long.parseLong(s.substring(j, i));
                if (v >= 2 && v <= 100_000_000L && isPrime(v)) f[i] = (f[i] + f[j]) % MOD;
            }
        }
        return (int) f[n];
    }
    private boolean isPrime(long x) {
        if (x < 2) return false;
        for (long i = 2; i * i <= x; i++) if (x % i == 0) return false;
        return true;
    }
}

int countPrimeStrings(string s) {
 const int MOD = 1e9 + 7;
 auto isPrime = [](long long x) {
 if (x < 2) return false;
 for (long long i = 2; i * i <= x; ++i) if (x % i == 0) return false;
 return true;
 };
 int n = s.size();
 vector<long long> f(n + 1, 0);
 f[0] = 1;
 for (int i = 1; i <= n; ++i) {
 for (int j = max(0, i - 9); j < i; ++j) {
 if (i - j > 1 && s[j] == '0') continue;
 long long v = stoll(s.substr(j, i - j));
 if (v >= 2 && v <= 100000000LL && isPrime(v)) f[i] = (f[i] + f[j]) % MOD;
 }
 }
 return f[n];
}

Given three strings text, prefixString, and suffixString, find:

• prefixScore: the longest substring of text matching the end of prefixString.
• suffixScore: the longest substring of text matching the beginning of suffixString.

Sum the lengths of the two strings to get the textScore. The substring of text that begins with the matching prefix and ends with matching suffix, and has the highest textScore, is the correct value to return. If there are other substrings with equal textScore, return the lexicographically lowest substring.

Note: if the prefix and suffix overlap, return only the substring of text, not prefix + suffix.

解法

对 text 中每个起点 i 求最长前缀匹配长度(text[i..i+k-1] == prefixString[-k:] 的最大 k)；同理对每个终点 j 求最长后缀匹配(text[j-k+1..j] == suffixString[0..k-1])。在不重叠的前缀/后缀端点上配对使得总长最大，平局取字典序最小子串。复杂度 O(|text| × min(|prefix|,|suffix|))。

def getSubstring(text, prefixString, suffixString):
    n = len(text)
    pref_match = [0] * n
    for i in range(n):
        k = 0
        while k < min(len(prefixString), n - i) + 1:
            if k == 0 or text[i:i+k] == prefixString[-k:]:
                k += 1
            else:
                break
        pref_match[i] = k - 1
    suf_match = [0] * n
    for i in range(n):
        k = 0
        while k < min(len(suffixString), i + 1) + 1:
            if k == 0 or text[i-k+1:i+1] == suffixString[:k]:
                k += 1
            else:
                break
        suf_match[i] = k - 1
    best_score, best_str = -1, ""
    for l in range(n):
        for r in range(l, n):
            ps, ss = pref_match[l], suf_match[r]
            if ps == 0 or ss == 0: continue
            if l + ps - 1 > r or r - ss + 1 < l: continue
            score = ps + ss
            sub = text[l:r+1]
            if score > best_score or (score == best_score and sub < best_str):
                best_score, best_str = score, sub
    return best_str

class Solution {
    public String getSubstring(String text, String pref, String suf) {
        int n = text.length(); String best = ""; int bestScore = -1;
        for (int l = 0; l < n; l++) for (int r = l; r < n; r++) {
            int ps = 0, ss = 0;
            for (int k = 1; k <= Math.min(pref.length(), r - l + 1); k++)
                if (text.substring(l, l + k).equals(pref.substring(pref.length() - k))) ps = k;
            for (int k = 1; k <= Math.min(suf.length(), r - l + 1); k++)
                if (text.substring(r - k + 1, r + 1).equals(suf.substring(0, k))) ss = k;
            if (ps == 0 || ss == 0) continue;
            int sc = ps + ss;
            String sub = text.substring(l, r + 1);
            if (sc > bestScore || (sc == bestScore && sub.compareTo(best) < 0)) { bestScore = sc; best = sub; }
        }
        return best;
    }
}

string getSubstring(string text, string pref, string suf) {
 int n = text.size();
 string best = ""; int bestScore = -1;
 for (int l = 0; l < n; ++l) for (int r = l; r < n; ++r) {
 int ps = 0, ss = 0;
 for (int k = 1; k <= min((int)pref.size(), r - l + 1); ++k)
 if (text.substr(l, k) == pref.substr(pref.size() - k)) ps = k;
 for (int k = 1; k <= min((int)suf.size(), r - l + 1); ++k)
 if (text.substr(r - k + 1, k) == suf.substr(0, k)) ss = k;
 if (ps == 0 || ss == 0) continue;
 int sc = ps + ss;
 string sub = text.substr(l, r - l + 1);
 if (sc > bestScore || (sc == bestScore && sub < best)) { bestScore = sc; best = sub; }
 }
 return best;
}

The NLP enthusiasts of Hackerland are working on a string transformation algorithm. In a single operation, a string s can be transformed into another string by removing a suffix of the string and adding the removed suffix in front of the remaining string. For example, the string "abcd" can be transformed to "cdab" by removing the suffix "cd" and adding it to the front of the remaining string "ab".

Given two strings src and target of lowercase English characters and an integer k, find the number of ways to transform the string src to the string target using the given algorithm in exactly k steps. Since the answer can be large, report it modulo 10⁹ + 7.

Two ways are considered different if the sequence of indices chosen for breaking the suffix is different at 1 or more steps for the two ways.

解法

每步操作都是 src 的循环旋转。预处理 t = src 的旋转中等于 target 的个数。设 f[k] 为走 k 步后停在等于 target 的旋转上的方案数，g[k] 为停在不等的方案数。递推：

f[k] = f[k-1] * (t - 1) + g[k-1] * t
g[k] = f[k-1] * (n - t) + g[k-1] * (n - 1 - t)

复杂度 O(n + k)。

MOD = 10**9 + 7

def get_num_ways(src, target, k):
    n = len(src)
    t = sum(1 for i in range(n) if (src + src)[i:i+n] == target)
    f, g = (1, 0) if src == target else (0, 1)
    for _ in range(k):
        f, g = (f * (t - 1) + g * t) % MOD, (f * (n - t) + g * (n - 1 - t)) % MOD
    return f

class Solution {
    static final int MOD = 1_000_000_007;
    public int getNumWays(String src, String target, int k) {
        int n = src.length();
        String ss = src + src;
        int t = 0;
        for (int i = 0; i < n; i++) if (ss.substring(i, i + n).equals(target)) t++;
        long f = src.equals(target) ? 1 : 0;
        long g = src.equals(target) ? 0 : 1;
        for (int i = 0; i < k; i++) {
            long nf = (f * ((t - 1 + MOD) % MOD) + g * t) % MOD;
            long ng = (f * (n - t) + g * ((n - 1 - t + MOD) % MOD)) % MOD;
            f = nf; g = ng;
        }
        return (int) f;
    }
}

int getNumWays(string src, string target, int k) {
 const int MOD = 1e9 + 7;
 int n = src.size();
 string ss = src + src;
 int t = 0;
 for (int i = 0; i < n; ++i) if (ss.substr(i, n) == target) ++t;
 long long f = (src == target) ? 1 : 0, g = (src == target) ? 0 : 1;
 for (int i = 0; i < k; ++i) {
 long long nf = (f * (t - 1 + MOD) + g * t) % MOD;
 long long ng = (f * (n - t) + g * (n - 1 - t + MOD)) % MOD;
 f = nf; g = ng;
 }
 return f;
}

There are n chocolates and the weight of the chocolates is given as an array of integers weights[n], where weights[i] denote the weight of the iᵗʰ chocolate. Every day, one can pick one chocolate, eat half of it, and put the remaining half back. Find the minimum total weight of the remaining chocolates after d days. Note that one can eat the same chocolate multiple times. The weight of the part eaten can be calculated as floor(weights[i] / 2).

Given a string of lowercase letters in the range ascii['a'-'z'], determine the number of substrings that can be created where every letter is a vowel and every vowel is present at least once. The vowels are {'a','e','i','o','u'}. A substring is a contiguous group of characters.

The data analysts of Hackerland want to schedule some long-running tasks on remote servers optimally to minimize the cost of running them locally. The analysts have two servers, a paid one and a free one. The free server can be used only if the paid server is occupied.

The iᵗʰ task is expected to take time[i] units of time to complete and the cost of processing the task on the paid server is cost[i]. The task can be run on the free server only if some task is already running on the paid server. The cost of the free server is 0 and it can process any task in 1 unit of time.

Find the minimum cost to complete all the tasks if tasks are scheduled optimally.

The city of Hackerland can be represented with an even number n of houses arranged in a row. A painter must paint the houses using at most three colors. The following conditions must hold true:

• No two adjacent houses are the same color.
• The houses which are at the same distance from both ends must be the same color (i.e., position i and position n - 1 - i get the same color).

Find the number of ways to paint the houses using at most three colors. Since the answer can be large, report it modulo 10⁹ + 7.

Given the length of a word (wordLen) and the maximum number of consecutive vowels that it can contain (maxVowels), determine how many unique words can be generated. Words will consist of English alphabetic letters a through z only. Vowels are v ∈ {a,e,i,o,u}, consonants are c (the remaining 21 letters).

Return the answer modulo 10⁹ + 7.

An employee has to work exactly as many hours as they are told to each week, scheduling no more than a given daily maximum number of hours. On some days, the number of hours worked will be given. The employee gets to choose the remainder of their schedule, within the given limits.

A completed schedule consists of exactly 7 digits in the range 0 to 8 that represent each day's work hours. A pattern string similar to the schedule is given, but some of its digits are replaced by a question mark ?. Given a maximum number of hours that can be worked in a day, replace the question marks with digits so that the sum of the scheduled hours is exactly the hours that must be worked in a week.

Return all possible work schedules as a list of strings, sorted ascending.

Given a list of employees where each is assigned a numeric evaluation score, use the selection process below to find the sum of scores of selected employees.

1. The employee with the highest score among the first k employees or the last k employees in the score list is selected.
2. The selected employee is removed from the score list.
3. The process continues to select the next employee until the team_size is achieved.

Notes:

1. In case multiple employees have the same highest score, the employee with the lowest index is selected.
2. If there are fewer than k employees, the entire list is available for selection.

During the day, a supermarket receives n phone calls from customers placing orders. Each call i has a known start[i], duration[i], and volume[i]. Only one call can be in progress at any time, and an unanswered call is lost. Choose a non-overlapping subset of calls so that the total order volume is maximized; return that maximum.

Example

start = [10, 5, 15, 18, 30]
duration = [30, 12, 20, 35, 35]
volume = [50, 51, 20, 25, 10]

Call 1 spans [10, 40], call 2 [5, 17], call 3 [15, 35], call 4 [18, 53], call 5 [30, 65]. Picking calls 2 and 4 yields 51 + 25 = 76, the maximum.

Constraints

1 ≤ n ≤ 10⁵, 1 ≤ start[i], duration[i], volume[i] ≤ 10⁹.

A test needs to be prepared on the HackerRank platform with questions from different sets of skills to assess candidates. Given an array, skills, of size n, where skills[i] denotes the skill type of the i^th question, select skills for the questions on the test. The skills should be grouped together as much as possible. The goal is to find the maximum length of a subsequence of skills such that there are no more than k unequal adjacent elements in the subsequence. Formally, find a subsequence of skills, call it x, of length m such that there are at most k indices where x[i] ≠ x[i+1] for all 0 ≤ i Function Description Complete the function findMaxLengthin the editor.findMaxLength` has the following parameters:

• 1. int skills[n]: the different skill types
• 2. int k: the maximum count of unequal adjacent elements Returns int: the maximum value of m

Constraints

• 1 ≤ n ≤ 2 * 10³
• 1

Example 1

Input:

skills = [1, 1, 2, 3, 2, 1]
k = 2

Output:

5

Explanation: The longest possible subsequence is x = [1, 1, 2, 2, 1]. There are only two indices where x[1] ≠ x[2] and x[3] ≠ x[4]. Return its length, 5.

There are n particles present in a space and an array, initialEnergy[n]. The finalEnergy[i] of the i^th particle is max(initialEnergy[i] - barrier, 0). The goal is to find the maximum possible integer value of the barrier such that the sum of final energies of the particles is greater than or equal to a given threshold th. Function Description Complete the function getMaxBarrier in the editor. getMaxBarrier has the following parameter(s):

• 1. int initialEnergy[n]: the initial energies of the particles
• 2. int th: the threshold Returns int: the maximum integer value of the barrier such that the sum of energies of all the particles is greater than or equal to th

Constraints

2 ≤ n ≤ 10⁵ 1 ≤ initialEnergy[i] ≤ 10⁹ 1 ≤ th ≤ 10¹⁴ It is guaranteed that a non-negative value of barrier will exist in each case, i.e., ∑initialEnergy[i] for all i from 0 to n-1 is greater than or equal to threshold th.

Example 1

Input:

initialEnergy = [4, 8, 7, 2, 1]
th = 9

Output:

3

Explanation: Test barrier values of 0 through 4.

• These columns in the image above are calculated for each value in initialEnergy. Each finalEnergy[i] is max(this value, 0), so negative values are not part of the sums. The maximum value of barrier for which the sum of final energies of all particles is greater than or equal to th is 3.

Example 2

Input:

initialEnergy = [5, 2, 13, 10]
th = 8

Output:

7

Explanation: With the initial energies provided and the threshold of 8, we start testing different barrier values: barrier initialEnergy sum of to test - barrier energies final 6 -1 -4 7 4 11 7 -2 -5 6 3 9 8 -3 -6 5 2 7

Example 3

Input:

initialEnergy = [3, 9, 7]
th = 6

Output:

5

The city of Hackerland is represented by a grid with n rows and m columns, where empty cells are marked with "*", and blocked cells are marked with '#'. Travel is only possible through empty cells. The inhabitants need to travel from a starting cell marked by 'S' to an ending cell marked by 'E'. They can jump any integer length k in four directions: up, down, left, and right. If the jump length k is greater than 1, the next jump must continue in the same direction. For example, a hacker can jump 3 units to the right, followed by 1 unit to the right, and then 3 units to the left. However, they cannot jump 3 units to the right followed by 1 unit to the left, as direction changes are not allowed if the previous jump was longer than 1 unit. The last jump in any sequence must always be of length 1. Jumps can be made over blocked cells as long as both the starting and ending cells of the jump are empty. Given the map of Hackerland as a 2D matrix grid containing exactly one 'S' and one 'E', determine the minimum number of jumps required to travel from 'S' to 'E'. Return -1 if it is not possible. Function Description Complete the function getMinJumps in the editor with the following parameter(s):

• grid[n][m]: an array of strings Returns int: the minimum number of jumps to reach cell 'E' starting from 'S', or -1 if it is not possible Constraints
• 2 ≤ n, m ≤ 100
• The strings will have only '*', '#', 'S', and 'E'. There will be only one 'S' and one 'E'.

Constraints

2 ≤ n, m ≤ 100

There are n jobs that can be executed in parallel on a processor, where the execution time of the j^th job is executionTime[j]. To speed up execution, the following strategy is used. In one operation, a job is chosen, the major job, and is executed for x seconds. All other jobs are executed for y seconds where y Function Description Complete the function getMinimumOperationsin the editor below.getMinimumOperations` has the following parameters:

• int executionTime[n]: the execution times of each job
• int x: the time for which the major job is executed
• int y: the time for which all other jobs are executed Returns int: the minimum number of operations in which the processor can complete the jobs

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ executionTime[i] ≤ 10⁹
• 1 ≤ y

Given an array of strings, each of the same length, and a target string, construct the target string using characters from the strings in the given array in such a way that the indices of the characters used are in a strictly increasing sequence. Here, the index of a character is the position at which it appears in the string. Multiple characters can be used from the same string. Determine the number of ways to construct the target string. Two constructions are considered different if either the sequences of indices they use are different or the sequences are the same but there exists a character at some index that is chosen from a different string. Return the value modulo (10⁹ + 7). Function Description Complete the function numWays in the editor below. numWays has the following parameters:

• 1. String words[n]: an array of strings
• 2. String target: the target string Returns int: an integer representing the number of ways, modulo (10⁹ + 7)

Constraints

• 1 ≤ n ≤ 10³
• 1 ≤ length of words[i] ≤ 3000
• All words[i] are of equal length per test case.
• The sum of the lengths of all words[i] is ≤ 10⁵.
• 1 ≤ length of target ≤ length of words[i]
• All characters are lowercase English letters.

Example 1

Input:

words = ["valya", "lyglb", "vldoh"]
target = "val"

Output:

4

Explanation: There are 4 ways to construct the string "val" such that the indices will be in strictly increasing order.

1. Select the 1st character of "valya", the 2nd character of "valya" and the 3rd character of "valya".
2. Select the 1st character of "valya", the 2nd character of "valya" and the 4th character of "lyglb".
3. Select the 1st character of "valya", the 2nd character of "valya" and the 4th character of "vldoh".
4. Select the 1st character of "vldoh", the 2nd character of "valya" and the 3rd character of "valya".

Example 2

Input:

words = ["adc", "aec", "efg"]
target = "ac"

Output:

4

Explanation: There are 4 ways to reach the target:

1. Select the 1st character of "adc" and the 3rd character of "adc".
2. Select the 1st character of "adc" and the 3rd character of "aec".
3. Select the 1st character of "aec" and the 3rd character of "adc".
4. Select the 1st character of "aec" and the 3rd character of "aec".

A pair of integers (x, y) is perfect if both of the following conditions are met: min(|x - y|, |y - x|) ≤ min(|x|, |y|) max(|x - y|, |y - x|) > max(|x|, |y|) Given an array arr of length n, find the number of perfect pairs (arr[i], arr[j]) where 0 ≤ i Function Description Complete the function getPerfectPairsCountin the editor below.getPerfectPairsCount` has the following parameter:

• int arr[n]: an array of integers Returns int: the number of perfect pairs

Constraints

• 2 ≤ n ≤ 2*10⁵
• -10⁹ ≤ arr[i] ≤ 10⁹

Given a series of integer intervals, determine the size of the smallest set that contains at least 2 integers within each interval. Function Description Complete the function interval in the editor. interval has the following parameters:

• 1. int first[n]: each element represents the start of intervali
• 2. int last[n]: each element represents the end of intervali Returns int: the size of the smallest interval possible

Constraints

• 1 ≤ n ≤ 10⁵
• 0 ≤ first[i] ≤ last[i] ≤ 10⁹

Example 1

Input:

first = [0, 1, 2]
last = [2, 3, 3]

Output:

3

Explanation: The intervals start at first[i] and end at last[i]. Both intervals 0 and 1 contain 1 and 2. These are the only two integers that interval 0 shares, so both integers must be included in the answer set. Both intervals 1 and 2 contain 2 and 3. These are the only two values that interval 2 shares. The smallest set that contains at least 2 integers from each interval is {1, 2, 3}.

The developers of Hackerland are working on an array reduction algorithm that takes in an array of n integers say arr and does the following until the array arr is empty: Initialize an array result as an empty array Choose an integer k such that 1 ≤ k ≤ length of the array Append the MEX of the first k elements of the array arr to the array result Remove first k elements of the array arr Given an array arr, find the lexicographically maximum array result that can be obtained using the above algorithm. Note: An array x is lexicographically greater than an array y if in the first position where x and y differ x_i > y_i or if |x| > |y| and y is a prefix of x (where |x| denotes the size of the array x). The MEX of a set of non-negative integers is the minimal non-negative integer such that it is not in the set. For example, MEX({1,2,3}) = 0 and MEX({0,1,2,4,5}) = 3.

Constraints

• 1 ≤ n ≤ 10⁵
• 0 ≤ arr[i] ≤ n

In many real-world applications, the problem of finding a pair of closest points arises. In the real world, data is usually distributed randomly. Given n points on a plane, randomly generated with uniform distribution, find the squared shortest distance between pairs of these points. Function Description Complete the function closestSquaredDistance in the editor below. closestSquaredDistance has the following parameter(s): int x[n]: each x[i] denotes the x coordinate of the ith point int y[n]: each y[i] denotes the y coordinate of the ith point Returns long: a long integer that denotes the squared shortest distance between the pairs of points

Constraints

• 2 ≤ n
• either n ≤ 1000 or n = 10⁵
• values of x[i] and y[i] are randomly generated with uniform distribution from the range [0, 10⁹-1]

Example 1

Input:

x = [0, 1, 2]
y = [0, 1, 4]

Output:

2

Explanation: There are 3 points with x coordinates x = [0, 1, 2] and y coordinates y = [0, 1, 4]. The points have the xy coordinates (0, 0), (1, 1), and (2, 4). The closest points are (0, 0) and (1, 1), and their squared shortest distance is (1-0)^2 + (1-0)^2 = 2.

A special string of length n consists of characters 0-9 only. Its characters can only be accessed sequentially i.e the first '1' chosen is the leftmost '1' in s. There is an array arr of m strings, also consisting of characters 0-9. Calculate the minimum number of characters needed from s to construct a permutation of each of the strings in arr. Return an array of integers where the ith element denotes the minimum length of a substring that contains a permutation of the ith string in arr. If a string cannot be constructed, return -1 at that index. Function Description Complete the function countMinimumCharacters in the editor below. countMinimumCharacters has the following parameters:

• String s: the special string of length n
• String[] arr: an array of strings Returns int[]: an array of integers where each element denotes the minimum length of a substring needed to construct a permutation of the string at that index in arr, or -1 if it cannot be constructed

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 2*10⁴
• 1 ≤ sum of the lengths of strings in arr ≤ 5*10⁵
• All strings consist of characters '0'-'9' only.

Example 1

Input:

s = "064819848398"
arr = ["088", "364", "07"]

Output:

[7, 10, -1]

Explanation: Consider n=12, s="064819848398", m=3, arr=["088", "364", "07"]:

• To construct "088", access the first 7 characters ("0648198") of the special string and use only '0', '8', and '8'. Since the characters can be rearranged, the result is "808".
• To construct "364", access the first 10 characters ("0648198483") of the special string and use only '6', '4', and '3'. Rearrange to match "364".
• String "07" cannot be constructed from the special string. No '7' is available. The return array is [7, 10, -1]. Note that only bolded characters are used to construct the strings.

Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers. The digits must remain in the order given and the entire string must be used. Each number must be in the range 2 to 10⁶ inclusive, and may not contain leading zeros. Since the answer can be large, return the answer modulo (10⁹ + 7). Note: The initial string does not contain leading zeros. Function Description Complete the function countPrimeStrings in the editor below. countPrimeStrings has the following parameter(s):

• string s: a string of digits Returns int: the number of ways the string can be split into primes, modulo 1000000007, (10⁹+7)

Constraints

• 1 ≤ length of s ≤ 10⁵
• there should be more of them. I will add once find more reliable reference

Example 1

Input:

s = "11375"

Output:

3

Explanation: This string can be split into primes 3 different ways: [11, 37, 5], [11, 3, 7, 5], [113, 7, 5].

The city of Hackerland can be represented with an even number n houses arranged in a row. A painter must paint the houses using at most three colors. The following conditions must hold true: No two adjacent houses are the same color. The houses which are at the same distance from both ends must not be colored with the same color. For example, n=6 then houses will be [1,2,3,4,5,6], so the houses at the same distance from both the ends will be [1,6], [2,5], [3,4]. The task is to find the number of ways to paint the houses using at most three colors such that both the above conditions hold true. Since the answer can be large, report it modulo 10⁹ + 7. Two ways are considered different if at least one house is colored differently. Function Description Complete the countWaysToColorHouses function in the editor. countWaysToColorHouses takes in a single parameter:

• int n, the number of houses

Constraints

• 1 ≤ n ≤ 100000
• n is an even integer

Example 1

Input:

n = 4

Output:

18

Explanation: For n = 4, some of the possible valid arrangements are:

• (color1, color2, color3, color2)
• (color1, color3, color1, color3) The number of ways to paint 4 houses using three colors is 18. Return 18 modulo (10⁹ + 7) which is 18.

Example 2

Input:

n = 2

Output:

6

Explanation: The valid arrangements for 2 houses are: (color1, color2) (color1, color3) (color2, color1) (color3, color1) (color2, color3) (color3, color2)

Example 3

Input:

n = 4

Output:

18

Explanation: Total valid arrangements for 4 hourses are 18. Some of the valid arrangements are: {color1, color2, color1, color2} {color1, color3, color1, color3} {color2, color1, color2, color1} {color3, color1, color3, color1} {color2, color3, color2, color3} {color3, color2, color3, color2}

You are given n roles. Role i has a list of direct privileges privileges[i]. You are also given inheritance relations grants, where each pair [u, v] means role v inherits every privilege from role u. The inheritance graph is a directed acyclic graph. A role's effective privileges are all privileges from its ancestors plus its own direct privileges. Return the effective privileges for every role. Remove duplicates within each role and return each role's privilege list in lexicographic order.

Constraints

• 1 ≤ privileges.length ≤ 2 * 10⁵
• 0 ≤ grants.length ≤ 2 * 10⁵
• Each grant is a pair [u, v] with 0 ≤ u, v < privileges.length.
• The role inheritance graph is a DAG.
• Privilege strings are non-empty tokens without spaces.

Example 1

Input:

privileges = [["A"],["B"],["C"]]
grants = [[0,1],[1,2]]

Output:

[["A"],["A","B"],["A","B","C"]]

Explanation: Role 1 inherits role 0, and role 2 inherits both role 1 and role 0 transitively.

Example 2

Input:

privileges = [["READ"],["WRITE"],["DEPLOY"],["AUDIT"]]
grants = [[0,2],[1,2],[2,3]]

Output:

[["READ"],["WRITE"],["DEPLOY","READ","WRITE"],["AUDIT","DEPLOY","READ","WRITE"]]

Example 3

Input:

privileges = [["A","A"],["A"],[]]
grants = [[0,1],[1,2]]

Output:

[["A"],["A"],["A"]]

You will be given an integer array and a threshold value. The threshold represents the maximum length of subarrays that may be created for the challenge. Each subarray created has a cost equal to the maximum integer within the subarray. Partition the entire array into subarrays with lengths less than or equal to the threshold, and do it at a minimum cost. The subarrays are to be chosen from contiguous elements, and the given array must remain in its original order. Function Description Complete the function efficientCost in the editor. efficientCost has the following parameters:

• 1. int[] arr: an integer array
• 2. int threshold: the maximum length of subarrays Returns int: the minimum cost to partition the array

Constraints

• 1 ≤ len(arr) ≤ 5000
• 1 ≤ arr[i] ≤ 10⁹
• 1 ≤ threshold ≤ len(arr)

Example 1

Input:

arr = [1, 3, 4, 5, 2, 6]
threshold = 3

Output:

10

Explanation: Here are some ways to partition the arrays as an example. The lengths of partitions can differ as long as none are longer than threshold.

• Partition into 6 subarrays of length 1 as [1], [3], [4], [5], [2], [6]. The total cost is 1 + 3 + 4 + 5 + 2 + 6 = 21.
• Partition into 4 subarrays of various lengths: [1, 3], [4], [5], [2, 6]. The total cost is 3 + 4 + 5 + 6 = 18.
• Partition into 3 subarrays of length 2 as: [1, 3], [4, 5], [2, 6]. The total cost is 3 + 5 + 6 = 14
• Partition into 2 subarrays of length 3 as: [1, 3, 4], [5, 2, 6]. The total cost is 4 + 6 = 10. The optimal cost is 10.

A supercomputer has several processors to deploy for execution. They are arranged sequentially in a row from 1 to n. The efficiency of each processor depends upon the order of deployment of its adjacent processors. For the i^th processor, the efficiency of the i^th processor is no_adjacent[i], one_adjacent[i], or both_adjacent[i] when neither, one, or both adjacent processors is deployed before processor i. Note: The 1^st and n^th processors can only have one adjacent. Find the maximum possible sum of efficiencies amongst all possible orders of deployment. Function Description Complete the function maxEfficiency in the editor. maxEfficiency has the following parameters: int noAdjacent[n]: an array of integers int oneAdjacent[n]: an array of integers int bothAdjacent[n]: an array of integers Returns long_int: the maximum possible sum of efficiencies

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ no_adjacent[i], one_adjacent[i], both_adjacent[i] ≤ 10⁹

Example 1

Input:

noAdjacent = [1, 2, 3, 4]
oneAdjacent = [4, 4, 2, 1]
bothAdjacent = [0, 1, 1, 0]

Output:

13

Explanation: Consider the following orders of deployment (1-based indexing):

• The deployment sequence is {1 → 3 → 4 → 2}. Then, the sum of efficiencies = no_adjacent[1] + no_adjacent[3] + one_adjacent[4] + both_adjacent[2] = 1 + 3 + 1 + 1 = 6.
• Let the deployment sequence be {4 → 2 → 1 → 3}, no_adjacent[4] + no_adjacent[2] + one_adjacent[1] + both_adjacent[3] = 4 + 2 + 4 + 1 = 11.
• Let the deployment sequence be {4 → 3 → 2 → 1}, one_adjacent[3] + one_adjacent[2] + 2 + 2 + 4 + 1 = 7.
• Similarly, other deployment orders can be performed. Amongst all possible deployments, the maximum possible sum of efficiencies is 13.

Example 2

Input:

noAdjacent = [2, 1, 3]
oneAdjacent = [4, 2, 1]
bothAdjacent = [1, 2, 3]

Output:

9

Explanation: Several ways to deploy processors are:

• let dethe deployment sequence be {1 → 2 → 3}

• The sum of efficiencies = no_adjacent[1] + one_adjacent[2] ++ 2 + 1 = 5

• {1 → 3 → 2_, no_adjacent[1] + no_adjacent[3] + both_adjacent[2] = 2 + 3 + 2 = 7
• {2 → 1 → 3}, no_adjacent[2] + one_adjacent[1] ++ 4 + 1 = 6
• {2 → 3 → 1}, no_adjacent[2] + one_adjacent[3] ++ 1 + 4 = 6
• {3 → 2 → 1}, no_adjacent[3] + one_adjacent[2] ++ 2 + 4 = 9
• {3 → 1 → 2}, no_adjacent[3] + no_adjacent[1] + both_adjacent[2] = 3 + 2 + 2 = 7

Example 3

Input:

noAdjacent = [1, 6]
oneAdjacent = [2, 3]
bothAdjacent = [3, 2]

Output:

8

Explanation: Some ways to deploy processors are:

• Let the deployment sequence be {1 → 2}. Then, sum of efficiencies = no_adjacent[1] ++ 3 = 4
• {2 → 1}, no_adjacent[2] ++ 2 = 8

Write a Python Program using SciPy that solves the equation X = A*B*C, given X, B, and C, as input. In the equation, X is a scalar, A is the unknown 1x2 vector, B is a 2x2 matrix, and C is a 2x1 vector. The two elements of A have the relationship A[1] = 1 - A[0]. Find the value of vector A. Function Description Complete the function findA in the editor below. findA has the following parameter(s):

• float X: the value of X.
• float B[2][2]: the matrix B.
• float C[2][1]: the vector C. Returns float[2]: an array containing the two values A[0] and A[1].

Example 1

Input:

X = 0.35
B = [[3, -1], [-2, 3]]
C = [0.2, 0.8]

Output:

[0.75, 0.25]

Explanation: After solving the equation X = A*B*C under the constraints A[1] = 1 - A[0], the value of the vector A = [[0.75, 0.25]]. The values of A should be rounded to two decimal places.

There are service_nodes of different micro-services in a system with bidirectional connections in the form of a tree, where the i^th edge connects the micro-service service_from[j] and service_to[j]. Each micro-service is configured with a maximum number of live threads that can be present in its lifecycle, where the i^th micro-service can have a maximum of threads[j] threads. The micro-services adjacent to each other must have maximum threads differing by exactly 1. Some configurations were lost, and only k of the micro-services are known. This information is given as a 2D array, currentValues, of size k x 2 denoting [micro-service index, maximum threads], or, [i, threads[i]]. Find the maximum number of live threads that each micro-service can have such that the total number of live threads in the system is the minimum possible. Return an array of length service_nodes where the i^th element denotes the maximum number of live threads for the i^th micro-service. Note: It is guaranteed that the solution always exists.

Constraints

• 1 ≤ service_nodes ≤ 10⁶
• 1 ≤ service_from[i], service_to[i] ≤ service_nodes
• 1 ≤ k ≤ service_nodes
• 1 ≤ currentValues[i][0] ≤ service_nodes
• 1 ≤ currentValues[i][1] ≤ 10⁶

Example 1

Input:

service_nodes = 5
service_from = [1, 2, 3]
service_to = [2, 3, 4]
k = 3
currentValues = [[1, 3], [2, 4], [3, 3]]

Output:

[3, 4, 3, 3]

Explanation: There are 4 micro-services, and 3 edges: {1, 2}, {2, 3}, and {2, 4}. There are 3 configurations left: 1, 2, and 3 with value 3, 4, and 3 respectively on them. The initial configuration is [3, 4, 3, 3], with the maixmum live threads on adjacent micro-services differing by exactly one.

The developers are trying to optimize their horizontal pod autoscaler for their micro-services. There are n micro-services where the number of pods for the ith micro-service is pods[i]. According to traffic, the number of pods of a service can increase or decrease. Also, at specific times when there is expected traffic, all services with fewer than x pods are assigned x pods. There is an event log of size m, which is described as a 2D array logs where logs[i] is an array of integers of size = 3. The interpretation of these logs are shown.

• [1, p, x]: the number of pods of the pth micro-service is changed to x.
• [2, -1, x]: all the micro-services whose number of pods is less than x are changed to x. Find the resulting number of pods for the micro-services. Function Description Complete the function findPodCount in the editor below. findPodCount has the following parameters: int pods[n]: the number of pods for the micro-services (1 int logs[m][3]: the event log of the horizontal pod autoscaler Returns int[n]: the ith element represents the final pod count of the ith micro-service

Constraints

• 1 ≤ n ≤ 2 * 10⁵
• 1 ≤ pods[i] ≤ 10⁹
• 1 ≤ m ≤ 2 * 10⁵
• 1 ≤ p ≤ n
• 0 ≤ x ≤ 10⁹

Example 1

Input:

pods = [2, 4, 1, 4]
logs = [[1, 2, 30], [1, 3, 4], [2, -1, 10]]

Output:

[10, 30, 10, 10]

Explanation:

Example 2

Input:

pods = [3, 50, 2, 1, 10]
logs = [[1, 2, 0], [2, -1, 8], [1, 3, 20]]

Output:

[8, 8, 20, 8, 10]

Explanation: This test case example was added on 06-24-2025. Relevant source image was included in the Problem Source section below.

You are given an integer array nums and a non-negative integer k. A sequence of integers seq is called good if there are at most k indices i in the range [0, seq.length - 2] such that seq[i] ≠ seq[i + 1]. Return the maximum possible length of a good subsequence of nums. Function Description Complete the function maxLengthGoodSubsequence in the editor. maxLengthGoodSubsequence has the following parameters:

• 1. int[] nums: an array of integers
• 2. int k: a non-negative integer Returns int: the maximum possible length of a good subsequence All credits go to the incredible Lie ༊·° 𓇢𓆸

Constraints

• 1 ≤ nums.length ≤ 500
• 1 ≤ nums[i] ≤ 10⁹
• 0 ≤ k ≤ min(nums.length, 25)

Implement a simple meeting assistant. A list of strings, events[n], in the form "<person_name> <action> <start> <end>" is provided where person_name performs action from start to end, both inclusive. Times are formatted HH:MM. Find the earliest time in the day, from "00:00" to "23:59", when all people mentioned in at least one event are available for a meeting of k minutes. Report the answer as "HH:MM" or the string "-1" if it is not possible. Function Description Complete the function getEarliestMeetTime in the editor below. getEarliestMeetTime takes the following arguments:

• 1. String events[n]: event descriptors
• 2. int k: meeting duration Returns string: the earliest time for the meeting or "-1" if it is not possible

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ length of events[i] ≤ 40
• 1 ≤ k ≤ 1440
• It is guaranteed that the number of people is less than 5000.
• It is guaranteed that no person's events overlap.

Example 1

Input:

events = ["Alex sleep 00:00 08:00", "Sam sleep 07:00 13:00", "Alex lunch 12:30 13:59"]
k = 60

Output:

"14:00"

Explanation: Alex is not available until 8:00. After that, Sam is not available until 13:00. Then Alex is busy until 13:59. Return the earliest time they are both available, "14:00".

Example 2

Input:

events = ["sam sleep 12:00 23:59", "alex sleep 00:00 13:00"]
k = 1

Output:

"-1"

Explanation: There is no time when both are free.

Example 3

Input:

events = ["sam sleep 12:00 18:59", "alex gaming 00:00 11:00"]
k = 60

Output:

"19:00"

Explanation: Alex plays games from 00:00 until 11:00. If the meeting starts at 11:01, it ends at 12:01. Sam is asleep from 12:00 to 18:59.

The people in HackerLand, are getting ready for a parade. There should be no instance where a person is wearing a white-colored uniform. There is a given string color that contains lowercase English characters ('a' - 'z'). Some of the positions in the string are empty, meaning that the color of the uniform is white at that position and is denoted by the '.' character. A beautiful string is defined as a string in which all characters are the same. For example "aaa", "zzzzz", "f" are beautiful while "aba", "aaad" are not beautiful. Replace each non-colored uniform with some lowercase English character such that the total number of substrings that are beautiful maximized. Find the maximum total number of beautiful substrings after replacing every empty character. Note: A substring of a string is a contiguous subsequence of that string. Function Description Complete the function getMaxBeautifulSubstrings in the editor. getMaxBeautifulSubstrings has the following parameter(s):

• string color: the color of each uniform Returns int: the maximum number of beautiful substrings possible

Constraints

1 ≤ |color| ≤ 5000

A network security administrator must protect networks at a number of locations from cyber-attacks. Initially, the ith network has num_servers[i] servers, and money[i] funds allocated for security upgrades. To upgrade a server in the ith network, it costs upgrade[i]. Selling a server adds sell[i] to available funds. Given the arrays num_servers, money, upgrade, and sell, each with n integers, determine the maximum number of servers that can be upgraded to ensure optimal network security. The result should be an array of n integers, where the ith integer represents the maximum number of upgraded servers for the ith network system. Function Description Complete the function getMaxUpgradedServers in the editor. getMaxUpgradedServers has the following parameter(s):

• int num_servers[n]: the number of servers in each network
• int money[n]: the initial amount of money at each network location
• int sell[n]: the network-specific value of selling a server
• int upgrade[n]: the network-specific cost to upgrade a server Returns int[]: The maximum number of upgraded servers for each network

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ num_servers[i], money[i], sell[i], upgrade[i] ≤ 10⁴

Example 1

Input:

num_servers = [4, 3]
money = [8, 9]
sell = [4, 2]
upgrade = [4, 5]

Output:

[3, 2]

Explanation: Explanation is shown in above image . Hence, answer is [3, 2]~

A search engine is being trained on an algorithm for searching similar words. Given two words, source and target, characters are removed from the string source one by one following the sequence of indices defined by the permutation order[]. More formally, order[] is a permutation of length n (length of string source), and in the i^th step of the removal, the character at index order[i] is removed from the string source, while keeping the other characters at their original indices. The string target is said to be searchable in the string source, if it appears as a subsequence in the source string. Find the maximum number of characters which can be removed by following the order defined by the permutation order[], such that the string target remains searchable in the string source. Note: The removals are performed according to the order of permutation. A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example [2, 3, 1, 5, 4] is a permutation, but [1, 2, 2] is not because 2 appears twice in the array; [1, 3, 4] is also not a permutation because n = 3, but 4 appears in the array. A subsequence of a string is a string which can be formed by deleting some (can be none) of the characters from the original string without disturbing the relative positions of the remaining characters. For example, "ace" is a subsequence of "abcde" while "aec" is not. It is guaranteed that string target exists as a subsequence in the source initially. Function Description Complete the function getMaximumRemovals in the editor. getMaximumRemovals has the following parameters: int order[order_size]: the order in which characters are removed from string source string source: the initial string string target: the desired subsequence Returns int: the maximum possible removals such that target exists as a subsequence of source

Constraints

• 1 ≤ |source| ≤ 10⁵
• 1 ≤ |target| ≤ |source|
• It is guaranteed that the array order[] forms a permutation.
• It is guaranteed that the length of array order[] and string source are equal.
• It is guaranteed that string target exists as a subsequence in source initially.

Example 1

Input:

order = [7, 1, 2, 5, 4, 3, 6]
source = "abbabaa"
target = "bb"

Output:

3

Explanation: The removals occur as follows (the characters in bold show the desired subsequence, whereas "-" represents removed characters):

1. Character at index 7 is removed; source = "abbaba-" → "abbaba-". Thus, target exists as a subsequence.
2. Character at index 1 is removed; source = "-bbaba-" → "-bbaba-". Thus, target exists as a subsequence.
3. Character at index 2 is removed; source = "--baba-" → "--baba-". Thus, target exists as a subsequence.
4. Character at index 5 is removed; source = "--ba-a-" → "--ba-a-". Here, target does not exist as a subsequence. A maximum of 3 removals can be done.

Example 2

Input:

order = [1, 4, 2, 3, 5]
source = "hkbdi"
target = "kd"

Output:

1

Explanation:

1. The character at index 1 is removed; source = "-kbdi" → "-kbdi". target exists as a subsequence.
2. The character at index 4 is removed; source = "-kb-i" → "-kb-i". target does not exist as a subsequence.

Given a string containing a number of characters, find the substrings within the string that satisfy the conditions below: The substring's length should be in the inclusive interval (minLength, maxLength). The total number of unique characters should not exceed maxUnique. Using those conditions, determine the frequency of the maximum occurring substring. Function Description Complete the function getMaxFrequencySubstring in the editor. getMaxFrequencySubstring has the following parameters:

• String s: the string to analyze
• int minLength: the minimum length of the substring
• int maxLength: the maximum length of the substring
• int maxUnique: the maximum number of unique characters in the substring Returns int: the frequency of the maximum occurring substring

Constraints

An unknown urban legend for now

A taxi can take multiple passengers to the railway station at the same time. On the way back to the starting point, the taxi driver may pick up additional passengers for his next trip to the airport. A map of passenger location has been created, represented as a square matrix. The matrix is filled with cells, and each cell will have an integer value as follows: A value ≥ 0 represents a path. A value == 1 represents a passenger. A value == -1 represents an obstruction. The rules of motion of taxi are as follows: The Taxi driver starts at (0,0) and the railway station is at (n-1,n-1). Movement towards the railway station is right or down, through valid path cells. After reaching (n-1,n-1) the taxi driver travels back to (0,0) by travelling left or up through valid path cells. When passing through a path cell containing a passenger, the passenger is picked up. Once the rider is picked up the cell becomes an empty path cell. If there is no valid path between (0,0) and (n-1,n-1) then no passenger can be picked. The goal is to collect as many passengers as possible so that the driver can maximize his earnings. For example, consider the following grid: Start at the top left corner. Move right one, collecting a rider. move down one to the airport. Cell (1, 0) is blocked, so the return path is the reversed of the path to the airport. All paths have been explored, and 1 rider was collected. Returns int: maximum number of passengers that can be collected.

Constraints

• 1 ≤ n ≤ 100
• -1 ≤ mat[i][j] ≤ 1

Example 1

Input:

mat = [[0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Output:

2

Explanation: The driver can contain a maximum of 2 passengers by taking the following path: (0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (2,3) → (3,3) → (3,2) → (3,1) → (3,0) → (2,0) → (1,0) → (0,0)

Example 2

Input:

mat = [[0, 1, -1], [1, 0, -1], [1, 1, 1]]

Output:

5

Explanation: The driver can contain a maximum of 5 passengers by taking the following path: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,1) → (2,0) → (1,0) → (0,0)

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. Minimum Clicks Between Wiki Pages with Link Fetch Simulator You have a set of wiki pages where each page may link to other pages. You must implement a link fetch simulator and then compute the minimum number of clicks needed to navigate from start to target (one click follows one outgoing link). Tasks Implement get_links(page): return the list of pages directly reachable from page. Using get_links, compute the minimum clicks from start to target: If start == target, the answer is 0 If target is unreachable, return -1 Input (for this simulator-based problem) Line 1: integer m, number of directed links Next m lines: two strings u v meaning a link from u to v Last line: two strings start target get_links(page) should behave as: return all x such that an input edge page → x exists. Output One line: the minimum click count, or -1 Constraints 1 ≤ m ≤ 2*10⁵ Page names are whitespace-free strings Sample Tests (5) Input: 5 A B B C A D D C C E A C Output: 2 Input: 3 A B B C C D A D Output: 3 Input: 2 A B C D A D Output: -1 Input: 1 A A Output: 0 Input: 4 A B A C B D C D A D Output: 2 Example Input 5 A B B C A D D C C E A C Output 2 Function Description Complete solveMinimumWikiClicks. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Use the limits and requirements stated in the prompt.

Example 1

Input:

input = "5\nA B\nB C\nA D\nD C\nC E\nA C"

Output:

["2"]

Explanation: The returned string array must match the expected standard output lines for the sample input.

Given is an array consisting of n intervals. The ith interval is of type (a[i], b[i]). Also given is an integer k. Add exactly one segment (a, b) to the array such that b - a ≤ k and the modified array can be separated into the minimum number of connected sets. A set of segments (a[1], b[1]), (a[2], b[2]), ..., (a[n], b[n]) is connected if every point in the segment (min(a[1], a[2], ..., a[n]), max(b[1], b[2], ..., b[n])) is covered by some segment (a[i], b[i]) in the set. Function Description Complete the function minimumDivision in the editor. minimumDivision has the following parameters:

• 1. int a[n]: an integer array of first parameters of intervals
• 2. int b[n]: an integer array of second parameters of intervals
• 3. k: an integer denoting the maximum range of the segment that can be added Returns int: an integer denoting the minimum number of sets needed to separate the array after adding one segment.

Constraints

• 1 ≤ n ≤ 2 * 10⁵
• 1 ≤ a[i] ≤ b[i] ≤ 10⁹
• 1 ≤ k ≤ 10⁹

Example 1

Input:

a = [1, 2, 5, 10]
b = [2, 4, 8, 11]
k = 2

Output:

2

Explanation: The original intervals are (1, 2), (2, 4), (5, 8), (10, 11). Add the segment (4, 5) into the array since 5 - 4 ≤ 2. After that, we can separate the array into 2 connected sets:

• (1, 2), (2, 4), (4, 5), (5, 8)
• (10, 11)

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. Minimum Index Distance Between Person and Cake in a Ternary Array Given a 1D array A of length n where each element is in {0,1,2}: 0 means empty 1 means person 2 means cake Compute the minimum distance between any person (1) and any cake (2) in terms of index difference: [ \min_{i,j} |i-j| \quad \text{where } A[i]=1, A[j]=2 ] If there is no valid pair (the array does not contain both 1 and 2), output -1. Input Line 1: integer n Line 2: n integers describing A Output One line: the minimum distance, or -1 Constraints 1 ≤ n ≤ 2*10⁵ Sample Tests (5) Input: 5 0 1 0 2 0 Output: 2 Input: 6 1 0 0 0 2 0 Output: 4 Input: 6 1 0 2 0 2 1 Output: 1 Input: 4 0 0 0 0 Output: -1 Input: 3 2 0 2 Output: -1 Example Input 5 0 1 0 2 0 Output 2 Function Description Complete solveMinimumPersonCakeDistance. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Use the limits and requirements stated in the prompt.

Example 1

Input:

input = "5\n0 1 0 2 0"

Output:

["2"]

Explanation: The returned string array must match the expected standard output lines for the sample input.

In an array, elements at any two indices can be swapped in a single operation called a move. For example, if the array is arr = [17, 4, 8], swap arr[0] = 17 and arr[2] = 8 to get arr' = [8, 4, 17] in a single move. Determine the minimum number of moves required to sort an array such that all of the even elements are at the beginning of the array and all of the odd elements are at the end of the array. Function Description Complete the function moves in the editor below. moves has the following parameter(s):

• int arr[N]: an array of positive integers Returns int: the minimum number of moves it takes to sort an array of integers with all

Example 1

Input:

arr = [6, 3, 4, 5]

Output:

1

Explanation: The following four arrays are valid custom-sorted arrays:

• a = [6, 4, 3, 5]
• a = [4, 6, 3, 5]
• a = [6, 4, 5, 3]
• a = [4, 6, 5, 3] The most efficient sorting requires 1 move: swap the 4 and the 3.

You want to build yourself a house. The building company you hired can only build houses with sides from their specific set s. That means they can build you a square house or a rectangular one but if and only if its length and width belong to the sets. This month, they have a special promotion: they will paint the ceiling of a new house for free... but only if its area is not more than a. You want them to do it for free but you also want to be sure that the house will be comfortable and not too small. How many possible house configurations can you create to have the ceiling painted for free given the side lengths offered? There is a method to how the company decides what lengths of sides to produce. To determine n lengths of wall segments to offer, they start with a seed value s0, some variables k, b and m, and use the following equation to determine all other side lengths s_i: s_i = (( k * s_{i-1} + b)mod m+1+s_{i-1}) for 1 Function Description Complete the function paintTheCeilingin the editor.paintTheCeiling` has the following parameters:

• s0: an integer, the seed value for side lengths
• n: an integer, the number of side lengths to produce
• k: an integer
• b: an integer
• m: an integer
• a: a long integer, the maximum area for a free paint job Returns long integer: the number of possible house configurations

Constraints

• 1 ≤ n ≤ 6 x 10⁶
• 1 ≤ s_i ≤ 10⁹
• 1 ≤ k, b, m ≤ 10⁹
• 1 ≤ a ≤ 10¹⁸

Example 1

Input:

s0 = 2
n = 3
k = 3
b = 3
m = 2
a = 15

Output:

5

Explanation: Now that we have our set of lengths, we can brute force the solution using the following tests assuming a=15: s=[2,4,6] s1 s2 s1xs2 s1xs2≤a 2 2 4 True 2 4 8 True 2 6 12 True 4 2 8 True 4 4 16 False 4 6 24 False 6 2 12 True 6 4 24 False 6 6 36 False There are 5 combinations that will result in a free paint job. Brute force will not meet the time constraints on large sets.

Application logs are useful in analyzing interaction with an application and may also be used to detect suspicious activities. A log file is provided as a string array where each entry represents a money transfer in the form "sender_user_id recipient_user_id amount". Each of the values is separated by a space.

• sender_user_id and recipient_user_id both consist only of digits, are at most 9 digits long and start with non-zero digit
• amount consists only of digits, is at most 9 digits long and starts with non-zero digit Logs are given in no particular order. Write a function that returns an array of strings denoting user_id's of suspicious users who were involved in at least threshold number of log entries. The id's should be ordered ascending by numeric value. Function Description Complete the function processLogs in the editor. The function has the following parameter(s):
• 1. String logs[n]: each logs[i] denotes the i’th entry in the logs
• 2. int threshold: the minimum number of transactions that a user must have to be included in the result Returns String[]: an array of user id's as strings, sorted ascending by numeric value

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ threshold ≤ n
• The sender_user_id, recipient_user_id and amount contain only characters in the range ascii["0"-"9"].
• The sender_user_id, recipient_user_id and amount start with a non-zero digit.
• 0

There is network of radio-wave devices which can transmit waves of integer frequencies of 1, 2 or 3 units. Two devices can receive messages directly if their transmission frequencies have an absolute difference of 1, at most. The network is given by a tree having network_nodes number of devices and network_nodes - 1 number of edges. The edges are numbered from 1 to network_nodes, in the form of two arrays, network_from, and network_to respectively. There is an undirected edge from network_from[i] to network_to[i] (1 ≤ i < network_nodes). There is also an array of frequency values, frequency, of size network_nodes. Determine the longest distance between two devices that can transmit their message to each other. A device can transmit a message to another node if there is a simple path such that compatibility values of two consecutive devices differ by no more than once. If no device can transmit a message, return 0. Note: The distance between two devices is defined as the number of edges in a simple path from one node to the other. A simple path is a sequence of devices from one node to another such that each consecutive device is connected by an edge and no node is used more than once in the sequence.

Constraints

• 1 ≤ network_nodes ≤ 10⁵
• frequency[i] ∈ {1, 2, 3}
• Edges form a valid tree on nodes 1..network_nodes.

Example 1

Input:

network_nodes = 4
network_from = [1, 2, 3]
network_to = [2, 3, 4]
frequency = [1, 3, 2, 1]

Output:

2

Explanation: The graph is labeled device:frequency. Check if a message can be passed for each pair of devices and distance.

• (1, 2): The difference between frequencies, 1 and 3, is greater than 1. A message cannot be transmitted.
• (1, 3): A message cannot be transmitted due to failure at (1, 2).
• (1, 4): A message cannot be transmitted due to failure at (1, 2).
• (2, 3): The difference in frequencies, 3 and 2, is 1. A message can be transmitted.
• (2, 4): Differences are such that a message can be transmitted from 2→3 and 3→4. The distance is 2.
• (3, 4): A message can be transmitted, and the distance is 1. The longest path, and the answer, is 2.

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times: • Choose any piles[i] and remove floor(piles[i] / 2) stones from it. Notice that you can apply the operation on the same pile more than once. Return the minimum possible total number of stones remaining after applying the k operations. floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down). (ෆ˙ᵕ˙ෆ) The incredible Lie carries!

Constraints

• 1 ≤ piles.length ≤ 10⁵
• 1 ≤ piles[i] ≤ 10⁴
• 1 ≤ k ≤ 10⁵

Example 1

Input:

piles = [5, 4, 9]
k = 2

Output:

12

Explanation: Steps of a possible scenario are:

• Apply the operation on pile 2. The resulting piles are [5,4,5].
• Apply the operation on pile 0. The resulting piles are [3,4,5]. The total number of stones in [3,4,5] is 12.

Example 2

Input:

piles = [4, 3, 6, 7]
k = 3

Output:

12

Explanation: Steps of a possible scenario are:

• Apply the operation on pile 2. The resulting piles are [4,3,3,7].
• Apply the operation on pile 3. The resulting piles are [4,3,3,4].
• Apply the operation on pile 0. The resulting piles are [2,3,3,4]. The total number of stones in [2,3,3,4] is 12.

An investor has saved some money and wants to invest in the stock market. There are a number of stocks to choose from, and they want to buy at most 1 share in any company. The total invested cannot exceed the funds available. A friend who is a stock market expert has predicted the values of each stock after 1 year. Determine the maximum profit that can be earned at the end of the year assuming the predictions come true. Function Description Complete the function selectStock in the editor below. The function should return an integer that denotes the maximum profit after one year. selectStock has the following parameter(s):

• 1. saving: amount available for investment
• 2. int currentValue[n]: the current stock values
• 3. int futureValue[n]: the values of the stocks after one year

Example 1

Input:

saving = 250
currentValue = [175, 133, 109, 210, 97]
futureValue = [200, 125, 128, 228, 133]

Output:

55

Explanation: To maximize profits, the investor should buy stocks at indices 2 and 4 for an investment of 109 + 97 = 206. At the end of the year the stocks are sold for 128 + 133 = 261, so total profit is 261 - 206 = 55.

You are given an array of distinct positive integers and another array that specifies the number of left circular rotations to be performed. Rotation Rule:

• A left circular rotation shifts all elements one position to the left.
• The element at index 0 moves to the last position.
• All other elements shift left by one index. Task: For each rotation value in the rotations array:
• Perform the rotation on the original array (not cumulative).
• Determine the index of the maximum element after the rotation. Function Description Complete the function getMaxRotationIndexes. getMaxRotationIndexes has the following parameters:- int a[]: Array of distinct integers.
• int rotations[]: Array representing the number of rotations. Returns int[]: Array where each element represents the index of the maximum element after corresponding rotations.

Constraints

• 1 ≤ n, m ≤ 500000
• 1 ≤ a[i] ≤ 10⁹
• 0 ≤ rotations[i] ≤ 10⁹

Example 1

Input:

a = [1, 2, 3]
rotations = [1, 2, 3]

Output:

[1, 0, 2]

Explanation: For each rotation, the array [1, 2, 3] is rotated starting from the original (not cumulative):

• Rotation 1 → [2, 3, 1], max = 3 at index 1
• Rotation 2 → [3, 1, 2], max = 3 at index 0
• Rotation 3 → [1, 2, 3], max = 3 at index 2

A bit string is a string of bits that have values of either 1 or 0, A super bit string is a bit string made by flipping zero or more of the 0s in the bit string to 1. Given k decimal integers, convert each to a bit string that has a given length n. Generate all possible super bitstrings of each of the k bit strings. Finally, perform a union of the super bit strings of all the bit strings and determine its size. This is the number to return. Function Description Complete the function superBitstrings in the editor. superBitstrings has the following parameters:

• 1. n: the required bit string length
• 2. int[] bitStrings: an array of decimal integers Returns int: the number of unique bitstrings that can be formed from all k values provided.