Given an integer array arr[n] and an integer d, count the number of distinct triplets (i, j, k) where 0 <= i < j < k < n and arr[i] + arr[j] + arr[k] is divisible by d.

Example: arr = [2, 3, 1, 6], d = 3 → 2 (triplets (0,1,2) and (0,2,3)).

Constraints

3 ≤ n ≤ 10³, 1 ≤ arr[i] ≤ 10⁹, 2 ≤ d ≤ 10⁶.

解法

统计模 d 各余数的频次，再求满足 r1 + r2 + r3 ≡ 0 (mod d) 的有序三元组数。重复余数用二项系数处理。复杂度 O(n + d²)。

from math import comb

def get_triplet_count(a, d):
    cnt = [0] * d
    for x in a:
        cnt[x % d] += 1
    ans = 0
    for r1 in range(d):
        for r2 in range(r1, d):
            r3 = (d - (r1 + r2) % d) % d
            if r3 < r2:
                continue
            if r1 == r2 == r3:
                ans += comb(cnt[r1], 3)
            elif r1 == r2:
                ans += comb(cnt[r1], 2) * cnt[r3]
            elif r2 == r3:
                ans += cnt[r1] * comb(cnt[r2], 2)
            else:
                ans += cnt[r1] * cnt[r2] * cnt[r3]
    return ans

class Solution {
    static long getTripletCount(int[] a, int d) {
        long[] cnt = new long[d];
        for (int x : a) cnt[((x % d) + d) % d]++;
        long ans = 0;
        for (int r1 = 0; r1 < d; r1++)
            for (int r2 = r1; r2 < d; r2++) {
                int r3 = ((d - (r1 + r2) % d) % d);
                if (r3 < r2) continue;
                if (r1 == r2 && r2 == r3) ans += cnt[r1] * (cnt[r1] - 1) * (cnt[r1] - 2) / 6;
                else if (r1 == r2) ans += cnt[r1] * (cnt[r1] - 1) / 2 * cnt[r3];
                else if (r2 == r3) ans += cnt[r1] * cnt[r2] * (cnt[r2] - 1) / 2;
                else ans += cnt[r1] * cnt[r2] * cnt[r3];
            }
        return ans;
    }
}

#include <vector>
using namespace std;

long long getTripletCount(vector<int>& a, int d) {
 vector<long long> cnt(d, 0);
 for (int x : a) cnt[((x % d) + d) % d]++;
 long long ans = 0;
 for (int r1 = 0; r1 < d; r1++)
 for (int r2 = r1; r2 < d; r2++) {
 int r3 = ((d - (r1 + r2) % d) % d);
 if (r3 < r2) continue;
 if (r1 == r2 && r2 == r3) ans += cnt[r1] * (cnt[r1] - 1) * (cnt[r1] - 2) / 6;
 else if (r1 == r2) ans += cnt[r1] * (cnt[r1] - 1) / 2 * cnt[r3];
 else if (r2 == r3) ans += cnt[r1] * cnt[r2] * (cnt[r2] - 1) / 2;
 else ans += cnt[r1] * cnt[r2] * cnt[r3];
 }
 return ans;
}

Two integers are considered coprime if their greatest common divisor (GCD) is 1.

Given an array A of positive integers, return an array B of length len(A) where B[i] represents the count of integers in [1, A[i]] (inclusive) that are co-prime with A[i].

Example: A = [5, 8, 14] → B = [4, 4, 6].

Constraints

1 ≤ A[i] ≤ 10⁵.

解法

B[i] 即欧拉函数 φ(A[i])。对每个值用 sqrt(A[i]) 内的试除分解质因数，再套 φ(n) = n · Π(1 − 1/p)。复杂度 O(n · sqrt(max A))。

def coprime_count(A):
    def phi(n):
        result = n
        p = 2
        while p * p <= n:
            if n % p == 0:
                while n % p == 0:
                    n //= p
                result -= result // p
            p += 1
        if n > 1:
            result -= result // n
        return result
    return [phi(x) for x in A]

class Solution {
    static int phi(int n) {
        int res = n;
        for (int p = 2; (long) p * p <= n; p++) {
            if (n % p == 0) {
                while (n % p == 0) n /= p;
                res -= res / p;
            }
        }
        if (n > 1) res -= res / n;
        return res;
    }
    static int[] coprimeCount(int[] A) {
        int[] out = new int[A.length];
        for (int i = 0; i < A.length; i++) out[i] = phi(A[i]);
        return out;
    }
}

