330. Patching Array
Difficulty: Hard
Problem Statement:
Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] (inclusive) can be formed by the sum of some elements in the array.
Return the minimum number of patches required.
Example 1:
Input: nums = [1, 3], n = 6
Output: 1
Explanation:
The combinations of nums are [1], [3], [1, 3], which form possible sums of 1, 3, 4.
Now if we add/patch 2 to nums, the combinations become [1], [2], [3], [1, 3], [2, 3], [1, 2, 3], covering all sums 1, 2, 3, 4, 5, 6.
Thus, only 1 patch is needed.
Example 2:
Input: nums = [1, 5, 10], n = 20
Output: 2
Explanation:
The two patches can be [2, 4].
Example 3:
Input: nums = [1, 2, 2], n = 5
Output: 0
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 10^4
nums is sorted in ascending order.
1 <= n <= 2^31 - 1
Solution :
Difficulty: Hard
Problem Statement:
Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] (inclusive) can be formed by the sum of some elements in the array.
Return the minimum number of patches required.
Example 1:
Input: nums = [1, 3], n = 6
Output: 1
Explanation:
The combinations of nums are [1], [3], [1, 3], which form possible sums of 1, 3, 4.
Now if we add/patch 2 to nums, the combinations become [1], [2], [3], [1, 3], [2, 3], [1, 2, 3], covering all sums 1, 2, 3, 4, 5, 6.
Thus, only 1 patch is needed.
Example 2:
Input: nums = [1, 5, 10], n = 20
Output: 2
Explanation:
The two patches can be [2, 4].
Example 3:
Input: nums = [1, 2, 2], n = 5
Output: 0
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 10^4
nums is sorted in ascending order.
1 <= n <= 2^31 - 1
Solution :
class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
patches = 0
miss = 1
i = 0
while miss <= n:
if i < len(nums) and nums[i] <= miss:
miss += nums[i]
i += 1
else:
miss += miss
patches += 1
return patches
👍2
135. Candy
Hard
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Example 1:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
Constraints:
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
i didnt know it had a simple ans; my ans is like thousand lines
Hard
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Example 1:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
Constraints:
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
candies = [1] * n # Give every child 1 candy initially
# Left-to-right pass: if a child has a higher rating than the left neighbor, give one more candy
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# Right-to-left pass: if a child has a higher rating than the right neighbor, ensure they have more candy
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)
i didnt know it had a simple ans; my ans is like thousand lines
👍2
Forwarded from Codeforces Official
Unfortunately, due to technical reasons, the round is postponed by 8.5 hours (to the usual scheduled time). We apologize for any inconvenience caused.
👍3
Forwarded from Codeforces Official
Educational Codeforces Round 176
(rated for Div. 2) starts in ~2 hours.
Please, join by the link https://codeforces.com/contests/2075
(rated for Div. 2) starts in ~2 hours.
Please, join by the link https://codeforces.com/contests/2075
Codeforces
Educational Codeforces Round 176 (Rated for Div. 2) - Codeforces
Codeforces. Programming competitions and contests, programming community
A big thank you to everyone at this channel and Alpha ,for a great session! I really enjoyed it.
❤7
Here is our very first leetcode Tree problem (BFS). Answer will be posted at 6:00 PM
LeetCode
Binary Tree Level Order Traversal - LeetCode
Can you solve this real interview question? Binary Tree Level Order Traversal - Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Example 1:
[https://assets.leetcode.c…
Example 1:
[https://assets.leetcode.c…
👍3
Leetcode with dani
Here is our very first leetcode Tree problem (BFS). Answer will be posted at 6:00 PM
102. Binary Tree Level Order Traversal
Difficulty: Medium
▎Problem Statement
Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).
▎Examples
Example 1:
• Input:
• Output:
Example 2:
• Input:
• Output:
Example 3:
• Input:
• Output:
▎Constraints
• The number of nodes in the tree is in the range
•
Difficulty: Medium
▎Problem Statement
Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).
▎Examples
Example 1:
• Input:
root = [3,9,20,null,null,15,7]• Output:
[[3],[9,20],[15,7]]Example 2:
• Input:
root = [1]• Output:
[[1]]Example 3:
• Input:
root = []• Output:
[]▎Constraints
• The number of nodes in the tree is in the range
[0, 2000].•
-1000 <= Node.val <= 1000
Leetcode with dani
Here is our very first leetcode Tree problem (BFS). Answer will be posted at 6:00 PM
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def helper(qu):
if not qu:
return
i = len(qu)
temp = []
nextsize = 0
while i > 0 :
poped = qu.popleft()
temp.append(poped.val)
if poped.left:
qu.append(poped.left)
nextsize += 1
if poped.right:
qu.append(poped.right)
nextsize += 1
i -= 1
ans.append(temp)
helper(qu)
if not root:
return []
ans =[]
q = deque()
q.append(root)
helper(q)
return ans
❤1
#Tree second question Answer will be posted at 4 PM
LeetCode
Average of Levels in Binary Tree - LeetCode
Can you solve this real interview question? Average of Levels in Binary Tree - Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.
Example…
Example…
👍3
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
def helper(qu):
if not qu:
return
i = len(qu)
leng = len(qu)
total = 0
while i > 0:
poped = qu.popleft()
total += poped.val
if poped.left:
qu.append(poped.left)
if poped.right:
qu.append(poped.right)
i -= 1
ans.append(total/leng)
helper(qu)
qu = deque()
qu.append(root)
ans = []
helper(qu)
return ans
👍2✍1
Forwarded from Codeforces Official
Codeforces Round 1011 (Div. 2) will take place on the 22nd of March at 14:35 UTC.
Please, join by the link https://codeforces.com/contests/2085?locale=en
Please, join by the link https://codeforces.com/contests/2085?locale=en
Codeforces
Codeforces Round 1011 (Div. 2) - Codeforces
Codeforces. Programming competitions and contests, programming community
Forwarded from Codeforces Official
Codeforces Round #1012 (Div. 1, Div. 2) will take place on the 23rd of March at 05:35 UTC.
Please, join by the link https://codeforces.com/contests/2089,2090?locale=en
Please, join by the link https://codeforces.com/contests/2089,2090?locale=en
Codeforces
Codeforces Round 1012 - Codeforces
Codeforces. Programming competitions and contests, programming community
▎2169. Count Operations to Obtain Zero
▎Problem
You are given two non-negative integers,
• If
• If
Repeat this until either
▎Examples
▎Example 1
Input:
Output:
▎Example 2
Input:
Output:
▎Constraints
• 0 ≤ num1, num2 ≤ 10⁵
▎Problem
You are given two non-negative integers,
num1 and num2. In one operation, do the following:• If
num1 >= num2, subtract num2 from num1.• If
num1 < num2, subtract num1 from num2.Repeat this until either
num1 or num2 becomes zero. Return the total number of operations performed.▎Examples
▎Example 1
Input:
num1 = 2, num2 = 3 Output:
3 ▎Example 2
Input:
num1 = 10, num2 = 10 Output:
1 ▎Constraints
• 0 ≤ num1, num2 ≤ 10⁵
LeetCode
Count Operations to Obtain Zero - LeetCode
Can you solve this real interview question? Count Operations to Obtain Zero - You are given two non-negative integers num1 and num2.
In one operation, if num1 >= num2, you must subtract num2 from num1, otherwise subtract num1 from num2.
* For example,…
In one operation, if num1 >= num2, you must subtract num2 from num1, otherwise subtract num1 from num2.
* For example,…
Leetcode with dani
▎2169. Count Operations to Obtain Zero ▎Problem You are given two non-negative integers, num1 and num2. In one operation, do the following: • If num1 >= num2, subtract num2 from num1. • If num1 < num2, subtract num1 from num2. Repeat this until either…
class Solution:
def countOperations(self, num1: int, num2: int) -> int:
count = 0
while num1 and num2:
if num1>=num2:
count += num1//num2
num1 = num1%num2
else:
count += num2//num1
num2 = num2%num1
return count