Given n vertices, count the number of distinct graphs that can be formed. The graph may be disjoint (edges are optional, no need to connect all vertices). Two graphs are different if any pair of vertices differs in connection. Return the answer modulo 10⁹ + 7.

Example: for n = 4, return 64.

解法

可能的边数为 C(n, 2) = n*(n-1)/2，每条独立选择有/无，共 2^(n*(n-1)/2) 张图。模 10⁹ + 7 快速幂即可。复杂度 O(log(n²))。

def drawing_edges(n):
 return pow(2, n * (n - 1) // 2, 10**9 + 7)

class Solution {
    static long drawingEdges(int n) {
        long MOD = 1_000_000_007L, base = 2, exp = (long) n * (n - 1) / 2, res = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) res = res * base % MOD;
            base = base * base % MOD;
            exp >>= 1;
        }
        return res;
    }
}

long long drawingEdges(int n) {
 const long long MOD = 1'000'000'007LL;
 long long base = 2, exp = (long long) n * (n - 1) / 2, res = 1;
 while (exp > 0) {
 if (exp & 1) res = res * base % MOD;
 base = base * base % MOD;
 exp >>= 1;
 }
 return res;
}

Given an array d[n] of distinct integers and an integer threshold t, count the index triplets (a, b, c) satisfying both:

• d[a] + d[b] < d[c]
• d[a] + d[b] + d[c] < t

Example

d = [1, 2, 3, 4, 5], t = 8
Triplets (sorted): (1,2,4) sum=7<8 and 1+2<4 ok; (1,2,3) 1+2<3? no; (1,3,4) 4<4? no.
Answer: 1

解法

先排序。对每个 c，两个条件简化为 a + b < min(d[c], t - d[c])。在 [0, c-1] 上用双指针 l, r 数对数。复杂度 O(n²)。

def count_triplets(d, t):
    a = sorted(d)
    n = len(a)
    cnt = 0
    for c in range(2, n):
        limit = min(a[c], t - a[c])
        l, r = 0, c - 1
        while l < r:
            if a[l] + a[r] < limit:
                cnt += r - l
                l += 1
            else:
                r -= 1
    return cnt

import java.util.*;

class Solution {
    static long countTriplets(int[] d, int t) {
        int[] a = d.clone();
        Arrays.sort(a);
        int n = a.length;
        long cnt = 0;
        for (int c = 2; c < n; c++) {
            int limit = Math.min(a[c], t - a[c]);
            int l = 0, r = c - 1;
            while (l < r) {
                if (a[l] + a[r] < limit) { cnt += r - l; l++; }
                else r--;
            }
        }
        return cnt;
    }
}

#include <vector>
#include <algorithm>
using namespace std;

long long countTriplets(vector<int>& d, int t) {
 vector<int> a = d;
 sort(a.begin(), a.end());
 int n = a.size();
 long long cnt = 0;
 for (int c = 2; c < n; c++) {
 int limit = min(a[c], t - a[c]);
 int l = 0, r = c - 1;
 while (l < r) {
 if (a[l] + a[r] < limit) { cnt += r - l; l++; }
 else r--;
 }
 }
 return cnt;
}

There are n students with skill levels in skills[n]. The team must be uniform: when its members' skills are sorted in increasing order, the difference between any two consecutive skill levels is either 0 or 1. Find the maximum team size.

Example: skills = [10, 12, 13, 9, 14] → 3 (valid teams: {9, 10}, {12, 13, 14}).

解法

合法分组只包含值 v 和 v+1。用哈希表统计频次，取 max_v (cnt[v] + cnt[v+1])。复杂度 O(n)。

from collections import Counter

def max_team_size(skills):
    c = Counter(skills)
    return max(c[v] + c.get(v + 1, 0) for v in c)

import java.util.*;

class Solution {
    static int maxTeamSize(int[] skills) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int s : skills) cnt.merge(s, 1, Integer::sum);
        int best = 0;
        for (int v : cnt.keySet())
            best = Math.max(best, cnt.get(v) + cnt.getOrDefault(v + 1, 0));
        return best;
    }
}

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int maxTeamSize(vector<int>& skills) {
 unordered_map<int, int> cnt;
 for (int s : skills) cnt[s]++;
 int best = 0;
 for (auto& [v, c] : cnt) {
 int next = cnt.count(v + 1) ? cnt[v + 1] : 0;
 best = max(best, c + next);
 }
 return best;
}

In a processor queue, n tasks have priorities (single digits). CPU-bound = odd, I/O-bound = even. Allowed operation: swap two adjacent tasks if one is odd and the other is even. Return the lexicographically smallest priority sequence achievable.

Example: priority = [2, 4, 6, 4, 3, 2] → [2, 3, 4, 6, 4, 2].

Given two strings a and b, build the merged password: alternately append a char from a then b. If one string is exhausted, append the rest of the other.

Example: a = "hackerrank", b = "mountain" → "hmaocukernratainnk".

Given two sorted arrays, merge them into one non-decreasing array.

Example: a = [1, 3, 5], b = [2, 4, 6] → [1, 2, 3, 4, 5, 6].

Given a string array strArr[n] and q queries of form "l-r" (1-indexed inclusive), for each query return the count of strings in strArr[l..r] whose first and last characters are both vowels ({a, e, i, o, u}).

Example: strArr = ['aba', 'bcb', 'ece', 'aa', 'e'], queries ['1-3', '2-5'] → [2, 3].

Given event timestamps and corresponding user IDs, and a timeout t: events within t seconds of each other (per user, when sorted) belong to the same session; otherwise a new session begins. Return the total number of sessions across all users.

Example

userIds = ["a", "b", "a", "a", "b"]
timestamps = [1, 2, 5, 100, 3], t = 10
User a: [1, 5, 100] -> gap 5-1=4 same; gap 100-5=95 new. 2 sessions.
User b: [2, 3] -> 1 session.
Answer: 3

Given the head of a linked list, remove all nodes whose value is even. Return the head of the modified list.

Example: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 → 1 -> 3 -> 5 -> 7.

In a recommendation system, two algorithms produce predictions1 and predictions2 (JSON strings mapping key to value). Implement a function to find keys whose recommended products (values) differ between the two algorithms. Return those keys sorted alphabetically. Keys that appear in only one of the two also count as differing.

Example

p1 = {"hacker":"rank", "input":"output"}
p2 = {"hacker":"ranked", "input":"wrong"}
-> ["hacker", "input"]

Implement a prototype of a simple cache query handler. There are n data entries stored in the cache. Each entry is of the form [timestamp, key, value], where timestamp represents the time at which the entry was stored in the cache, key represents the ID assigned to the cache entry, and value represents the data value of the entry, an integer represented as a string. The keys assigned to the cache entries may not be unique. The cache query handler receives query requests, where each query is of the form [key, timestamp], where key represents the ID of the cache entry to find, and timestamp represents the time the entry was added. Given two 2D arrays of strings, cache_entries, and queries, of sizes n x 3 and q x 2 respectively, return an array of size q with the data values for each query.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 10⁵
• 1 ≤ int(cache_entries[i][2]) ≤ 10⁸
• cache_entries[i][0] represents a valid timestamp in the format hh:mm:ss
• size(cache_entries[i][0]) = 8
• cache_entries[i][1], is an alphanumeric value, consisting of only lowercase English letters (a-z), and digits (0-9)
• It is guaranteed that the queried [key, timestamp] pair is present in the cache.
• At a particular timestamp, there can be no duplicate keys.

Example 1

Input:

cacheEntries = [["12:30:22", "a2er5i80", "125"], ["09:07:47", "i09ju56", "341"], ["01:23:09", "a2er5i80", "764"]]
queries = [["a2er5i80", "01:23:09"], ["i09ju56", "09:07:47"]]

Output:

["764", "341"]

Explanation:

• queries[0] corresponds to the data entry at index 2, with value = "764"
• queries[1] corresponds to the data entry at index 1, with value = "341"

Example 2

Input:

cacheEntries = [["12:30:22", "a2er5i80", "125"], ["09:07:47", "i09ju56", "341"], ["01:23:09", "a2er5i80", "764"]]
queries = [["a2er5i80", "01:23:09"], ["i09ju56", "09:07:47"]]

Output:

["764", "341"]

Explanation:

• queries[0] corresponds to the data entry at index 2, with value = "764"
• queries[1] corresponds to the data entry at index 1, with value = "341"

An e-commerce company specializes in cards with sports figures on them. Each sport has different categories of cards. For instance, there might be more desirable cards with the most popular sports personalities, others with small pieces of a player's jersey attached, and so on. They have a number of each category of card and want to make some number of packets greater than 1 that each contain equal numbers of each type of card. To do this, they will add more cards of each type until each type can be divided equally among some number of packets. Determine the minimum number of additional cards needed to create a number of packets with equal type distribution. Function Description Complete the function cardPackets in the editor. cardPackets has the following parameter(s):

• int cardTypes[n]: the quantity available of card type Returns int: the minimum number of additional cards to add

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ cardTypes[i] ≤ 500

