Skip to content

Commit 5da411f

Browse files
author
Partho Biswas
committed
readme
1 parent 18c1c87 commit 5da411f

File tree

2 files changed

+75
-2
lines changed

2 files changed

+75
-2
lines changed

‎README.md

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -182,7 +182,8 @@ I have solved quite a number of problems from several topics. See the below tabl
182182
|06| [410. Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/)| [Python](leetcode.com/python/410_Split_Array_Largest_Sum.py)| [Article 01](https://leetcode.com/problems/split-array-largest-sum/solution/)| Hard | 📌 Not done |
183183
|07| [4. Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/)| [Python](leetcode.com/python/4_Median_of_Two_Sorted_Arrays.py)| [Article 01](https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2755/9-lines-O(log(min(mn)))-Python), [Video 1](https://www.youtube.com/watch?v=LPFhl65R7ww)| Hard | 📌 Classic problem |
184184
|08| [981. Time Based Key-Value Store](https://leetcode.com/problems/time-based-key-value-store/)| [Python](leetcode.com/python/981_Time_Based_Key-Value_Store.py)| [Article 01](https://leetcode.com/problems/time-based-key-value-store/solution/)| Medium | 📌 |
185-
|09| [222. Count Complete Tree Nodes](https://leetcode.com/problems/count-complete-tree-nodes//)| [Python](leetcode.com/python/222_Count_Complete_Tree_Nodes.py)| [Theory](http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/bin-tree.html), [Official Solution](https://leetcode.com/problems/count-complete-tree-nodes/solution/), [Fantastic idea!](https://tinyurl.com/y5s43jtt) | Medium | 📌 BS within BS |
185+
|09| [222. Count Complete Tree Nodes](https://leetcode.com/problems/count-complete-tree-nodes/)| [Python](leetcode.com/python/222_Count_Complete_Tree_Nodes.py)| [Theory](http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/bin-tree.html), [Official Solution](https://leetcode.com/problems/count-complete-tree-nodes/solution/), [Fantastic idea!](https://tinyurl.com/y5s43jtt) | Medium | 📌 BS within BS |
186+
|10| [1231. Divide Chocolate](https://leetcode.com/problems/divide-chocolate/)| [Python](leetcode.com/python/1231_Divide_Chocolate.py)| [Art 1](https://tinyurl.com/sl7w7cb), [Art 2](https://tinyurl.com/vabdbzo), [Art 3](https://tinyurl.com/v4cablt), [Vid 1](https://www.youtube.com/watch?v=vq2OXjXQPYw&feature=emb_title) | Hard | 📌 **Not done. Check again** |
186187

187188

188189
### [Binary Search Tree](https://leetcode.com/explore/learn/card/introduction-to-data-structure-binary-search-tree/)
@@ -233,7 +234,9 @@ I have solved quite a number of problems from several topics. See the below tabl
233234
|03| [642. Design Search Autocomplete System](https://leetcode.com/problems/design-search-autocomplete-system/)| [Python](leetcode.com/python/642_Design_Search_Autocomplete_System.py)| [Article 01](https://leetcode.com/problems/design-search-autocomplete-system/discuss/105386/Python-Clean-Solution-Using-Trie), [Video 01](https://www.youtube.com/watch?v=us0qySiUsGU)| Hard | --- |
234235

235236

236-
### Graphs (BFS, DFS, Dijkstra, Union Find, Kruskal, Prim's, Minimum Spanning Tree, Topological Ordering...etc)
237+
### Graphs
238+
(BFS, DFS, Dijkstra, Union Find, Kruskal, Prim's, Minimum Spanning Tree, Topological Ordering...etc)
239+
237240
| # | Title | Solution | Tutorial | Level | Remarks |
238241
| --- | --- | --- | --- | --- | --- |
239242
|01| [200. Number of Islands](https://leetcode.com/problems/number-of-islands/)| [Python](leetcode.com/python/200_Number_of_Islands.py)|

‎leetcode.com/python/1231_Divide_Chocolate.py

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
class Solution:
2+
3+
4+
# SOlution borrowed from here: https://tinyurl.com/w9wbcyl
5+
def maximizeSweetness(self, sweetness, K):
6+
"""
7+
:type sweetness: List[int]
8+
:type K: int
9+
:rtype: int
10+
"""
11+
"""
12+
The problem asks us to divide the chocolate in a clever way in order to
13+
maximize the sweetness we can get, since our friends are greedy and
14+
always take the sweetest chunks. In essence, it is asking for the
15+
maximum of the minimum sum of continuous subarrays, since we always get
16+
the least sweet piece, which have the least sweet chunks (minimum sum of
17+
continuous subarray) as compared to our friend's, and we want to find
18+
the maximum we can get among all the dividing strategies.
19+
"""
20+
21+
def divide(target):
22+
"""
23+
The function divides the given chocolate into a number of pieces, so
24+
that there must be at least one piece with a total sweetness less
25+
than or equal to the given target
26+
"""
27+
# total sweetness of current piece and the number of pieces
28+
sum_, count = 0, 0
29+
for l in sweetness:
30+
# add the sweet level to the total
31+
sum_ += l
32+
# if the current piece has a total greater than or equal to the
33+
# given target, make a cut
34+
if sum_ >= target:
35+
count += 1
36+
sum_ = 0
37+
return count
38+
39+
# the desired total sweetness must fall in the range from the minimum
40+
# sweetness to the average sweetness of the (K + 1) pieces - if we are
41+
# dumb enough to cut the least sweet chunk as a piece by itself, its
42+
# total sweetness is the sweet level of that single chunk; if we are
43+
# lucky enough that the sweetness is evenly distributed throughout the
44+
# chocolate bar, we can make even cuts so we have the same amount of
45+
# sweetness with our greedy friends. The real life is somewhere in
46+
# between, and we always hope for the best, so we move towards the
47+
# lucky side as much as we can
48+
lo, hi = min(sweetness), sum(sweetness) // (K + 1)
49+
while lo < hi:
50+
# try a number in the middle tentatively
51+
target = (lo + hi + 1) // 2
52+
# if it results in less than K + 1 chunks, some of our friends
53+
# cannot get a piece and may get mad, so we decrease the sweetness
54+
# we get to make our friends happy
55+
if divide(target) < K + 1:
56+
hi = target - 1
57+
# otherwise, we try to increase the sweetness (sneakily) as much as
58+
# we can right before being exposed...
59+
else:
60+
lo = target
61+
# this is the most we can get before being exposed...
62+
return lo
63+
64+
65+
66+
sol = Solution()
67+
sweetness = [1,2,3,4,5,6,7,8,9]
68+
K = 5
69+
out = sol.maximizeSweetness(sweetness, K)
70+
print('Res: ', out)

0 commit comments

Comments
 (0)