**Physical Address**

304 North Cardinal St.

Dorchester Center, MA 02124

A shop is selling candies at a discount. For **every two** candies sold, the shop gives a **third** candy for **free**.

The customer can choose **any** candy to take away for free as long as the cost of the chosen candy is less than or equal to the **minimum** cost of the two candies bought.

- For example, if there are
`4`

candies with costs`1`

,`2`

,`3`

, and`4`

, and the customer buys candies with costs`2`

and`3`

, they can take the candy with cost`1`

for free, but not the candy with cost`4`

.

Given a **0-indexed** integer array `cost`

, where `cost[i]`

denotes the cost of the `i`

candy, return ^{th}*the minimum cost of buying all the candies*.

**Example 1:**

```
Input: cost = [1,2,3]
Output: 5
Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free.
The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies.
Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free.
The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.
```

**Example 2:**

```
Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: The way in which we can get the minimum cost is described below:
- Buy candies with costs 9 and 7
- Take the candy with cost 6 for free
- We buy candies with costs 5 and 2
- Take the last remaining candy with cost 2 for free
Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.
```

**Example 3:**

```
Input: cost = [5,5]
Output: 10
Explanation: Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free.
Hence, the minimum cost to buy all candies is 5 + 5 = 10.
```

**Constraints:**

`1 <= cost.length <= 100`

`1 <= cost[i] <= 100`

```
var minimumCost = function(cost) {
if (cost.length < 3) {
return cost.reduce((prev, cur) => prev + cur);
}
cost.sort((a, b) => b - a);
let count = 0;
let sum = 0;
for (const num of cost) {
if (count === 2) {
count = 0;
continue;
}
sum += num;
count++;
}
return sum;
};
```

```
public int minimumCost(int[] A) {
Arrays.sort(A);
int res = 0, n = A.length;
for (int i = 0; i < n; ++i)
if (i % 3 != n % 3)
res += A[i];
return res;
}
```

```
int minimumCost(vector<int>& A) {
sort(A.begin(), A.end());
int res = 0, n = A.size();
for (int i = 0; i < A.size(); ++i)
if (i % 3 != n % 3)
res += A[i];
return res;
}
```

```
class Solution:
def minimumCost(self, cost: List[int]) -> int:
cost.sort(reverse=True)
res, i, N = 0, 0, len(cost)
while i < N:
res += sum(cost[i : i + 2])
i += 3
return res
```

```
class Solution:
def minimumCost(self, cost: List[int]) -> int:
return sum(x for i, x in enumerate(sorted(cost, reverse=True)) if (i+1)%3)
```

You are given a **0-indexed** array of `n`

integers `differences`

, which describes the **differences **between each pair of **consecutive **integers of a **hidden** sequence of length `(n + 1)`

. More formally, call the hidden sequence `hidden`

, then we have that `differences[i] = hidden[i + 1] - hidden[i]`

.

You are further given two integers `lower`

and `upper`

that describe the **inclusive** range of values `[lower, upper]`

that the hidden sequence can contain.

- For example, given
`differences = [1, -3, 4]`

,`lower = 1`

,`upper = 6`

, the hidden sequence is a sequence of length`4`

whose elements are in between`1`

and`6`

(**inclusive**).`[3, 4, 1, 5]`

and`[4, 5, 2, 6]`

are possible hidden sequences.`[5, 6, 3, 7]`

is not possible since it contains an element greater than`6`

.`[1, 2, 3, 4]`

is not possible since the differences are not correct.

Return *the number of possible hidden sequences there are.* If there are no possible sequences, return

`0`

.**Example 1:**

```
Input: differences = [1,-3,4], lower = 1, upper = 6
Output: 2
Explanation: The possible hidden sequences are:
- [3, 4, 1, 5]
- [4, 5, 2, 6]
Thus, we return 2.
```

**Example 2:**

```
Input: differences = [3,-4,5,1,-2], lower = -4, upper = 5
Output: 4
Explanation: The possible hidden sequences are:
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
Thus, we return 4.
```