#include <vector>
using namespace std;

int phi(int n) {
 int res = n;
 for (int p = 2; (long long) p * p <= n; p++) {
 if (n % p == 0) {
 while (n % p == 0) n /= p;
 res -= res / p;
 }
 }
 if (n > 1) res -= res / n;
 return res;
}

vector<int> coprimeCount(vector<int>& A) {
 vector<int> out;
 out.reserve(A.size());
 for (int x : A) out.push_back(phi(x));
 return out;
}

Given a tree of tree_nodes vertices labeled 1..tree_nodes, each vertex i has value a[i]. Define the beauty of vertex v as Σ dis(i, v) * a[i] where dis(i, v) is the number of edges on the path from i to v. Return the maximum beauty over all vertices.

Example: 2 nodes, 1 edge, a = [3, 4]. beauty(1) = 0*3 + 1*4 = 4, beauty(2) = 1*3 + 0*4 = 3. max = 4.

解法

换根 DP。首次 DFS 算 beauty[1](Σ depth[v] · a[v])和子树权和 weight_sum[u] = Σ_{v in subtree(u)} a[v]。把根从父 p 移到子 u 时，u 子树所有节点深度 −1(节省 weight_sum[u])，其余节点深度 +1(增加 total − weight_sum[u])，所以 beauty[u] = beauty[p] − weight_sum[u] + (total − weight_sum[u])。复杂度 O(n)。

from collections import defaultdict

def max_beauty(n, tree_from, tree_to, a):
    g = defaultdict(list)
    for u, v in zip(tree_from, tree_to):
        g[u].append(v); g[v].append(u)
    parent = [0] * (n + 1)
    order, visited = [], [False] * (n + 1)
    stack = [1]; visited[1] = True
    while stack:
        u = stack.pop()
        order.append(u)
        for v in g[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                stack.append(v)
    weight_sum = [0] * (n + 1)
    for u in reversed(order):
        weight_sum[u] = a[u - 1] + sum(weight_sum[v] for v in g[u] if v != parent[u])
    depth = [0] * (n + 1)
    for u in order:
        for v in g[u]:
            if v != parent[u]:
                depth[v] = depth[u] + 1
    beauty = [0] * (n + 1)
    beauty[1] = sum(depth[v] * a[v - 1] for v in range(1, n + 1))
    total = sum(a)
    for u in order:
        if u == 1:
            continue
        beauty[u] = beauty[parent[u]] - weight_sum[u] + (total - weight_sum[u])
    return max(beauty[1:n + 1])

import java.util.*;

class Solution {
    static long maxBeauty(int n, int[] from_, int[] to_, int[] a) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        for (int i = 0; i < from_.length; i++) {
            g.get(from_[i]).add(to_[i]);
            g.get(to_[i]).add(from_[i]);
        }
        int[] parent = new int[n + 1];
        int[] order = new int[n];
        boolean[] vis = new boolean[n + 1];
        int idx = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1); vis[1] = true;
        while (!stack.isEmpty()) {
            int u = stack.pop();
            order[idx++] = u;
            for (int v : g.get(u)) if (!vis[v]) { vis[v] = true; parent[v] = u; stack.push(v); }
        }
        long[] weight = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            int u = order[i];
            weight[u] = a[u - 1];
            for (int v : g.get(u)) if (v != parent[u]) weight[u] += weight[v];
        }
        int[] depth = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int u = order[i];
            for (int v : g.get(u)) if (v != parent[u]) depth[v] = depth[u] + 1;
        }
        long total = 0;
        for (int x : a) total += x;
        long[] beauty = new long[n + 1];
        for (int v = 1; v <= n; v++) beauty[1] += (long) depth[v] * a[v - 1];
        for (int i = 1; i < n; i++) {
            int u = order[i];
            beauty[u] = beauty[parent[u]] - weight[u] + (total - weight[u]);
        }
        long ans = Long.MIN_VALUE;
        for (int v = 1; v <= n; v++) ans = Math.max(ans, beauty[v]);
        return ans;
    }
}

#include <bits/stdc++.h>
using namespace std;