Two circles on a Cartesian plane, A and B, are each defined by three descriptors: x: the x-coordinate of the circle's center y: the y-coordinate of the circle's center R: the radius of the circle Circles A and B will both be centered either on the X-axis (i.e., Y_A = 0 and Y_B = 0, or on the Y-axis (i.e., X_A = 0 and X_B = 0), but not both. A pair of circles (A and B) will have one of the following relationship types: Touching: they touch each other at a single point Concentric: they have the same center point Intersecting: they intersect each other (touching at two points) Disjoint-Outside: disjoint with one not existing outside of the other Disjoint-Inside: disjoint with one contained inside the other (but not concentric) Function Description Complete the function circles in the editor. circles has the following parameter(s):

• string circlePairs[n]: each string contains six space-separated integers. The first three integers are X, Y, and R for circle A, and the last three are X, Y, and R for circle B. Returns string[n]: each string is the relation between the circles described in circlePairs[i]

Constraints

• 1 ≤ n ≤ 5000
• 0 ≤ X,Y,R ≤ 5000

Given an integer array nums, count how many contiguous subarrays of length at least 2 are strictly descending by exactly 1 at every step. A subarray nums[l..r] is valid if, for every index i with l ≤ i < r, we have nums[i + 1] = nums[i] - 1. Function Description Complete the function countDescendingSubarrays in the editor below. countDescendingSubarrays has the following parameter:

• int[] nums: the input array Returns long: the number of valid descending subarrays.

Constraints

The source thread did not provide explicit numeric bounds.

• nums.length ≥ 1
• Count only contiguous subarrays whose adjacent values differ by exactly -1.
• Use a wide enough integer type to store the number of valid subarrays.

Example 1

Input:

nums = [7, 6, 5, 5, 4]

Output:

4

Explanation: The valid subarrays are [7, 6], [6, 5], [7, 6, 5], and [5, 4].

Example 2

Input:

nums = [4, 3, 2, 1]

Output:

6

Explanation: Every subarray of length at least 2 is valid, so the answer is 3 + 2 + 1 = 6.

Given two integers low and high, count how many integers in the inclusive range [low, high] can be written in the form 3^x * 5^y, where x and y are non-negative integers. Each valid value should be counted once, even if there is only one way to generate it. The value 1 is valid because 1 = 3⁰ * 5⁰. Function Description Complete the function countPowerProductsInRange in the editor below. countPowerProductsInRange has the following parameters:

• long low: the lower bound of the range
• long high: the upper bound of the range Returns int: the number of integers in [low, high] that can be expressed as 3^x * 5^y.

Constraints

The source thread did not provide explicit numeric bounds.

• x and y are non-negative integers.
• Only values within the inclusive range [low, high] should be counted.
• Implementations should avoid overflow when generating powers of 3 and 5.

Two strings are said to be similar if they are composed of the same characters. For example "abaca" and "cba" are similar since both of them are composed of characters 'a', 'b' and 'c'. However "abaca" and "bcd" are not similar since they do not share all of the same letters. Given an array of strings words of length n, find the number of pairs of strings that are similar. Note:

• Each string is composed of lowercase English characters only.
• Pairs are considered index-wise, i.e., two equal strings at different indices are counted as separated pairs.
• A pair at indices (i, j) is the same as the pair at (j, i). Function Description Complete the function countSimilarPairs in the editor below. countSimilarPairs has the following parameter:
• string words[n]: an array of n strings Returns long integer: the number of similar pairs

Constraints

• 1 ≤ n ≤ 10⁵
• The Sum of the lengths of all strings does not exceed 10⁶.
• All strings consist of lowercase English char

Example 1

Input:

words = ["xyz", "foo", "of"]

Output:

1

Explanation: Here, the strings "foo" and "of" are similar because they are composed of the same characters ['o', 'f']. There are no other similar pairs so the answer is 1.

FC Codelona is trying to assemble a team from a roster of available players. They have a minimum number of players they want to sign, and each player needs to have a skill rating within a certain range. Given a list of players' skill levels with desired upper and lower bounds, determine how many teams can be created from the list. Function Description Complete the function countTeams in the editor. countTeams has the following parameters:

• 1. int[] skills: an array of integers representing the skill levels of players
• 2. int minPlayers: the minimum number of players required to form a team
• 3. int minLevel: the minimum skill level required for a player to be eligible
• 4. int maxLevel: the maximum skill level required for a player to be eligible Returns int: the number of ways to form a team that meets the criteria

An English lecture at HackerElementary School is aimed at teaching students the letters of alphbets. The students are provided with a string word that consists of lowercase English letters. In one move, the can choose any index i, and let the character at the index be c. Then, the first occurrence of c to the left of i, and the first occurence of c to the right of i are deleted (Note: the operation can still be carried out even if either the left or right occurrence does not exist). For example, if word = "adabacaea", and if index 8 is chosen (0-based), the first occurrence of 'a' to the left and right of index 4 (bold, indices 2 and 6) are deleted leaving word = "adbacea". Find the min num of moves the students need to perform in order to get a word of minimal length. Function Description Complete the function getMinMove in the editor below. getMinMove has the following parameter(s): String word: the word given to the students Returns int: the min num of moves needed to get a word of minimal length

Constraints

• 1 ≤ |word| ≤ 10⁵
• The string word consists of lowercase English letters.

HackerRank is organizing a hackathon for all its employees. A hackathon is a team event, and there are n teams taking part. The number of employees in the nth team is denoted by teamSize[n]. In order to maintain uniformity, the team size of at most k teams can be reduced. Find the maximum number of teams of equal size that can be formed if team size is reduced optimally. Function Description Complete the function equalizeTeamSize in the editor below. equalizeTeamSize has the following parameters:

• int teamSize[n]: the number of employees in each team
• int k: the maximum number of teams whose size can be reduced Returns int: the maximum number of equal size teams possible

Constraints

• 1 ≤ n ≤ 2 * 10⁵
• 1 ≤ teamSize[i] ≤ 10⁹
• 0 ≤ k ≤ 10⁹

Example 1

Input:

teamSize = [1, 2, 2, 3, 4]
k = 2

Output:

4

Explanation: The team size of the last 2 teams can be reduced to 2, thus teamSize = [1, 2, 2, 2, 2]. The maximum number of teams with equal size is 4.

Anju teaches Physics and Chemistry for P and C number of hours respectively. After teaching a particular subject for more than N number of hours continuously, Anju gets exhausted and needs to switch to another subject. So the Principal has decided to schedule the time table for Anju in such a way that she does not teach a given subject for more than N number of hours continuously. The principal being weak in maths asks you to find out the maximum number of possible arrangements of hours in which Anju can teach a given subject for no more than N number of hours continuously. Input format

• First line contains T the required number of test cases.
• Next T lines contain Three space-separated integers P, C, and N respectively. Output format For each test case, print the number of arrangements of hours in which Anju has not to teach a given subject for more than N number of hours continuously modulo 10⁹+7. Note: If no arrangement is possible print 0.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ P, C, N ≤ 10³

Example 1

Input:

P = 1
C = 1
N = 2

Output:

2

Explanation: N/A

Example 2

Input:

P = 1
C = 2
N = 1

Output:

1

Explanation: N/A

A bitonic sequence is a sequence of numbers that first increase (non-decreasing) and then decreases (non-increasing). Given an array of integers, find the length of the longest subarray that is bitonic in nature.

Constraints

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

Example 1

Input:

arr = [10, 8, 9, 15, 12, 6, 7]

Output:

5

Explanation: [8,9,15,12,6] is the longest bitonic subarray. Return its length, 5.

Example 2

Input:

arr = [5, 1, 2, 1, 4, 5]

Output:

3

Explanation: [1,2,1]is the longest bitonic subarray. Note that the subarray[1,4,5]is also bitonic in nature and has the same length. It is non-decreasing through[1,4,5]and the non-increasing portion is[5].

Example 3

Input:

arr = [9, 7, 6, 2, 1]

Output:

5

Explanation: The non-decreasing subarray is[9]. The non-increasing subarray is the entire array. The entire array has 5 elements.

There is a list of items in the shopping cart, each having a cost associated with it. There are n items, the cost of the i^th item is i dollars and m items have already been bought represented in the array arr. Currently, there are k dollars, find the maximum number of distinct items one can have in total after purchasing any number of items from that money. Function Description Complete the function findMaxDistinctItems in the editor below. The function must return an integer denoting the maximum count of distinct items that can be purchased. findMaxDistinctItems has the following parameter(s):

• 1. n: an integer denoting the number of items
• 2. arr[n]: an integer array denoting already purchased items
• 3. k: an integer denoting amount in dollars

Constraints

• 1 ≤ n ≤ 10⁶
• 1 ≤ m ≤ 10⁵
• 1 ≤ k ≤ 10⁹
• 1 ≤ a[i] ≤ 10⁶

Example 1

Input:

n = 10
arr = [1, 3, 8]
k = 10

Output:

5

Explanation: Consider n = 10, m = 3, k = 10, arr = [1, 3, 8]. So, the task is to find the maximum number of distinct items which can be purchased out of 10 items with 10 dollars apart from items [1, 3, 8]. At max, 2 items can be purchased apart from the given 3. let's say item 2 and item 5. Total cost = 2 + 5 = 7 which is less than 10. Let us consider three items - Item 2, item 4, and Item 5. Total cost = 2 + 4 + 5 = 11 which is greater than 10. So, it is not possible. So, the answer is 5 (3 already purchased, and 2 purchased just now).

Example 2

Input:

n = 5
arr = [3, 6]
k = 8

Output:

5

Explanation: At max, 3 items can be purchased apart from the given 2, let's say Item - 1, Item - 2, and Item - 4. Total cost = 1 + 2 + 4 = 7 which is less than 8. So, the answer is 5 (2 already purchased, and 3 purchased just now).

The goal is to find the maximum possible even sum of values of tags that can be chosen. Note: It is guaranteed that there is at least one tag with an even value. The tags can have positive or negative values. It can be possible to choose no tags at all.

Example 1

Input:

val = [2, 3, 6, -5, 10, 1, 1]

Output:

22

Explanation: The tags [2, 3, 6, 10, 1] sum to 22 which is even and is the maximum possible. Hence, the answer is 22.

A scheduler manages multiple processes with priorities represented by the letters a, b, and c. Its goal is to optimize the schedule to achieve a specific sequence. The operations available to the scheduler are as follows: Choose a process with priority a, b, or c. Insert the chosen process into the scheduling queue at any position. Determine the minimum number of scheduling operations required to ensure that the scheduling queue follows the repeating pattern "abc". Function Description Complete the function findMinOperations in the editor below. findMinOperations takes the following parameters:

• string s: the scheduling queue Returns int: the minimum number of operations required to make the queue a concatenation of 'abc' several times Constraints
• 1 ≤ |s| ≤ 10⁵
• s consists only of characters 'a', 'b', and 'c'.

In the context of data analysis and machine learning, a dataset containing an array of integers has been provided. Each integer is denoted as arr[i] (0 ≤ i Function Description Complete the function findMissingInteger in the editor below. findMissingInteger takes the following parameter(s):

• int arr[n]: a machine learning dataset
• long k: find the kth smallest positive integer that is not present in the dataset Returns long: the kth smallest positive integer that is not in the dataset

Constraints

• 1 ≤ n ≤ 2 * 10⁵
• 1 ≤ arr[i] ≤ 10⁹
• 1 ≤ k ≤ 10¹²

Example 1

Input:

arr = [1, 4, 7, 3, 4]
k = 5

Output:

9

Explanation: The first five missing positive integers are [2, 5, 6, 8, 9]. The 5th smallest positive integer not in the dataset is 9.

Given a binary number as a string, x (a binary string), return the binary string of the same length, y, that will produce the maximum value when XORed with x. There is a number of bits that may be set in y called maxSet. The binary strings will always have bits digits, and leading zeros are fine. Function Description Complete the function findYValue in the editor below. findYValue has the following parameter(s):

• 1. int bits: the length of the binary strings x and y
• 2. int maxSet: the number of bits that may be set in y
• 3. string x: a binary string Returns string: the best y value as a binary string

Constraints

• 1 ≤ bits ≤ 10⁵
• 0 ≤ maxSet ≤ bits
• len(x) == bits and x contains only '0' and '1'.

Example 1

Input:

bits = 3
maxSet = 1
x = "101"

Output:

"010"

Explanation: First, determine all possible bits = 3 digit binary strings with only maxBits = 1 or fewer bits set: 000, 001, 010, 100. These are the potential y values. Now, XOR each of the y values with x = 101:

• 000 xor 101 = 101
• 001 xor 101 = 100
• 010 xor 101 = 111
• 100 xor 101 = 001 The third value produces the maximal result, where y = 010. Return the string '010'.

Given a string s with uppercase English letters, remove all occurrences of the string AWS until no more remain. After each removal, the prefix and suffix strings are concatenated. Return the final string. If the final string is empty, return "-1" as a string. Function Description Complete the function getFinalString in the editor below. The function getFinalString has the following parameter:

• string s(n): a string of uppercase English characters Returns string: the string after removing all occurrences of "AWS" from the given string or "-1"

Constraints

• 1 ≤ |s| ≤ 10⁵
• The string contains only uppercase English letters.

Example 1

Input:

s = "AWAWSSG"

Output:

"G"

Explanation:

• AWAWSSG → AWSG
• AWSG → G Return the final string, G.

Given n request ids as an array of strings, requests, and an integer k, after all requests are received, find the k most recent requests. Report the answer in order of most recent to least recent. Function Description Complete the function getLatestKRequests in the editor below. getLatestKRequests takes the following arguments:

• str requests[n]: the request ids
• int k: the number of requests to report Returns str[k]: the k most recent requests

Constraints

• 1 ≤ k ≤ n ≤ 10⁵
• 1 ≤ requests[i].length ≤ 20

Example 1

Input:

requests = ["item1", "item2", "item3", "item1", "item3"]
k = 3

Output:

["item3", "item1", "item2"]

Explanation: Starting from the right and moving left, collecting distinct requests, there is "item3" followed by "item1". Skip the second instance of "item3" and find "item2". The answer is ["item3", "item1", "item2"].

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 getMaxOccurrences in the editor below. getMaxOccurrences has the following parameter(s):

• string components: the given string
• int minLength: the minimum length of the substring
• int maxLength: the maximum length of the substring
• int maxUnique: the maximum unique characters of the substring Returns int: the maximum number of occurrences of any substring satisfying the conditions

Constraints

• 2 ≤ n ≤ 10⁵
• 2 ≤ minLength ≤ maxLength ≤ 26
• maxLength < n
• 2 ≤ maxUnique ≤ 26

Example 1

Input:

components = "abcde"
minLength = 2
maxLength = 4
maxUnique = 26

Output:

1

Explanation: The given string is 'abcde'. The combination of components should be greater than or equal to 2, so 'a', 'b', 'c', 'd', and 'e' are discarded. The combination of components should be less than or equal to 4, so 'abcde' is discarded. The combinations of components that satisfy the conditions above are 'ab', 'bc', 'cd', 'de', 'abc', 'bcd', 'cde', 'abcd', 'bcde', and 'abcde'. Each combination of characters occurs only one time, so the number of occurrences is 1.

Example 2

Input:

components = "ababab"
minLength = 2
maxLength = 3
maxUnique = 4

Output:

3

Explanation: The given string is 'ababab'. The combination of characters should be greater than or equal to 2, so a, b, a, b, a, and b are discarded. The combination of characters should be less than or equal to 3, so 'abab', 'baba', 'abab', 'baba', and 'ababa' are discarded. The combinations of components that satisfy the conditions above are 'ab', 'ba', 'ab', 'ba', 'ab', 'aba', 'bab', 'aba', 'bab', and 'bab'. The combination of characters 'ab' occurs 3 times, 'ba' and 'aba' and 'bab' 2 times. So, the maximum frequency of occurrence is 3.

Example 3

Input:

components = "abcde"
minLength = 2
maxLength = 3
maxUnique = 3

Output:

1

Explanation: The given string components is 'abcde' The number of pieces in an interval should be greater than or equal to minLength = 2, so 'a', 'b', 'c', 'd', and 'e' The combination that satisy the conditions above are 'ab', 'bc', 'cd', 'de', 'abc', 'bcd', and 'cde' Each combination of characters occurs only one time, so the max number of occurances is 1.

There is client/server architecture with n clients and one server. Each client starts its interaction with the server at the second start[i] and stops at the second end[i]. The maximum traffic is defined as the maximum number of concurrent interactions with the server. Find the earliest time at which the maximum number of clients are interacting with the server. Note: The endpoint is also included in the interaction. Function Description Complete the function getMaxTrafficTime in the editor below. getMaxTrafficTime has the following parameters:

• int start[n]: interaction start times
• int end[n]: interaction end times Returns int: the earliest time of maximum concurrent interactions

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ start[i] ≤ end[i] ≤

Example 1

Input:

start = [1, 6, 2, 9]
end = [7, 8, 6, 10]

Output:

6

Explanation: The maximum number of concurrent interactions is 3 which happens first at the 6th second. Return 6.

Example 2

Input:

start = [2, 3, 7, 4, 7]
end = [4, 5, 8, 7, 10]

Output:

4

Explanation:

There are n types of items in a shop, where the number of items of type i is denoted by quantity[i]. The price of the items is determined dynamically, where the price of the i^th item is equal to the remaining number of items of type i. There are m customers in line to buy the items from the shop, and each customer will buy exactly one item of any type. The shopkeeper, being greedy, tries to sell the items in a way that maximises revenue. Find the maximum amount the shopkeeper can earn by selling exactly m items to the customers optimally. Function Description Complete the function getMaximumAmount in the editor. getMaximumAmount has the following parameter:

• int quantity[n]: the number of items of each type Returns long integer: the maximum revenue possible

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ m ≤ 10⁵
• 1 ≤ quantity[i] ≤ 10⁵

Example 1

Input:

quantity = [10, 10, 8, 9, 1]
m = 6

Output:

55

Explanation: N/A for now

Example 2

Input:

quantity = [1, 2, 4]
m = 4

Output:

11

Explanation:

Process scheduling algorithms are used by a CPU to optimally schedule the running processes. A core can execute one process at a time, but a CPU may have multiple cores. There are n processes where the i^th process starts its execution at start[i] and ends at end[i], both inclusive. Find the minimum number of cores required to execute the processes. Function Description Complete the function getMinCores in the editor below. getMinCores takes the following arguments:

• int start[n]: the start times of processes
• int end[n]: the end times of processes Returns int: the minimum number of cores required

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ start[i] ≤ end[i] ≤ 10⁹

Example 1

Input:

start = [1, 3, 4]
end = [3, 5, 6]

Output:

2

Explanation: If the CPU has only one core, the first process starts at 1 and ends at 3. The second process starts at 3. Since both processes need a processor at 3, they overlap. There must be more than 1 core. If the CPU has two cores, the first process runs on the first core from 1 to 3, the second runs on the second core from 3 to 5, and the third process runs on the first core from 4 to 6. Return 2, the minimum number of cores required.

Implement a function that returns the minimum number of operations needed to ensure the string s (of length n) contains no segments of exactly m consecutive '0's. In one operation, you can do the following:

• Select a contiguous segment of length k and make every bit in this segment '1'. The function getMinOperations will take three inputs:
• string s: a string representing s.
• int m: an integer representing m.
• int k: an integer representing k. The function should return an integer representing the minimum number of operations needed.

Constraints

• 1 ≤ n ≤ 2 * 10⁵
• 1 ≤ m, k ≤ n

Example 1

Input:

s = "000000"
m = 3
k = 2

Output:

1

Explanation: We can perform an operation on the interval [3, 4] (1-based indexing) to get "001100", ensuring no segment of consecutive 0s has a length ≥ 3. Thus, the answer is 1.

A Domain Name System (DNS) translates domain names to IP addresses which are then used by browsers to load internet resources. For quicker DNS lookups, browsers store a number of recent DNS queries in a DNS cache. Retrieving data from the cache is often faster than retrieving it from a DNS server. This task aims to simulate DNS resolution and determine the time taken to process different URLs. Assume that each DNS cache can store a maximum of the cache_size most recent DNS requests, i.e., URL-IP mappings. The cache is initially empty. It takes cache_time units of time to fetch data from the DNS cache, and server_time units of time to fetch data from the DNS server. Given a list of URLs visited as an array of strings, urls, determine the minimum time taken to resolve each DNS request. Note: New DNS requests are dynamically added to the cache, and the cache stores mappings according to the order in which the requests were made. Function Description Complete the function getMinTime in the editor. getMinTime has the following parameters(s):

• int cache_size: the size of the DNS cache
• int cache_time: the time taken to fetch data from the cache
• int server _time: the time taken to resolve an address using the DNS server
• String urls[n]: the URLs visited by a user Returns int[n]: the minimum time to resolve each DNS request

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ cache_size ≤ 10⁵
• 1 ≤ cache_time, server_time ≤ 10⁹
• 1 ≤ size of urls[i] ≤ 20

Example 1

Input:

cache_size = 2
cache_time = 2
server_time = 3
urls = ["www.google.com", "www.yahoo.com", "www.google.com", "www.yahoo.com", "www.coursera.com"]

Output:

[3, 3, 2, 2, 3]

Explanation: :)

Example 2

Input:

cache_size = 3
cache_time = 2
server_time = 5
urls = ["http://www.hackerrank.com", "http://www.google.com", "http://www.gmail.com", "http://www.yahoo.com", "http://www.hackerrank.com","http://www.gmail.com"]

Output:

[5, 5, 5, 5, 5, 2]

Explanation: :P

In an edge computing environment, required hardware includes edge devices, input peripherals, and bundles that encompass both types. Each resource comes at a cost, with edge devices priced at edgeDeviceCost, peripherals at inputPeripheralCost, and bundles at bundleCost. The challenge is to optimize the procurement of resources. The objective is to ensure the provision of the right quantities of edge devices and peripherals, allowing for a degree of flexibility, and accommodating extra equipment. This flexibility is provided to meet the requirements of the environment, which necessitates x edge devices and y peripherals. The primary goal is to minimize costs while simultaneously guaranteeing that the edge computing environment is equipped with all the essential resources. Compute and return the total expenditure. Function Description Complete the function getMinimumCost in the editor. getMinimumCost has the following parameter(s):

• int edgeDeviceCost: the cost of an edge device
• int inputPeripheralCost: the cost of an input peripheral
• int bundleCost: the cost of a bundle containing both, an edge device and an input peripheral
• int x: the number of edge devices required
• int y: the number of input peripherals required Returns long: the minimum expenditure necessary to ensure that the edge computing environment fully equipped Constraints
• 1 ≤ edgeDeviceCost, inputPeripheralCost, bundleCost, x, y ≤ 10⁹

Example 1

Input:

edgeDeviceCost = 3
inputPeripheralCost = 2
bundleCost = 1
x = 4
y = 3

Output:

4

Explanation: The optimal strategy is to buy 4 bundles for 4 units of money. This provides the environment with 4 edge devices (x ≤ 4) and 4 peripherals (y ≤ 4).

Example 2

Input:

edgeDeviceCost = 1
inputPeripheralCost = 20
bundleCost = 5
x = 9
y = 1

Output:

13

Explanation: The optimal strategy is to get 8 edge devices and 1 bundle containing both, resulting in a total cost of 13 units. The environment will have 9 edge devices and 1 peripheral.

Example 3

Input:

edgeDeviceCost = 1
inputPeripheralCost = 2
bundleCost = 2
x = 2
y = 1

Output:

3

Explanation: The most cost-efficient strategy is to purchase 1 edge device and 1 bundle pack with a total of 1 + 2 = 3 units. Any other approach results in a higher cost. The min total expenditure is 3 units.

An anagram is a word whose characters can be rearranged to create another word. Given two strings, determine the minimum number of characters in either string that must be modified to make the two strings anagrams. If it is not possible to make the two strings anagrams, return -1. Function Description Complete the function getMinimumDifference in the editor. getMinimumDifference has the following parameter(s):

• String[] a: an array of strings
• String[] b: an array of strings Returns int[]: the minimum number of characters in either string that needs to be modified to make the two strings anagrams or -1 if it is not possible

Constraints

• Each string consists of lowercase characters [a-z]
• 1 ≤ n ≤ 100
• 0 ≤ |a[i]|, |b[i]| ≤ 10⁴
• 1 ≤ |a[i]| + |b[i]| ≤ 10⁴

Example 1

Input:

a = ["tea", "tea", "act"]
b = ["ate", "toe", "acts"]

Output:

[0, 1, -1]

Explanation: Perform the following calculations:

• a[0] = tea and b[0] = ate are anagrams, so 0 characters need to be modified.
• a[1] = tea and b[1] = toe are not anagrams. Modify 1 character in either string (o → a or a → o) to make them anagrams.
• a[2] = act and b[2] = acts are not anagrams and cannot be converted to anagrams because they contain different numbers of characters. The return array is [0, 1, -1].

Example 2

Input:

a = ["a", "jk", "abb", "mn", "abc"]
b = ["bb", "kj", "bbc", "op", "def"]

Output:

[-1, 0, 1, 2, 3]

Explanation: Perform the following n = 5 calculations:

• Index 0: a and bb cannot be anagrams because they contain different numbers of characters.
• Index 1: jk and kj are already anagrams because they both contain the same characters at the same frequencies.
• Index 2: abb and bbc differ by one character.
• Index 3: mn and op differ by two characters.
• Index 4: abc and def differ by three characters. After checking each pair of strings, return the array [-1, 0, 1, 2, 3] as the answer.

Given an integer array arr of length n, you can perform the following operation on the array at most once: Choose a subset of elements from the array such that no two selected elements are adjacent (i.e., no two selected elements are next to each other in the array). Choose a non-negative integer x, and increase all the selected elements by x. Determine the minimum non-negative integer x, required to make the array arr non-decreasing using at most one operation. If it is impossible, return -1. Function Description Complete the function getMinimumIncrement in the editor with the following parameter(s):

• int arr[n]: the array Returns int: the minimum value of increment so that the array becomes non-decreasing

Example 1

Input:

arr = [1, 1, 3, 2]

Output:

1

Explanation: Some of the possible ways are:

• Select the element with index 3 (0-based indexing) and increment = 1 to get the array arr = [1, 1, 3, 3].
• Select the elements with indices [1, 3] (0-based indexing) and increment = 2 to get the array arr = [1, 3, 3, 4]. Hence, the minimum value of increment is 1.

A shopkeeper sells n items where the price of the jth item is price[j]. To maintain balance, the shopkeeper wishes to adjust the price of items such that the median of prices is exactly k. In one move, the shopkeeper can increase or decrease the price of any item by 1, and the shopkeeper can perform this move any number of times. Find the minimum number of moves in which the median of prices becomes exactly k. Note: The index of the median of an array of m sorted elements, where m is odd, is (m+1)/2. For example, [2, 5, 4, 1, 1, 1, 6] sorted is [1, 1, 1, 2, 4, 5, 6]. Its length is 7 so the median is at index (7 + 1)/2 = 4 using 1-based indexing. The median is 2. Function Description Complete the function getMinimumMoves in the editor. getMinimumMoves has the following parameters:

• int price[n]: the prices of items
• int k: the required median Returns long integer: the minimum number of moves to make the median of the array exactly k

Example 1

Input:

price = [4, 2, 1, 4, 7]
k = 3

Output:

1

Explanation: Decrease price[0] by 1, the resulting array is [3, 2, 1, 4, 7]; on sorting, this becomes [1, 2, 3, 4, 7] whose median equals k = 3. Thus, in one move, the median becomes 3 and the answer is 1.

A string is "beautiful" if no two adjacent characters are either

1. the same (e.g. "aa"), or
2. adjacent in the alphabet (e.g. "ef", "ba").

In one operation you may choose any index i and replace s[i] with any lowercase letter. Return the minimum number of operations needed to make s beautiful.

Constraints

• 2 ≤ |s| ≤ 10⁵
• The string s contains only lowercase English letters.

Example 1

Input:

s = "abdde"

Output:

2

Explanation: String s is not beautiful because:

• 'dd' violates constraint 1, no two adjacent characters are the same.
• 'ab' and 'de' violate constraint 2, no two adjacent characters are adjacent in the alphabet. The string can be converted into a beautiful string after 2 operations. One solution is below:
• Choose i=1 and change s[i] to 'z', s becomes "azdde".
• Choose i=3 and change s[i] to 'k', s becomes "azdke" which is beautiful. Note: There are many other solutions such as "ardze", "axdke", etc. It can be shown that 2 is the minimum number of operations required so return 2.

A string is to be constructed using only the characters 'A' and 'B'. Given four integers, countA, countB, maxA, maxB, the constructed string is said to be optimal if: There are at most countA 'A' characters, and countB 'B' characters. Each substring of only 'A's contains at most maxA 'A' characters. Each substring of only 'B's contains at most maxB 'B' characters. HackerRank organized fun trivia for its employees where it asked for the maximum possible length of an optimal string that can be constructed satisfying the criteria above. The goal is to find the maximum possible length of an optimal string. Note:

• There can be multiple optimal strings with the same maximal length.
• A substring of a string is a contiguous subsegment of the string. Function Description Complete the function getOptimalStringLength in the editor. getOptimalStringLength has the following parameters:
• int countA: the maximum count of character 'A'
• int countB: the maximum count of character 'B'
• int maxA: the maximum substring length of character 'A'
• int maxB: the maximum substring length of character 'B' Returns long integer: the maximum length of optimal string that can be constructed

Constraints

0 ≤ countA, countB, maxA, maxB ≤ 10⁶

The city of Hackerland organized a chess tournament for its citizens. There are n participants numbered 1 to n where i^th participant has potential denoted by potential[i]. The potential of each player is distinct. Initially, all players stand in a queue in order from the 1^st to the n^th player. In each game, the first 2 participants of the queue compete and the participant with a higher potential wins the game. After each game, the winner remains at the beginning of the queue and plays with the next person from the queue and the losing player goes to the end of the queue. The game continues until a player wins k consecutive games. Given the potential of the participants and the deciding factor k, find the potential of the winning player. Function Description Complete the function getPotentialOfWinner in the editor. getPotentialOfWinner has the following parameters:

• int potential[n]: the potentials of participants
• long int k: the number of consecutive matches the winning participant must win Returns int: the potential of the winning player

Constraints

• 2 ≤ n ≤ 10⁵
• 1 ≤ potential[i] ≤ n
• 2 ≤ k ≤ 10¹⁴

Example 1

Input:

potential = [3, 2, 1, 4]
k = 2

Output:

3

Explanation:

• Initial position of participants: [1, 2, 3, 4].
• Participants 1 and 2 compete. Their potentials are 3 and 2. Player 1 wins due to the higher potential. Player 1 stays at the front of the queue and player 2 moves to the back. Now their positions are [1, 3, 4, 2].
• Participants 1 and 3 compete. Their potentials are 3 and 1. 1 wins a second consecutive game. Since k = 2, player 1 has won enough consecutive games. Return player 1's potential, 3.

Example 2

Input:

potential = [1, 3, 2, 4, 5]
k = 2

Output:

3

Explanation:

• Initial position of participants: [1, 2, 3, 4, 5].
• potential[1] = 3, potential[2] = 2 player 2 wins. The positions of participants after match 1: [2, 3, 4, 5, 1].
• potential[2] = 3, potential[3] = 1, player 2 wins. Since k = 2, player 2 is the winner.

Example 3

Input:

potential = [3, 2, 1, 4]
k = 3

Output:

4

Explanation: Positions Potentials Consecutive 1st in line 2nd in line Winner wins

[1, 2, 3, 4] 3 2 1 [1, 3, 4, 2] 3 1 2 [1, 4, 2, 3] 3 4 1 [4, 1, 2, 3] 4 3 2 [4, 2, 3, 1] 4 2 3 player 4 is the winner.

Implement a prototype of a simple cache query handler. There are n entries stored in the cache. Each entry is of the form {timestamp, key, value}, where time stamp represents the time at which the entry was stored in the cache entry, and value represents the data value of the entry, an integer represented as string. The keys assigned to the cache entries may not be unique. The cache query handler receives q query requests, where each query is of the form {key, timestamp}, where key represents the ID of the query entry to find, and timestamp represents the time the enry was added. Given 2 2d arr of strings, cache_entries, and queries, of sizes n X 3 and q X 2 respectively, return an arr of size q with the data values for each query. Function Description Complete the function getQueryAnswers in the editor. getQueryAnswers has the following parameters:

• string cache_entries[n][3]: the cache data entries
• string queries[q][2]: the queries Returns int[q]: the answers to the queries

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 10⁵
• 1 ≤ int(cache_entries[i][2]) ≤ 10⁸
• cache_entries[i][0] represents a valid timestamp in the format hh:mm:ss
• size(cache_entries[i][0]) = 8
• cache_entries[i][1] is an alphanumeric value, consisting of only lowercase English letters (a-z) and digits (0-9)
• It is guaranteed that the queried {key, timestamp} pair is present in the cache.
• At a particular timestamp, there can be no duplicate keys.

Example 1

Input:

cache_entries = [["01:34:05", "l66klkph", "352"], ["56:38:37", "8pvj20oo", "107"], ["36:17:33", "r0v06eec", "180"], ["20:34:20", "e15y6dv4", "490"]]
queries = [["e15y6dv4", "20:34:20"], ["8pvj20oo", "56:38:37"]]

Output:

[490, 107]

Explanation: :)

