Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Biweekly Contest 70 LeetCode Solution
Problem 1 – Minimum Cost of Buying Candies With Discount Leetcode Solution
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
4candies with costs1,2,3, and4, and the customer buys candies with costs2and3, they can take the candy with cost1for free, but not the candy with cost4.
Given a 0-indexed integer array cost, where cost[i] denotes the cost of the ith candy, return 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 <= 1001 <= cost[i] <= 100
Minimum Cost of Buying Candies With Discount Leetcode Solution in JavaScript
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;
};
Minimum Cost of Buying Candies With Discount Leetcode Solution in Java
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;
}
Minimum Cost of Buying Candies With Discount Leetcode Solution in C++
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;
}
Minimum Cost of Buying Candies With Discount Leetcode Solution in Python
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
Minimum Cost of Buying Candies With Discount Leetcode Solution in Python 3
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)
Problem 2 – Count the Hidden Sequences Leetcode Solution
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 length4whose elements are in between1and6(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 than6.[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.length1 <= n <= 105-105 <= differences[i] <= 105-105 <= lower <= upper <= 105
Count the Hidden Sequences Leetcode Solution in Java
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);
}
Count the Hidden Sequences Leetcode Solution in C++
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);
}
Count the Hidden Sequences Leetcode Solution in Python 3
def numberOfArrays(self, diff, lower, upper):
A = list(accumulate(diff, initial = 0))
return max(0, (upper - lower) - (max(A) - min(A)) + 1)
Count the Hidden Sequences Leetcode Solution in Kotlin
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()
}
Count the Hidden Sequences Leetcode Solution in Python
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);
Problem 3 – K Highest Ranked Items Within a Price Range Leetcode Solution
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:
0represents a wall that you cannot pass through.1represents 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 all of them.
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.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1050 <= grid[i][j] <= 105pricing.length == 22 <= low <= high <= 105start.length == 20 <= row <= m - 10 <= col <= n - 1grid[row][col] > 01 <= k <= m * n
K Highest Ranked Items Within a Price Range Leetcode Solution in Python
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]]
K Highest Ranked Items Within a Price Range Leetcode Solution in C++
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;
}
};
K Highest Ranked Items Within a Price Range Leetcode Solution in Java
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;
}
K Highest Ranked Items Within a Price Range Leetcode Solution in Python
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
Problem 4 – Number of Ways to Divide a Long Corridor Leetcode Solution
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 109 + 7. If there is no way, return 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.length1 <= n <= 105corridor[i]is either'S'or'P'.
Number of Ways to Divide a Long Corridor Leetcode Solution in C++
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;
}
Number of Ways to Divide a Long Corridor Leetcode Solution in Java
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;
}
Number of Ways to Divide a Long Corridor Leetcode Solution in Python
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)
Biweekly Contest 70 LeetCode Solution Review:
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
Conclusion:
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 >>