long long maxBeauty(int n, vector<int>& from_, vector<int>& to_, vector<int>& a) {
 vector<vector<int>> g(n + 1);
 for (size_t i = 0; i < from_.size(); i++) {
 g[from_[i]].push_back(to_[i]);
 g[to_[i]].push_back(from_[i]);
 }
 vector<int> parent(n + 1, 0), order, depth(n + 1, 0);
 vector<bool> vis(n + 1, false);
 stack<int> st;
 st.push(1); vis[1] = true;
 while (!st.empty()) {
 int u = st.top(); st.pop();
 order.push_back(u);
 for (int v : g[u]) if (!vis[v]) { vis[v] = true; parent[v] = u; st.push(v); }
 }
 vector<long long> weight(n + 1, 0);
 for (int i = n - 1; i >= 0; i--) {
 int u = order[i];
 weight[u] = a[u - 1];
 for (int v : g[u]) if (v != parent[u]) weight[u] += weight[v];
 }
 for (int u : order)
 for (int v : g[u])
 if (v != parent[u]) depth[v] = depth[u] + 1;
 long long total = 0;
 for (int x : a) total += x;
 vector<long long> beauty(n + 1, 0);
 for (int v = 1; v <= n; v++) beauty[1] += (long long) depth[v] * a[v - 1];
 for (size_t i = 1; i < order.size(); i++) {
 int u = order[i];
 beauty[u] = beauty[parent[u]] - weight[u] + (total - weight[u]);
 }
 long long ans = LLONG_MIN;
 for (int v = 1; v <= n; v++) ans = max(ans, beauty[v]);
 return ans;
}

Q1: Probability — In a family, P(at least one parent ill) = 20%, P(father ill) = 12%, P(both ill) = 5%. What is P(mother ill)?

Answer: 13% Explanation: P(M) = P(A∪B) + P(A∩B) − P(F) = 20 + 5 − 12 = 13%.

Q2: Logic — Two rows of five students each face each other (Row-1, Row-2). Extremes are A/B/C/D; E is center of Row-1; F opposite E; J immediately right of A in Row-1; A and B in different rows and not opposite; I between F and B; H and C share a row. Which pair definitely shares a row?

Answer: G and D Explanation: Working through the seating constraints forces G and D into the same row as the only consistent assignment.

Q3: Vectors — Given vectors A and B, which statements are correct?

Answer: Dot product is 0 if orthogonal; cross product is 0 if collinear. Explanation: Orthogonality kills the dot product; collinearity (parallel or anti-parallel) kills the cross product.

Q4: Enrollment — 40 students; 12 in English, 27 in Chemistry, 9 in both. How many are in neither?

Answer: 10 Explanation: Either-class count = 12 + 27 − 9 = 30; neither = 40 − 30 = 10.

Q5: Charts — Over 1998-2002, how many of the 5 stocks (Warren Hays, Jackmail, Warren Bros, Brotherly Mail, Buffet Hastings) had a net overall price increase?

Answer: 3 Explanation: Compare 2002 vs 1998 per stock: Warren Hays 130 > 100, Warren Bros 175 > 100, Brotherly Mail 32 < 40, Jackmail 187 < 200, Buffet Hastings 129 < 132 — three net increases.

There are n Toy cars moving in road and you are given array direction of size n where direction[i] = 1 or -1, 1 means car going to right and -1 means car going to left and array strength. If two car collide at any point the car with lower strength will Blast and if both cars strength are equal then both will Blast. Returns how many cars will stay after all possible collision. Function Description CarsLeft has the following parameters:

• int n: The numbers of cars.
• int[] direction: The directions of each car.
• int[] strength: The strength of each car. Returns int[]: array Lists of Cars left after collisions in non-decreasing order.

Constraints

• n ≤ 2 * 10⁵
• direction[i] = 1 or dir

Example 1

Input:

n = 3
direction = [1, -1, 1]
strength = [5, 3, 2]

Output:

[0, 2]

Explanation: Car 0 going right and car 1 going left strength[0] > strength[1]. Therefore, when 0 and 1 meet, 1 will Blast.

Example 2

Input:

n = 5
direction = [1, -1, -1, 1, -1, 1]
strength = [7, 2, 3, 5, 5, 6]

Output:

[0, 4]

Explanation: Both car 2 and 3 will blast when they collide.