Example 2

Input:

cache_entries = [["12:30:22", "a2er5i80", "125"], ["09:07:47", "ioO9ju56", "341"], ["01:23:09", "a2er5i8O", "764"], ]
queries = [["a2er5i8O", "01:23:09"], ["ioO9ju56", "09:07:47"]]

Output:

[764, 341]

Explanation: queries[0] corresponds to the data entry at index 2, with value = "764" queries[1] corresponds to the data entry at index 1, with value = "341" Return [764, 341] :)

Given a string s that consists of lowercase English letters, select exactly one non-empty substring of s and replace each character of it with the previous character of the English alphabet. For example 'b' is converted to 'a', 'c' is converted to 'b'; ..., and 'a' is converted to 'z'. Find the lexicographically smallest string that can be obtained after performing the above operation exactly once. Function Description Complete the function getSmallestString in the editor below. getSmallestString has the following parameter:

• s: string - a string Returns string: the lexicographically smallest string possible

Constraints

1 ≤ length of s, |s| ≤ 10⁵

Example 1

Input:

s = "hackerrank"

Output:

"gackerrank"

Explanation: Select and change only the first character. Return "gackerrank", the lexicographically smallest string possible.

Example 2

Input:

s = "bbcad"

Output:

"aabad"

Explanation: Change bbc to aab.