**Example 3:**

```
Input: differences = [4,-7,2], lower = 3, upper = 6
Output: 0
Explanation: There are no possible hidden sequences. Thus, we return 0.
```

**Constraints:**

`n == differences.length`

`1 <= n <= 10`

^{5}`-10`

^{5}<= differences[i] <= 10^{5}`-10`

^{5}<= lower <= upper <= 10^{5}

```
public int numberOfArrays(int[] diff, int lower, int upper) {
long a = 0, ma = 0, mi = 0;
for (int d: diff) {
a += d;
ma = Math.max(ma, a);
mi = Math.min(mi, a);
}
return (int)Math.max(0, (upper - lower) - (ma - mi) + 1);
}
```

```
int numberOfArrays(vector<int>& diff, int lower, int upper) {
long a = 0, ma = 0, mi = 0;
for (int d: diff) {
a += d;
ma = max(ma, a);
mi = min(mi, a);
}
return max(0L, (upper - lower) - (ma - mi) + 1);
}
```

```
def numberOfArrays(self, diff, lower, upper):
A = list(accumulate(diff, initial = 0))
return max(0, (upper - lower) - (max(A) - min(A)) + 1)
```

```
fun numberOfArrays(differences: IntArray, lower: Int, upper: Int): Int {
var accSum = 0L
var minSum = 0L
var maxSum = 0L
for(diff in differences){
accSum += diff
minSum = minOf(accSum , minSum)
maxSum = maxOf(accSum, maxSum)
}
return maxOf(0, (upper- lower) - (maxSum - minSum) +1).toInt()
}
```

```
class Solution:
def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
# Largest Increment
maxAdd = 0;
# Largest Decrement
minSub = 0;
# Current Difference
currDiff = 0;
# Calculating above values in this loop
for i in range(len(differences)):
currDiff += differences[i]
# We need largest increment, so we choose the maximum value
maxAdd = max(currDiff, maxAdd)
# We need largest decrement, so we choose the minimum value
minSub = min(currDiff, minSub)
# Return 0 if value of the equation is negative
return max(0, (upper - maxAdd) - (lower - minSub) + 1);
```

You are given a **0-indexed** 2D integer array `grid`

of size `m x n`

that represents a map of the items in a shop. The integers in the grid represent the following:

`0`

represents a wall that you cannot pass through.`1`

represents an empty cell that you can freely move to and from.- All other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.

It takes `1`

step to travel between adjacent grid cells.

You are also given integer arrays `pricing`

and `start`

where `pricing = [low, high]`

and `start = [row, col]`

indicates that you start at the position `(row, col)`

and are interested only in items with a price in the range of `[low, high]`

(**inclusive**). You are further given an integer `k`

.

You are interested in the **positions** of the `k`

**highest-ranked** items whose prices are **within** the given price range. The rank is determined by the **first** of these criteria that is different:

- Distance, defined as the length of the shortest path from the
`start`

(**shorter**distance has a higher rank). - Price (
**lower**price has a higher rank, but it must be**in the price range**). - The row number (
**smaller**row number has a higher rank). - The column number (
**smaller**column number has a higher rank).

Return *the *`k`

* highest-ranked items within the price range sorted by their rank (highest to lowest)*. If there are fewer than

`k`

reachable items within the price range, return **Example 1:**

```
Input: grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
Output: [[0,1],[1,1],[2,1]]
Explanation: You start at (0,0).
With a price range of [2,5], we can take items from (0,1), (1,1), (2,1) and (2,2).
The ranks of these items are:
- (0,1) with distance 1
- (1,1) with distance 2
- (2,1) with distance 3
- (2,2) with distance 4
Thus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1).
```

**Example 2:**

```
Input: grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
Output: [[2,1],[1,2]]
Explanation: You start at (2,3).
With a price range of [2,3], we can take items from (0,1), (1,1), (1,2) and (2,1).
The ranks of these items are:
- (2,1) with distance 2, price 2
- (1,2) with distance 2, price 3
- (1,1) with distance 3
- (0,1) with distance 4
Thus, the 2 highest ranked items in the price range are (2,1) and (1,2).
```