A trading firm predicts the stock prices of a commodity for the next n days. A period of consecutive days is considered investable if the maximum price in the period is max_price, and the minimum price in the period is min_price. Find the number of investable periods in the next n days. More formally, given an array price of length n, find the number of subarrays in which the maximum element is max_price and the minimum element is min_price. Note: A subarray is a sequence of consecutive elements of the array. Function Description Complete the function countInvestablePeriods in the editor below. countInvestablePeriods has the following parameters:

• int price[n]: the predicted prices for the next n days
• int max_price: the maximum price of an investable period
• int min_price: the minimum price of an investable period Returns long integer: the number of investable periods

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ price[i] ≤ 10⁹
• 1 ≤ min_price ≤ max_price ≤ 10⁹

Example 1

Input:

price = [4, 5, 3, 3, 1]
max_price = 5
min_price = 3

Output:

4

Explanation: Here, the periods [4, 5, 3], [4, 5, 3, 3], [5, 3], and [5, 3, 3] are investable.

Example 2

Input:

price = [2, 2, 1, 5, 1]
max_price = 2
min_price = 1

Output:

2

Explanation: The periods [2, 2, 1] and [2, 1] are investable.

Example 3

Input:

price = [1, 2, 3, 2]
max_price = 3
min_price = 2

Output:

3

Explanation: Hola!! This testcase was added on the 18th of May, 2025~ You can find the source image in the problem source section below. The consecutive periods [2, 3], [2, 3, 2], and [3, 2] are investable as the min and max of these subarrays equal min_price and max_price respective. There are no otehr periods that satisfy this constraint. So, answer is 3.

Hackerbank allows all citizens of the city of Hackerland to maintain their finances. In order to ensure security, given two integers n and k, a password is valid if: The length of the password is n. The password consists of lowercase English characters only. The password does not contain k consecutive equal characters. Given the integers n and k, find the number of distinct valid passwords that can be generated. Since the answer can be large, compute it modulo (10⁹ + 7). Function Description Complete the function countValidPasswords in the editor. countValidPasswords has the following parameters:

• int n: the length of the password
• int k: the number of matching consecutive characters should be less than this number Returns int: the number of valid passwords, modulo (10⁹ + 7)

Constraints

• 2 ≤ n ≤ 10⁵
• 2 ≤ k ≤ n

A foundry in Hackerland makes an alloy out of n different metals. In the manufacturing of an alloy, the composition of each metal is fixed, where the required quantity of the nth metal in preparing 1 unit of the alloy is denoted by composition[n]. The company already has stock[n] units of metal in their stock. The company has a budget to purchase any of the metals if needed. The cost of the nth metal is cost[n] per unit. Find the maximum units of alloys the company can produce by using available stock plus what they can purchase within their budget. Note: Their supplier has an infinite supply of all metal types. Function Description Complete the function findMaximumAlloyUnits in the editor. findMaximumAlloyUnits has the following parameters:

• int composition[n]: the composition of metals in 1 unit of alloy
• int stock[n]: the units of metals type that the company has in stock
• int cost[n]: the cost of each metal type
• int budget: the total money the company can spend Returns int: the maximum unit of alloys that can be produced

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ budget ≤ 10⁹
• 1 ≤ composition[i] ≤ 10⁹
• 1 ≤ stock[i] ≤ 10⁹
• 1 ≤ cost[i] ≤ 10⁹
• composition[i] ≤ cost[i] ≤ 10⁹

Example 1

Input:

composition = [1, 2]
stock = [0, 1]
cost = [1, 1]
budget = 3

Output:

1

Explanation: A maximum of 1 unit of alloy can be produced.

• The cost for 1 unit required quantity = [1, 2], stock = [0, 1], extra metal requirements = [1, 1], cost = (1 x 1) + (1 x 3) = 4, which is within the budget.
• The cost for 2 units required quantity = [2, 4], stock = [0, 1], extra metal requirements = [2, 3], cost = (2 x 1) + (3 x 3) = 11, which is beyond the budget. The answer is 1.

Given an array arr of n integers, in a single operation, one can choose two indices, i and j, and delete arr[i] from the array if 2 * arr[i] ≤ arr[j]. A particular element can be chosen at most once. Find the minimum possible size of the array after performing the operation any number of times, possibly zero.

Constraints

N/A

Example 1

Input:

arr = [1, 2, 3, 4, 16, 32, 64]

Output:

4