When multiple tasks are executed on a single-threaded CPU, the tasks are scheduled based on the principle of pre-emption. When a higher-priority task arrives in the execution queue, then the lower-priority task is pre-empted, i.e. its execution is paused until the higher-priority task is complete. There are n functions to be executed on a single-threaded CPU, with each function having a unique ID between 0 and n - 1. Given an integer n representing the number of functions to be executed, and an execution log, as an array of strings, logs, of size m, determine the exclusive times of each of the functions. Exclusive time is the sum of execution times for all calls to a function. Any string representing an execution log is of the form {function_id}:{start/end}:{timestamp}, indicating that the function with ID = function_id, either starts or ends at a time identified by the timestamp value. Note: While calculating the execution time of a function call, both the starting and ending times of the function call have to be included. The log of the form {function_id}:{start}:{timestamp} means that the running function is preempted at the beginning of timestamp timestamp. The log of the form {function_id}:{end}:{timestamp} means that the function function_id is preempted after completing its execution at timestamp second i.e. after timestamp second. Function Description Complete the function getTotalExecutionTime in the editor below. getTotalExecutionTime has the following parameters:

• 1. int n: the number of functions to be executed
• 2. string logs[m]: the execution logs of the different calls to the functions Returns int[n]: the execution time of all functions with IDs from 0 to n - 1.