**Example 3:**

```
Input: grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
Output: [[2,1],[2,0]]
Explanation: You start at (0,0).
With a price range of [2,3], we can take items from (2,0) and (2,1).
The ranks of these items are:
- (2,1) with distance 5
- (2,0) with distance 6
Thus, the 2 highest ranked items in the price range are (2,1) and (2,0).
Note that k = 3 but there are only 2 reachable items within the price range.
```

**Constraints:**

`m == grid.length`

`n == grid[i].length`

`1 <= m, n <= 10`

^{5}`1 <= m * n <= 10`

^{5}`0 <= grid[i][j] <= 10`

^{5}`pricing.length == 2`

`2 <= low <= high <= 10`

^{5}`start.length == 2`

`0 <= row <= m - 1`

`0 <= col <= n - 1`

`grid[row][col] > 0`

`1 <= k <= m * n`

```
class Solution:
def highestRankedKItems(self, G, pricing, start, k):
m, n = len(G), len(G[0])
row, col = start
node = (0, G[row][col], row, col)
visited = set()
visited.add((row, col))
d = deque([node])
ans = []
while d:
dist, cost, row, col = d.popleft()
if pricing[0] <= cost <= pricing[1]:
ans += [(dist, cost, row, col)]
for x, y in (row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1):
if 0 <= x <= m-1 and 0 <= y <= n-1 and (x, y) not in visited and G[x][y] != 0:
d.append((dist + 1, G[x][y], x, y))
visited.add((x, y))
ans = sorted(ans)
return [[x, y] for _, _, x, y in ans[:k]]
```

```
class Solution {
public:
vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& price, vector<int>& start, int k) {
int m=grid.size(),n=grid[0].size();
vector<vector<int>>ans,res;
// visited array
vector<vector<bool>>seen(m,vector<bool>(n,false));
// queue for BFS
queue<pair<int,int>>q;
q.push({start[0],start[1]});
//directions
vector<vector<int>>dirs={{-1,0},{0,-1},{0,1},{1,0}};
// distance
int dist=0;
while(!q.empty()){
int size=q.size();
while(size--){
auto p=q.front();
q.pop();
// already visited cell
if(seen[p.first][p.second])
continue;
// found wall
if(grid[p.first][p.second]==0)
continue;
// make the cell visited ,if visiting first time
seen[p.first][p.second]=true;
// if the value is 1 then it is empty cell so first check it
if(grid[p.first][p.second]!=1){
int val=grid[p.first][p.second];
// cell value should be in the range of price,if yes then push it to array or min-heap
if(val>=price[0] && val<=price[1])
res.push_back({dist,val,p.first,p.second});
}
// check other cells which you can reach from current cell
for(auto & dir:dirs){
int row=p.first+dir[0],col=dir[1]+p.second;
if(row>=0 && row<m && col>=0 && col<n)
q.push({row,col});
}
}
dist++;
}
// sort the array, if you have used min-heap,then obviously there is no need
sort(res.begin(),res.end());
// first k values or whole vector,whatever is minimum
for(int i=0;i<min(int(k),int(res.size()));i++)
ans.push_back({res[i][2],res[i][3]});
return ans;
}
};
```