Explanation: • In the first operation, choose 1 and 16 and delete 1 from the array as 2 * 1 ≤ 16. The array becomes [2, 3, 4, 16, 32, 64]. • In the second operation, choose 2 and 32 and delete 2 from the array as 2 * 2 ≤ 32. The array becomes [3, 4, 16, 32, 64]. • In the third operation, choose 4 and 64 and delete 4 from the array as 2 * 4 ≤ 64. The array becomes [3, 16, 32, 64]. Now the only element that has not been chosen is 3. There have to be two elements, arr[i] and arr[j], for a comparison to take place, so no more operations can occur. The minimum possible size of the array is 4. Note that there are multiple ways to achieve 4 elements in the final array after performing the operations.

Analyze the difference in adjacent letters of the alphabet given a string. Given an input sequence of words, find the 'Odd One Out' by checking the difference between adjacent letters. The element having a distinct difference is the 'Odd One Out.' Function Description Complete the function findOdd in the editor. findOdd has the following parameter(s):

• string series[n]: an array of strings Returns string: the odd one out.

Constraints

• 3 ≤ n ≤ 26
• 2 ≤ length of series[i] ≤ 26
• All strings are uppercase English letters only.
• Within a test case, all strings are of equal length.

Example 1

Input:

series = ["ACB", "BDC", "CED", "DEF"]

Output:

"DEF"

Explanation: In the first three strings, the differences between the letters are (+2, -1), e.g. 'C' - 'A' = 2, 'B' - 'C' = -1. In the last string, the differences are (+1, +1). "DEF" is the odd one out.

Two interns at HackerRank are teamed up to complete a total of n tasks. Each task is to be completed by either of the two interns. Both interns have their reward points defined, where the first intern gains reward_1[i] points for completing the i^thth task, while the second intern gains reward_2[i] points for completing the i^thth task. Since the interns work as a team, they wish to maximize the total reward points gained by both of them combined. Find the maximum combined reward points that can be gained if the first intern has to complete k tasks, and the second intern completes the remaining tasks. Note: The k tasks completed by the first intern could be any amongst the n tasks. Function Description Complete the function getMaximumRewardPoints in the editor. getMaximumRewardPoints has the following parameters:

• 1. int k: the number of tasks that have to be completed by intern 1
• 2. int reward_1[n]: the reward points earned by intern 1 for each task
• 3. int reward_2[n]: the reward points earned by intern 2 for each task Returns int: the maximum possible combined reward points when intern 1 completes exactly k tasks

Constraints

• 1 ≤ n ≤ 10⁵
• 0 ≤ k ≤ n
• 1 ≤ reward_1[j] ≤ 10⁴
• 1 ≤ reward_2[j] ≤ 10⁴

Example 1

Input:

k = 3
reward_1 = [5, 4, 3, 2, 1]
reward_2 = [1, 2, 3, 4, 5]

Output:

21

Explanation: Intern 1 has to complete 3 tasks, while intern 2 has to complete the remaining 2 tasks. The reward points for each task are the same for both the interns, so any tasks can be picked up by either intern. Total reward points = 1 + 2 + 3 + 2 = 8.

Example 2

Input:

k = 2
reward_1 = [2, 3, 4, 2]
reward_2 = [1, 1, 1, 1]

Output:

9

Explanation: Intern 1 has to complete 2 tasks, while intern 2 has to complete the remaining 2 tasks. In order to maximize the total reward points, intern 1 completes the second and third tasks, while intern 2 completes the first and fourth tasks. Total reward points gained = 4 + 3 (from intern 1) + 1 + 1 (from intern 2) = 9.

You are given two integers n and d. Returns the numbers of Good Strings having length n and absolute difference between the adjacent characters 'a' to 'z' is not more than d. a and z have absolute difference 25. b and c have absolute difference 1. Function Description GoodStrings has the following parameters:

• n: The size of the string.
• d: The difference. Returns int number of Good Strings mod 10⁹ + 7.

Constraints

• n ≤ 10⁵
• d ≤ 25

Example 1

Input:

n = 2
d = 2

Output:

124

Explanation: There are 124 Good Strings of length 2 where the absolute difference between adjacent characters is not more than 2.

Example 2

Input:

n = 3
d = 5

Output:

2596

Explanation: There are 2596 Good Strings of length 3 where the absolute difference between adjacent characters is not more than 5.

Given a string array that contains n elements, each composed of lowercase English letters, and q queries, each query of the format i-r, for each query, determine how many strings starting from index i and ending at index r have vowels as the first and last character. Vowels are in {a,e,i,o,u}. Function Description Complete the function hasVowels in the editor below. It must return an array of integers that represent the result of each query in the order given. hasVowels has the following parameters:

• strArr string[]: an array of n strings
• query string[]: an array of q strings, each of which describes an interval i-r using integers delimited by a dash

Constraints

• 1 ≤ n, q ≤ 10⁵
• 1 ≤ i ≤ r ≤ n
• 1 ≤ size of strArr[i] ≤ 10

Example 1

Input:

strArr = ["aba","bcb","ece","aa","e"]
queries = ["1-3","2-5","2-2"]

Output:

[2, 3, 0]

Explanation: These strings represent two dash delimited integers i and r, the start and end indices of the interval, inclusive. Using 1-based indexing in the string array, the interval 1-3 contains two strings that start and end with a vowel: 'aba' and 'ece'. The interval 2-5 also has three. The third interval, from 2-2, the only element in the interval, 'bcb' does not begin and end with a vowel. The return array for the queries is [2, 3, 0].

Implement a prototype of a resource allocation system in a distributed parallel computing infrastructure. There are n resources and m tasks to schedule on them where the p^th task has a processing time of burstTime[i]. The total load time of a resource is the sum of the total burst times of the jobs assigned to the resources. However, a particular resource can be allocated jobs in a contiguous segment only i.e. from some index x to some index y or [x, x + 1, x + 2, ..., y]. Find the minimum possible value of the maximum total load time of the servers if resources are allocated optimally. Function Description Complete the function loadBalancing in the editor. loadBalancing has the following parameters:

• 1. int n: the number of resources
• 2. int[] burstTime: an array of integers representing the processing times of tasks Returns int: the minimum possible value of the maximum total load time of the servers

Constraints

• 1 ≤ n ≤ m ≤ 10^5
• 1 ≤ burstTime[i] ≤ 10^4

Example 1

Input:

n = 3
burstTime = [7, 2, 3, 4, 5]

Output:

9

Explanation: It is optimal to allocate the first job to the first resource, the last job to the second resource, and the remaining three jobs to the third resource. Total load times are 7, 5, and 2 + 3 + 4 = 9 respectively.

Given two arrays source and target, return the minimum number of operations to make the arrays equal. If it is impossible return -1. In 1 operation, you can select a prefix or suffix of the array and add 1 to all the elements in the selected subarray. For example, source = [1,2,2] and target = [2,2,3]. First operation: [2,2,2]. Next operation: [2,2,3]. Answer is 2. Function Description Complete the function minOperations in the editor. minOperations has the following parameters:

• 1. int[] source: an array of integers representing the source array
• 2. int[] target: an array of integers representing the target array Returns int: the minimum number of operations to make the arrays equal or -1 if impossible

Constraints

• Size of the array can be up to 10⁵
• element are in the range [-10¹³, 10¹³]

Example 1

Input:

source = [1,2,2]
target = [2,2,3]

Output:

2

Explanation: First operation: select the prefix [1] and add 1 to all its elements to get [2,2,2]. Next operation: select the suffix [3] and add 1 to all its elements to get [2,2,3]. The answer is 2 operations.

The beauty of an array of length m is defined as the number of integers i (1 ≤ i ≤ m) such that a[i] = i. Given an array arr of n integers, the following operation can be performed on the array while its length is greater than 1:

• Choose some i (1 ≤ i ≤ length of the array) and delete arr[i] without changing the order of the remaining elements. Find the maximum possible beauty of the array after performing this operation any number of times. Function Description Complete the function maximizeBeauty in the editor below. maximizeBeauty has the following parameter: int arr[n]: the given array Returns int: the maximum possible beauty of the array

Constraints

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

Example 1

Input:

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

Output:

4

Explanation: One optimal sequence of operations is shown.

• Choose i = 2, delete arr[2] = 3; arr = [1, 2, 5, 4, 5].
• Choose i = 6, delete arr[6] = 3; arr = [1, 2, 5, 4, 5] The beauty of arr is 4 since arr[1] = 1, arr[2] = 2, arr[4] = 4, and arr[5] = 5. Return 4. Note that there can be more than one final array with maximum beauty, like [1, 2, 5, 4, 5, 3] in this case.

Example 2

Input:

arr = [6, 3, 2, 4, 3, 4]

Output:

3

Explanation: One optimal sequence of operations is shown.