Constraints

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 500
• 0 ≤ function_id < n
• 0 ≤ timestamp ≤ 10³
• The timestamps are given in non-decreasing order.
• No two starting timestamps and no two ending timestamps are equal.
• Every function "start" call has a corresponding function "end" call.

Example 1

Input:

n = 2
logs = ["0:start:0", "1:start:3", "1:end:6", "0:end:10"]

Output:

[7, 4]

Explanation: The execution of functions happens in the following order:

• Time = [0, 3]: Function ID = 0 executes
• Time = [3, 6]: Function ID = 1 executes
• Time = [6, 10]: Function ID = 0 executes Thus the exclusive times for different functions are as follows:
• Function (ID = 0) = 3 + 4 = 7
• Function (ID = 1) = 3 = 4

Example 2

Input:

n = 3
logs = ["0:start:0", "1:start:3", "1:end:6", "2:start:8", "2:end:10", "0:end:12"]

Output:

[6, 4, 3]

Explanation: The execution of functions happens in the following order:

• Time = [0, 3]: Function ID = 0 executes
• Time = [3, 6]: Function ID = 1 executes
• Time = [6, 8]: Function ID = 0 executes
• Time = [8, 10]: Function ID = 2 executes
• Time = [11, 12]: Function ID = 0 executes Thus the exclusive times for different functions are as follows:
• Function (ID = 0) = 3 + 1 + 2 = 6
• Function (ID = 1) = 4 = 4
• Function (ID = 2) = 3 So the answer to be returned is [6, 4, 3].

Given a dataset of strings containing only parentheses, characters '(' and ')', the data represented by the string is valid if it is a balanced bracket sequence. One adjustment to the string can be made: at most one bracket can be moved from its original place to any other position in the string. The task is to determine whether, for each string, it is possible to balanced the bracket sequence in 1 move or less. Return an array of the size of the dataset, where the j^th integer is 1 if the string can be converted into a balanced string, and 0 otherwise. Note: A string s is a balanced bracket sequence if: s is empty. s is equal to "(t)", where t is a balanced bracket sequence. s is equal to t_1t_2, i.e. concatenation of t_1 and t_2 where t_1 and t_2 are balanced bracket sequences. Function Description Complete the function isConvertibleData in the editor. isConvertibleData takes the following parameter(s):

• String[] dataset: the dataset where each string contains characters ')' and '(' Returns int[]: an array of integers, where the j^th integer is 1 if the corresponding string can be transformed into a balanced bracket sequence and 0 otherwise

Constraints

• 1 ≤ n ≤ 2 * 10⁵
• 1 ≤ |dataset[i]| ≤ 2 * 10⁵
• n ≤ Σ|dataset[i]| ≤ 2 * 10⁵
• It is guaranteed that each string dataset[i] consists of characters '(' and ')' only

There is an infinite array of integers numbered consecutively from 0. At each step, a pointer can move from index i to index i + j, or remain where it is. The value of i begins at 0. The value of j begins at 1 and at each step, j increments by 1. There is one known index that must be avoided. Determine the highest index that can be reached in a given number of steps. Function Description Complete the function maxIndex in the editor. maxIndex has the following parameter(s):