```
private static final int[] d = {0, 1, 0, -1, 0};
public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
int R = grid.length, C = grid[0].length;
int x = start[0], y = start[1], low = pricing[0], high = pricing[1];
Set<String> seen = new HashSet<>(); // Set used to prune duplicates.
seen.add(x + "," + y);
List<List<Integer>> ans = new ArrayList<>();
// PriorityQueue sorted by (distance, price, row, col).
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] == b[1] ? a[2] == b[2] ? a[3] - b[3] : a[2] - b[2] : a[1] - b[1] : a[0] - b[0]);
pq.offer(new int[]{0, grid[x][y], x, y}); // BFS starting point.
while (!pq.isEmpty() && ans.size() < k) {
int[] cur = pq.poll();
int distance = cur[0], price = cur[1], r = cur[2], c = cur[3]; // distance, price, row & column.
if (low <= price && price <= high) { // price in range?
ans.add(Arrays.asList(r, c));
}
for (int m = 0; m < 4; ++m) { // traverse 4 neighbors.
int i = r + d[m], j = c + d[m + 1];
// in boundary, not wall, and not visited yet?
if (0 <= i && i < R && 0 <= j && j < C && grid[i][j] > 0 && seen.add(i + "," + j)) {
pq.offer(new int[]{distance + 1, grid[i][j], i, j});
}
}
}
return ans;
}
```

```
def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
R, C = map(len, (grid, grid[0]))
ans, (x, y), (low, high) = [], start, pricing
heap = [(0, grid[x][y], x, y)]
seen = {(x, y)}
while heap and len(ans) < k:
distance, price, r, c = heapq.heappop(heap)
if low <= price <= high:
ans.append([r, c])
for i, j in (r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c):
if R > i >= 0 <= j < C and grid[i][j] > 0 and (i, j) not in seen:
seen.add((i, j))
heapq.heappush(heap, (distance + 1, grid[i][j], i, j))
return ans
```

Along a long library corridor, there is a line of seats and decorative plants. You are given a **0-indexed** string `corridor`

of length `n`

consisting of letters `'S'`

and `'P'`

where each `'S'`

represents a seat and each `'P'`

represents a plant.

One room divider has **already** been installed to the left of index `0`

, and **another** to the right of index `n - 1`

. Additional room dividers can be installed. For each position between indices `i - 1`

and `i`

(`1 <= i <= n - 1`

), at most one divider can be installed.

Divide the corridor into non-overlapping sections, where each section has **exactly two seats** with any number of plants. There may be multiple ways to perform the division. Two ways are **different** if there is a position with a room divider installed in the first way but not in the second way.

Return *the number of ways to divide the corridor*. Since the answer may be very large, return it **modulo** `10`

. If there is no way, return ^{9} + 7`0`

.

**Example 1:**

```
Input: corridor = "SSPPSPS"
Output: 3
Explanation: There are 3 different ways to divide the corridor.
The black bars in the above image indicate the two room dividers already installed.
Note that in each of the ways, each section has exactly two seats.
```

**Example 2:**

```
Input: corridor = "PPSPSP"
Output: 1
Explanation: There is only 1 way to divide the corridor, by not installing any additional dividers.
Installing any would create some section that does not have exactly two seats.
```

**Example 3:**

```
Input: corridor = "S"
Output: 0
Explanation: There is no way to divide the corridor because there will always be a section that does not have exactly two seats.
```

**Constraints:**

`n == corridor.length`

`1 <= n <= 10`

^{5}`corridor[i]`

is either`'S'`

or`'P'`

.

```
int numberOfWays(string s) {
long res = 1, j = 0, k = 0, mod = 1e9 + 7;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == 'S') {
if (++k > 2 && k % 2 == 1)
res = res * (i - j) % mod;
j = i;
}
}
return k % 2 == 0 && k > 0 ? res : 0;
}
```

```
public int numberOfWays(String s) {
long res = 1, j = 0, k = 0, mod = (long)1e9 + 7;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == 'S') {
if (++k > 2 && k % 2 == 1)
res = res * (i - j) % mod;
j = i;
}
}
return k % 2 == 0 && k > 0 ? (int)res : 0;
}
```

```
def numberOfWays(self, s):
a = [i for i,c in enumerate(s) if c == 'S']
res = 1
for i in xrange(1,len(a) - 1,2):
res *= a[i+1] - a[i]
return res % (10**9+7) * (len(a) % 2 == 0 and len(a) >= 2)
```

In our experience, we suggest you solve this Biweekly Contest 70 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Biweekly Contest 70 LeetCode Solution

I hope this Biweekly Contest 70 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

**More Coding Solutions >>**