• Choose i = 2, delete arr[2] = 3; arr = [6, 2, 4, 3, 4].
• Choose i = 3, delete arr[3] = 4; arr = [6, 2, 3, 4]. arr[2] = 2, arr[3] = 3, and arr[4] = 4. The maximum possible beauty of the array is 3. Note that there can be more than one final arr with max beauty, like [1, 2, 5, 4, 5, 3] in this case.

Example 3

Input:

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

Output:

4

Explanation: One optimal sequence of operations is shown.

• Choose i = 2, delete arr[2] = 3; arr = [1, 2, 5, 4, 5, 3]
• Choose i = 6, delete arr[6] = 3; arr = [1, 2, 5, 4, 5] The beauty of arr is 4 since arr[1] = 1, arr[2] = 2, arr[4] = 4, and arr[5] = 5. Return 4.

Given a array of n positive and negative integers, find the subsequence with the maximum even sum and display that even sum.

Constraints

N/A

Example 1

Input:

arr = [-2, 2, -3, 1, 3]

Output:

6

Explanation: The longest subsequence with even sum is 2, 1 and 3.

Example 2

Input:

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

Output:

8

Explanation: The longest subsequence with even sum is 2, -3, 4 and 5.

Given a string s of lowercase English characters, the following operation can be performed on it any number of times.

• Choose three consecutive characters s[i], s[i+1] and s[i+2] where (1 ≤ i ≤ |s| - 2, 1-based indexing) such that s[i] = s[i+1] and s[i+1] ≠ s[i+2]. Replace s[i+2] with s[i].
• For example, if s = "aabc", then after the operation at i = 1, s = "aaac". Find the maximum number of operations that can be applied to s. Function Description Complete the function maximumNumberOfOperations in the editor. maximumNumberOfOperations has the following parameter:
• String s: the string to perform operations on Returns int: the maximum number of operations that can be applied

Constraints

len of string can be up to 10⁵

Example 1

Input:

s = "accept"

Output:

3

Explanation: The following operations are performed. Bold indicates the changed character.

• In the original string, start at i = 2, "cce". The new string s' = "accpct".
• Start at i = 3, s' = "acccct".
• Start at i = 4 s' = "accccc". The maximum number of operations that can be applied is 3. (Not very sure about the output and explanation. If you happen to know about it, feel free to lmk! Manyyy thanks in advance! )

Example 2

Input:

s = "accept"

Output:

3

Explanation: The following operations are performed. Bold indicates the changed character.

• In the original string, start at i = 2, "cce". The new string s' = "accpct".
• Start at i = 3, s' = "acccct".
• Start at i = 4 s' = "accccc". The maximum number of operations that can be applied is 3. (Not very sure about the output and explanation. If you happen to know about it, feel free to lmk! Manyyy thanks in advance! )

One of the shops in HackerMall is offering discount coupons based on a puzzling problem. There are n tags where each tag has a value denoted by val[i]. A customer needs to choose the tags in such a way that the sum of values is even. 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. Function Description Complete the function maximumPossibleEvenSum in the editor. maximumPossibleEvenSum has the following parameter:

• int val[]: an array of integers representing the values of tags Returns int: the maximum possible even sum of values of tags that can be chosen

Two teams have skill arrays teamA and teamB. A value of

Constraints

• 1 ≤ n, m ≤ 10⁵
• 0 ≤ teamA[i], teamB[i] ≤ 10⁴

Example 1

Input:

teamA = [5, 10, 0, 4]
teamB = [2, 4, 0, 5, 0]

Output:

20

Explanation: Fill the zero in teamA with 1, and the zeros in teamB with 3 and 6. Both teams then sum to 20, which is the minimum equal sum.

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 a square integer matrix grid and an integer maxSum, return the largest k such that there exists a k × k contiguous sub-grid whose sum is ≤ maxSum. If no 1 × 1 sub-grid qualifies, return 0.

Constraints

• grid is an n × n matrix, 1 ≤ n ≤ 500
• 0 ≤ grid[i][j] ≤ 10⁵
• 1 ≤ maxSum ≤ 10¹⁰

Example 1

Input:

grid = [[2, 2, 2], [3, 3, 3], [4, 4, 4]]
maxSum = 4

Output:

0

Explanation: Every 1 x 1 square in the last row sums to 4, but no larger square stays within the limit. Under the prompt's example, the maximum valid size is 0.