• 1. int steps: the number steps to take
• 2. int badIndex: the bad index Returns int: the maximum index that can be reached from index 0

Constraints

• 1 ≤ steps ≤ 2 × 10³
• 0 ≤ badIndex ≤ steps × (steps + 1) / 2

Example 1

Input:

steps = 4
badIndex = 6

Output:

9

Explanation: The pointer is limited to 4 steps and should avoid the bad item 6.

• Scenario 1:
• In the first step, j starts at 1. Move 1 unit to index 0 + 1 = 1 and j = 2.
• At step 2, move 2 units to index 1 + 2 = 3, and j = 3.
• At step 3, do not move. Otherwise, the pointer will move 3 units to the bad item 6. Now j = 4.
• At step 4, move 4 units to item 3 + 4 = 7.
• Scenario 2:
• At step 1, remain at index 0. Now j = 2.
• At step 2, move 2 units to index 0+2 = 2 and j = 3.
• At step 3, move 3 units to index 2+3 = 5 and j = 4.
• At step 4, move 4 units to index 5 + 4 = 9.
• The maximum index that can be reached is 9.

Find the maximum profit that can be generated for the given amount of money. As the answer can be rather large, report the answer as maxProfit % (10 ^ 9 + 7) where % denotes modulo operator. Function Description Complete the function maxProfit in the editor. maxProfit has the following parameters: int[] cost: an array of integers representing the cost of each item int x: the initial amount of money Walker has Returns int: the maximum profit that can be obtained modulo (10⁹+7)

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ cost[i] ≤ 10⁵
• 0 ≤ x ≤ 10⁹

Example 1

Input:

cost = [3, 4, 1]
x = 8

Output:

7

Explanation: :)

Example 2

Input:

cost = [19, 78, 27, 15, 20, 25]
x = 25

Output:

16

Explanation: :)

Example 3

Input:

cost = [10, 20, 14, 40, 50]
x = 70

Output:

20

Explanation: Some possible combination of items Walker can buy are: She can buy items 0, 1, and 2 for a cost of 44 and obtain a profit of 2 ^ 0 + 2 ^ 1 + 2 ^ 2 = 7 She can buy items 0 and 4 for a cost of 60 and obtain a profit of 2 ^ 0 + 2 ^ 4 = 17 She can buy items 1 and 4 for a cost of 70 and obtain a profit of 2 ^ 1 + 2 ^ 4 = 18 She can buy items 2 and 4 for a cost of 64 and obtain a profit of 2 ^ 2 + 2 ^ 4 = 20 Out of all the possible combinations, the maximum profit obtained is by buying items 2 and 4 for a cost of 64 to obtain a profit of 20.

A student is taking a test on n different subjects. For each n^th subject they have already answered answered[i] questions and have time to answer a total of q more questions overall. For each n^th subject, the number of questions answered has to be at least needed[i] in order to pass. Determine the maximum number of subjects the student can pass if the additional answered questions are optimally distributed among the subjects. For example, there are n = 2 subjects and needed = [4, 5] answered questions, respectively, to pass. The student has answered answered = [2, 4] questions in the two subjects so far, and can answer another q = 2 questions in all subjects combined. The best outcome is to answer an additional question in the second subject to pass it, and it is not possible to pass the first subject. The maximum number of subjects that can be passed is 1. Function Description Complete the function maxSubjectsNumber in the editor below. The function must return an integer that represents the maximum number of subjects that can be passed. maxSubjectsNumber has the following parameter(s):

• answered[answered[0],...answered[n-1]]: an array of integers
• needed[needed[0],...needed[n-1]]: an array of integers
• q: an integer

Constraints

• 1 ≤ n ≤ 10⁵
• 0 ≤ answered[i], needed[i] ≤ 10⁹

Example 1

Input:

answered = [24, 27, 0]
needed = [51, 52, 100]
q = 100

Output:

2

Explanation: Here answered = [2, 4, 0] and needed = [5, 7, 100]. The additional answers needed to pass are [3, 3, 100]. The best distribution is at least 7 - 2 = 5 questions among the first two subjects. It would take all 100 questions to pass the third subject.

Example 2

Input:

answered = [24, 27, 0]
needed = [51, 52, 100]
q = 200

Output:

3

Explanation: :)

Example 3

Input:

answered = [2, 4]
needed = [4, 5]
q = 1

Output:

1

Explanation: There are n = 2 subjects and needed = [4, 5] answered questions, respectively, to pass. The student has answered answered = [2, 4] questions in the two subjects so far, and can answer another q = 1 questions in all subjects combined. The best outcome is to answer an additional question in the second subject to pass it, and it is not possible to pass the first subject. The maximum num of subjects that can be passed is 1 :)

Given three positive integers lo, hi, and k, choose two integers a and b with lo ≤ a ≤ b ≤ hi such that a XOR b ≤ k. Return the maximum value of a XOR b achievable under that constraint.

Constraints

• 1 ≤ lo ≤ hi ≤ 10⁴
• 1 ≤ k ≤ 10⁴

Example 1

Input:

lo = 3
hi = 5
k = 6

Output:

6

Explanation: The maximal useable XORed value is 6 because it is the maximal value that is less than or equal to the limit k = 6.

Given a set of n distinct points on the x-axis, choose k of them such that the minimum distance between any two chosen points is as large as possible. Find this maximum possible minimum distance. Function Description Complete the function maximizeMinimumDistance in the editor below. maximizeMinimumDistance has the following parameters:

• int x[n]: the x-coordinates of points
• int k the number of points to choose Returns int: the maximum possible minimum distance between any 2 of the chosen points

Constraints

• 2 ≤ n ≤ 10⁵
• 0 ≤ x[i] ≤ 10⁹
• 2 ≤ k ≤ n
• All points are at distinct x-coordinates.

Example 1

Input:

x = [1, 4, 2, 9, 8]
k = 3

Output:

3

Explanation: In the optimal solution, one of the possible selection of points is {1, 4, 8}. Here,

• The distance between 1 and 4 = abs(1 - 4) = 3
• The distance between 1 and 8 = abs(1 - 8) = 7
• The distance between 4 and 8 = abs(4 - 8) = 4 The minimum amongst them is 3, which is the maximum possible.

An array of size n represents a set of available resources. Identify a subarray that optimally utilizes these resources under the following constraints: The subarray must have a specific length, denoted as k. All elements in the subarray must be unique, representing distinct resource allocations. The ultimate goal is to find the subarray that maximizes the sum of the allocated resources. Return the sum for that subarray. If it is not possible to allocate resources per the constraints, return -1. Note: A subarray is a contiguous segment of an array.

Example 1

Input:

arr = [1, 2, 3, 7, 3, 5]
k = 3

Output:

15

Explanation: Following are the subarrays of length k = 3 and all elements are distinct:

• [1, 2, 3], and 1 + 2 + 3 = 6
• [2, 3, 7], sum = 12
• [7, 3, 5], sum = 15 Return the maximum sum, 15.

When evaluating a machine learning model, n test cases are provided. Each is associated with an arrivalTime[i] indicating the times each test case was given. The testing environment is activated once for some time, then enters an inactive state. If activated at time t1 and deactivated at time t2, tests with arrival times between t1 and t2 (inclusive) are executed. The total time the system was active is t2 - t1. Efficiency of testing system = number of test cases tested / total time the system was active Determine the maximum efficiency when the testing environment selects optimum activation and deactivation times. The active environment must execute at least two test cases during its active period. Return the maximum possible efficiency. Notes:

• Execution time for test cases is practically instantaneous; that is, it takes almost no time.
• If two test cases share the same arrival time, they are evaluated simultaneously.
• Efficiency may take negative values.

Constraints

• 2 ≤ n ≤ 2 × 10⁵
• 1 ≤ arrivalTime[i] ≤ 10⁹

An array of integers is defined as being in meandering order when the first two elements are the respective largest and smallest elements in the array and the subsequent elements alternate between its next largest and next smallest elements. In other words, the elements are in order of [first_largest, first_smallest, second_largest, second_smallest, ...]. Function Description Complete the function meanderingArray in the editor below. meanderingArray has the following parameters:

• int unsorted[n]: the unsorted array Returns int[n]: the array sorted in meandering order

Constraints

• 2≤n≤10⁵
• -10⁶ ≤ unsorted[i] ≤ 10⁶
• The unsorted array may contain duplicate elements.

Example 1

Input:

unsorted = [-1, 1, 2, 3, -5]

Output:

[3, -5, 2, -1, 1]

Explanation: The array [-1, 1, 2, 3, -5] sorted normally is [-5, -1, 1, 2, 3]. Sorted in meandering order, it becomes [3, -5, 2, -1, 1].

Given two sorted arrays, merge them to form a single, sorted array with all items in non-decreasing order. Function Description Complete the function mergeArrays in the editor below. mergeArrays has the following parameter(s):

• int a[n]: a sorted array of integers
• int b[n]: a sorted array of integers Returns int[n]: an array of all the elements from both input arrays in non-decreasing order

Constraints

• 1 < n ≤ 10⁵
• 0 ≤ a[i], b[i] ≤ 10⁹ where 0 ≤ i < n

Example 1

Input:

a = [1, 2, 3]
b = [2, 5, 5]

Output:

[1, 2, 2, 3, 5, 5]

Explanation: Merge the arrays to create array c as follows: a[0] c = [a[0]] = [1] a[1] c = [a[0], b[0]] = [1, 2] a[1] c = [a[0], b[0], a[1]] = [1, 2, 2] a[2] c = [a[0], b[0], a[1], a[2]] = [1, 2, 2, 3] No more elements in a → c = [a[0], b[0], a[1], a[2], b[1], b[2]] = [1, 2, 2, 3, 5, 5] Elements were alternately taken from the arrays in the order given, maintaining precedence.

In this challenge, determine the minimum number of chairs to be purchased to accommodate all workers in a new business workroom. There is no chair at the beginning. There will be a string array of simulations. Each simulation is described by a combination of four characters: C, R, U, and L

• C - A new employee arrives in the workroom. If there is a chair available, the employee takes it. Otherwise, a new one is purchased.
• R - An employee goes to a meeting room, freeing up a chair.
• U - An employee arrives from a meeting room. If there is a chair available, the employee takes it. Otherwise, a new one is purchased.
• L - An employee leaves the workroom, freeing up a chair. Function Description Complete the minChair function. minChair has the following parameter(s):
• string simulation[n]: an array of strings representing discrete simulations to process. Return int[n]: an array of integers denoting the minimal number of chairs required for each simulation.

Constraints

• 1 ≤ n ≤ 100
• 1 ≤ length of each simulation[i] ≤ 10000

Given an array measurements of distinct integers, find the minimum absolute difference between any two values. Return all pairs [a, b] with a < b and b - a equal to that minimum, sorted ascending by a, then by b.

(The original problem prints these pairs; we return them as a 2D integer array.)

Constraints

• 2 ≤ n ≤ 10⁵
• -10⁹ ≤ measurements[i] ≤ 10⁹
• Values are distinct.

Example 1

Input:

measurements = [-1, 3, 6, -5, 0]

Output:

[[0,3],[3, 6]]

Explanation: After sorting the measurements: [-5, -1, 0, 3, 6]. The minimum adjacent gap is 3, achieved by (0, 3) and (3, 6). Pairs are returned sorted by first element, then second.

Example 2

Input:

measurements = [6, 5, 4, 3, 7]

Output:

[[3, 4],[4, 5],[5, 6],[6, 7]]

Explanation: The minimum absolute difference is 1, and the pairs with that difference are (3,4), (4,5), (5,6), and (6,7).

Example 3

Input:

measurements = [1, 3, 5, 10]

Output:

[[1, 3], [3, 5]]

Explanation: The minimum absolute difference between any two elements in the array is 2, and there are two such pairs: (1, 3) and (3, 5).

Given a string, find the minimum number of non-empty disjoint segments a string can be partitioned into, such that each segment has no repeated characters. Choose the partitioning that yields the fewest such segments among all possible ways to partition the string. Note: Each character of the string should be in exactly one segment.

Constraints

• 1 ≤ |s| ≤ 2 * 10⁵
• It is guaranteed that the string s consists only of lowercase English letters.

Example 1

Input:

s = "bcoc"

Output:

2

Explanation: Possible partitions of the string:

• "b", "c", "o", "c" → 4 segments
• "boc", "c" → 2 segments
• "bc", "o", "c" → 3 segments

The fewest number of segments is 2.

Example 2

Input:

s = "abdaa"

Output:

3

Explanation: It can be concluded that the partition "abd", "a", and "a" is the optimal partitioning of s into non-empty disjoint segments, each having no repeating characters.

Example 3

Input:

s = "abcdefghijklmnopqrstuvwxyz"

Output:

1

Explanation: Observed in test results panel: input "abcdefghijklmnopqrstuvwxyz" gives output 1.

Given a string that consists of left and right parentheses, '(' and ')', balance the parentheses by inserting parentheses as necessary. Determine the minimum number of characters that must be inserted. Function Description Complete the function minInsertionsToBalance in the editor. minInsertionsToBalance has the following parameter:

• String s: the initial parentheses sequence Returns int: the minimum number of insertions

Constraints

• 1 ≤ length of s ≤ 10⁵

Example 1

Input:

s = "()))"

Output:

2

Explanation: N/A

Example 2

Input:

s = "(()))"

Output:

4

Explanation: Insert 1 left parenthesis at the left end of the string to get '((()))'. The string is balanced after 1 insertion. s = '))((' Insert 2 left parentheses at the start and 2 right parentheses at the end of the string to get "(())(())" after 4 insertions.

There are two arrays of integers, arr1 and arr2. One move is defined as an increment or decrement of one element in an array. Determine the minimum number of moves to match arr1 with arr2. No reordering of the digits is allowed. Function Description Complete the function minimumMoves in the editor below. minimumMoves has the following parameter(s):

• int arr1[n]: array to modify
• int arr2[n]: array to match Returns int: the minimum number of moves to match arr1 with arr2

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ arr1[i], arr2[i] ≤ 10⁹
• The lengths of arr1 and arr2 are equal, |arr1| = |arr2|.
• The elements arr1[i] and arr2[i] have an equal number of digits.

Example 1

Input:

arr1 = [1234, 4321]
arr2 = [2345, 3214]

Output:

10

Explanation:

• Match arr1[0]=1234 with arr2[0]=2345.
• Increment 1 once to get 2 (1 move)
• Increment 2 once to get 3 (1 move)
• Increment 3 once to get 4 (1 move)
• Increment 4 once to get 5 (1 move). 4 moves are needed to match 1234 with 2345.
• Match arr1[1]=4321 with arr2[1]=3214.
• Decrement 4 once to get 3 (1 move)
• Decrement 3 once to get 2 (1 move)
• Decrement 2 once to get 1 (1 move)
• Increment 1 three times to get 4 (3 moves) 6 moves are needed to match 4321 with 3214.
• 6+4=10 total moves are needed to match the arrays arr1 and arr2.

Example 2

Input:

arr1 = [1248]
arr2 = [8642]

Output:

16

Explanation:

• Match arr1[0]=1248 with arr2[0]=8642.
• Decrement 1 seven times to get 8 (7 moves)
• Increment 2 four times to get 6 (4 moves)
• Decrement 4 two times to get 2 (2 moves)
• Increment 8 two times to get 4 (2 moves) 15 moves are needed to match 1248 with 8642.
• 15 total moves are needed to match the arrays arr1 and arr2.

A shop contains n items where the price of item j is price[j]. In one operation, the price of any one item can be increased or decreased by 1. For each query query[i], return the minimum number of operations required to make every price equal to query[i]. Return the answers as an array of length q.

Constraints

• 1 ≤ n, q ≤ 10⁵
• 1 ≤ price[j], query[i] ≤ 10⁹

You are given an array nums consisting of positive integers. You are also given an integer array queries of size m. For the ith query, you want to make all of the elements of nums equal to queries[i]. You can perform the following operation on the array any number of times:

• Increase or decrease an element of the array by 1. Return an array answer of size m where answer[i] is the minimum number of operations to make all elements of nums equal to queries[i]. Note that after each query the array is reset to its original state.

Constraints

• n == nums.length
• m == queries.length
• `1

Example 1

Input:

nums = [3,1,6,8]
queries = [1,5]

Output:

[14,10]

Explanation: For the first query we can do the following operations:

• Decrease nums[0] 2 times, so that nums = [1,1,6,8].
• Decrease nums[2] 5 times, so that nums = [1,1,1,8].
• Decrease nums[3] 7 times, so that nums = [1,1,1,1]. So the total number of operations for the first query is 2 + 5 + 7 = 14. For the second query we can do the following operations:
• Increase nums[0] 2 times, so that nums = [5,1,6,8].
• Increase nums[1] 4 times, so that nums = [5,5,6,8].
• Decrease nums[2] 1 time, so that nums = [5,5,5,8].
• Decrease nums[3] 3 times, so that nums = [5,5,5,5]. So the total number of operations for the second query is 2 + 4 + 1 + 3 = 10.

Example 2

Input:

nums = [2,9,6,3]
queries = [10]

Output:

[20]

Explanation: We can increase each value in the array to 10. The total number of operations will be 8 + 1 + 4 + 7 = 20.

Given a binary string s, return the minimum number of bit flips needed to make s alternating (i.e. no two adjacent characters are equal). Either "0101..." or "1010..." may be the target.

Constraints

• 1 ≤ len(s) ≤ 2 × 10⁵
• s consists only of '0' and '1'.

Example 1

Input:

s = "11101"

Output:

1

Explanation: Flipping the bit at index 1 (0-based indexing) makes the string "10101", which is alternating. So the minimum operations is 1.

Example 2

Input:

s = "111101"

Output:

2

Explanation: Flip the 1st and 3rd characters (1-based indexing) to obtain "101010", which is alternating. Thus, the minimum operations is 2.

You are given the inclusive start and end times of n processes via parallel arrays start and end. Process i runs during the interval [start[i], end[i]]. Return the total wall-clock duration covered by at least one process (i.e. the length of the union of all intervals).

Constraints

• 1 ≤ n ≤ 2 × 10⁵
• 1 ≤ start[i] ≤ end[i] ≤ 10⁹

Example 1

Input:

start = [1, 2, 8]
end = [5, 6, 10]

Output:

9

Explanation: The first two processes merge into [1, 6] for 6 units. The third process contributes 3 more units from [8, 10]. Total = 9.

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 < length of sender_user_id, recipient_user_id, amount ≤ 9.
• The result will contain at least one element.

Given two arrays, serverCapacity, and serverLoad, each of size n, they represent the resource requirements or capacities of servers and the workload distribution across the servers. The total resource consumption is the sum of serverCapacity[i] * serverLoad[i] (0 ≤ i Function Description Complete the function rearrangeServerLoad in the editor. rearrangeServerLoad has the following parameters:

• 1. int[] serverCapacity: an array of integers representing server capacities
• 2. int[] serverLoad: an array of integers representing server loads Returns int[]: the rearranged array of server loads that minimizes the total resource consumption

Example 1

Input:

serverCapacity = [4, 5, 6]
serverLoad = [1, 2, 3]

Output:

[3, 2, 1]

Explanation: The task is to rearrange the elements in the array serverLoad to minimize the sum, serverCapacity[i] * serverLoad[i]. If serverLoad = [3, 2, 1], the total resources are calculated as follows: 4 * 3 + 5 * 2 + 6 * 1 = 28. This arrangement yields the lowest sum of resources.

Example 2

Input:

serverCapacity = [1, 2, 3, 3, 3]
serverLoad = [2, 2, 4, 5, 6]

Output:

[6, 5, 2, 2, 4]

Explanation: For the rearranged serverLoad = [6, 5, 2, 2, 4], the total resource requirement is calculated as follows: = 1 * 6 + 2 * 5 + 3 * 2 + 3 * 2 + 3 * 4 = 40. 40 is the minimum possible sum after rearranging the serverLoad array, hence the answer.

The process of initiating an action on a server is done through HTTP requests which are messages sent by the client. The two most commonly used HTTP requests are GET and POST. This task involves validating requests and parsing URL parameters as a comma-separated string. Authentication tokens for both GET and POST requests are sent as a URL parameter named "token". For validation of authentication, the tokens must be in a set of valid authentication tokens. In the case of a POST request, a CSRF (cross-site request forgery) token must also be provided. A POST request is considered valid if its authentication token is valid and its CSRF token is an alphanumeric value consisting only of lowercase letters and/or numbers with a minimum length of 8. Once a request is validated, the URL parameters must be parsed as a comma-separated string. URL parameters are identified by the portion of the URL that comes after a question mark (?). They consist of a key and a value, separated by an equal sign (=). Multiple parameters are separated by an ampersand (&). Implement a request parser prototype. Given an array of strings validAuthTokens (the valid authentication tokens) and a 2D array requests of [method, url] pairs, return for each request either "VALID,key1,value1,key2,value2,..." (with all parsed non-token/non-csrf query parameters in input order) or "INVALID".

Constraints

• 1 ≤ len(validAuthTokens), len(requests) ≤ 10⁴
• Each request is [method, url] where method ∈ {"GET", "POST"}.
• For POST requests, a csrf query parameter is required; it must be a lowercase-alphanumeric string of length ≥ 8.

Example 1

Input:

validAuthTokens = ["ah37j2ha483u", "safh34yw0bp5", "ba34wyi8t902"]
requests = [["GET", "https://example.com/?token=347sd6yk8iu2&name=alex"], ["GET", "https://example.com/?token=safh34yw0bp5&name=sam"], ["POST", "https://example.com/?token=safh34yw0bp5&name=alex"], ["POST", "https://example.com/?token=safh34yw0bp5&csrf=ak2sh32dy&name=chris"]]

Output:

["INVALID", "VALID,name,sam", "INVALID", "VALID,name,chris"]

Explanation:

• In the first request, the auth_token = 347sd6yk8iu2, which is not in the list of given tokens, so the request is INVALID. The string to be returned is "INVALID".
• In the second request, the auth_token = safh34yw0bp5, which is in the list of valid tokens, so the request is VALID. The request parameters are - name = sam. The string to be returned is "VALID,name,sam".
• In the third request, the auth_token = safh34yw0bp5, which is in the list of valid tokens, but since the request is a POST request, it must have a valid CSRF token. Since the given request doesn't have a CSRF token, the request is INVALID. The string to be returned is "INVALID".
• In the fourth request, the auth_token = safh34yw0bp5, which is in the list of valid tokens, but since the request is a POST request, it must have a valid CSRF token. CSRF_token = ak2sh32dy. It is an alphanumeric string with length 9 (≥8), so the given request is VALID. The request parameters are - name = chris. The string to be returned is "VALID,name,chris".

A Mars rover is directed to move within a square matrix. It accepts a sequence of commands to move in any of the four directions from each cell: [UP, DOWN, LEFT or RIGHT]. The rover starts from cell 0. and may not move diagonally or outside of the boundary. Each cell in the matrix has a position equal to: (row * size) + column where row and column are zero-indexed, size = row length of the matrix. Return the final position of the rover after all moves. Function Description Complete the function roverMove in the editor. roverMove has the following parameter(s):

• 1. int n: the size of the square matrix
• 2. String[] cmds: the commands Returns int: the label of the cell the rover occupies after executing all commands

Constraints

• 2 ≤ n ≤ 20
• 1 ≤ |cmds| ≤ 20

Example 1

Input:

n = 4
cmds = ["RIGHT", "UP", "DOWN", "LEFT", "DOWN", "DOWN"]

Output:

12

Explanation: The function returns 12.

Heartbeat events are recorded with a timestamp and a service ID. For each service, sort its heartbeats by timestamp and check the gaps between consecutive timestamps. A service is considered to have timed out if any such gap exceeds threshold. Return the IDs of all services that have timed out, sorted in lexicographic order.

Constraints

• 1 ≤ n ≤ 2 × 10⁵
• 1 ≤ timestamps[i] ≤ 10⁹
• 0 ≤ threshold ≤ 10⁹

Example 1

Input:

timestamps = [10, 20, 80, 10, 65]
serviceIds = ["svc1", "svc1", "svc1", "svc2", "svc2"]
threshold = 30

Output:

["svc1", "svc2"]

Explanation: svc1 has a 60-second gap between heartbeats at 20 and 80, and svc2 has a 55-second gap between 10 and 65. Both exceed the threshold.

Given an integer array, divide the array into 2 subsets A and B while respecting the following conditions: The intersection of A and B is null. The union A and B is equal to the original array. The number of elements in subset A is minimal. The sum of A's elements is greater than the sum of B's elements. Return the subset A in increasing order where the sum of A's elements is greater than the sum of B's elements. If more than one subset exists, return the one with the maximal sum. Function Description Complete the function subsetA in the editor. subsetA has the following parameter(s):

• int arr[]: an integer array Returns int[]: an integer array with the values of subset A.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁵ (where `0 ≤ i

Example 1

Input:

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

Output:

[4, 5]

Explanation: The subset of A that satisfies the conditions is [4, 5]:

• A is minimal (size 2)
• Sum(A) = (4 + 5) = 9 > Sum(B) = (1 + 2 + 2 + 3) = 8
• The intersection of A and B is null and their union is equal to arr.
• The subset A with the maximal sum is [4, 5].

Example 2

Input:

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

Output:

[5, 6]

Explanation: The subset of A that satisfies the conditions is [5, 6]:

• A is minimal (size 2)
• Sum(A) = (5 + 6) = 11 > Sum(B) = (1 + 2 + 4) = 7
• Sum(A) = (4 + 6) = 10 > Sum(B) = (1 + 2 + 5) = 8
• The intersection of A and B is null and their union is equal to arr.
• The subset A with the maximal sum is [5, 6].

Create a table of contents for a simple markup language. It must follow two rules: If a line starts with a single # followed by a space, then it's a chapter title. If a line starts with a double # followed by a space, then it's a section title. The table of contents should be displayed in the following format: Note that each number is followed by a period and the last period is followed by 1 space. Function Description Complete the function tableOfContents in the editor. tableOfContents has the following parameter:

• string text[n]: the input text Returns string[]: each string is a line in the table of contents

Constraints

• 1 ≤ n ≤ 1000
• 1 ≤ length of text[i] ≤ 100
• When a line starts with # or with ##, these special characters are always followed by a space.
• The first line of the text is guaranteed to be a chapter line.

Example 1

Input:

text = ["# Cars", "Cars came into global use during the 20th century", "Most definitions of car say they run primarily on roads", "## Sedan", "Sedan's first recorded use as a name for a car body was in 1912", "## Coupe", "Coupe is a passenger car with a sloping rear roofline and generally two doors", "## SUV", "The predecessors to SUVs date back to military and low-volume models from the late 1930s", "There is no commonly agreed definition of an SUV, and usage varies between countries."]

Output:

["1. Cars", "1.1. Sedan", "1.2. Coupe", "1.3. SUV"]

Explanation: The first line of input indicates there are n = 10 lines of text. There is only 1 chapter in the input, and it contains 3 sections. All the lines that don't begin with # or ## are ignored in the table of contents.

A popular social media platform provides a feature to connect people online. Connections are represented as an undirected graph where a user can see the profiles of those they are connected to. There are connection_nodes users numbered 1 to connection_nodes, and connection_edges connections where the pth pair connects nodes connection_from[p] and connection_to[p]. The queries array contains node numbers. Find the number of users whose profiles are visible to query[p]. Report an array of integers where the pth value is the answer to the pth query. Function Description Complete the function visibleProfilesCount in the editor. visibleProfilesCount has the following parameters:

• connection_nodes: an integer, the number of users
• connection_edges: an integer, the number of connections
• connection_from[p]: an array of integers, the starting nodes of each connection
• connection_to[p]: an array of integers, the ending nodes of each connection
• queries: an array of integers, the node numbers to query Returns int[]: an array of integers where the pth value is the number of visible profiles for the pth query

Example 1

Input:

connection_nodes = 7
connection_edges = 4
connection_from = [1, 2, 3, 5]
connection_to = [2, 3, 4, 6]
queries = [1, 3, 5, 7]

Output:

[4, 4, 2, 1]

Explanation: For each query, the number of visible profiles is calculated as follows:

• Query 1: Visible Profiles are [1, 2, 3, 4]. Number of Visible Profiles is 4.
• Query 3: Visible Profiles are [1, 2, 3, 4]. Number of Visible Profiles is 4.
• Query 5: Visible Profiles are [5, 6]. Number of Visible Profiles is 2.
• Query 7: Visible Profiles are []. Number of Visible Profiles is 1 (the user can see their own profile). Therefore, the function returns [4, 4, 2, 1].