<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Gismet_Majidov on Medium]]></title>
        <description><![CDATA[Stories by Gismet_Majidov on Medium]]></description>
        <link>https://medium.com/@gismetmajidov?source=rss-ad3b953ade7a------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*kBHsyQpeARl1CTsOV4SIHA.png</url>
            <title>Stories by Gismet_Majidov on Medium</title>
            <link>https://medium.com/@gismetmajidov?source=rss-ad3b953ade7a------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 03:23:36 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@gismetmajidov/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Test Your Problem-Solving Ability]]></title>
            <link>https://medium.com/puzzle-sphere/test-your-problem-solving-ability-29ac99d1f009?source=rss-ad3b953ade7a------2</link>
            <guid isPermaLink="false">https://medium.com/p/29ac99d1f009</guid>
            <category><![CDATA[proof]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[problem-solving-process]]></category>
            <category><![CDATA[problem-solving-skills]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[Gismet_Majidov]]></dc:creator>
            <pubDate>Thu, 05 Dec 2024 14:19:21 GMT</pubDate>
            <atom:updated>2024-12-06T12:12:46.416Z</atom:updated>
            <content:encoded><![CDATA[<p>See if you can solve this problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*pqkv3wsoBh25wxLR" /><figcaption>Generated With ChatGPT</figcaption></figure><h3>Problem</h3><p>You are given a sequence of numbers. The given sequence contains values in the range [<strong>1, 2n] once </strong>where n is <strong>odd</strong>. In one move, you can pick any two numbers <strong>a</strong> and <strong>b (not necessarily adjacent)</strong>, remove them and add to the sequence<strong> |a — b|. Repeat the moves until a single number remains. <em>Is it possible that you will have an odd number at the end?</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/225/0*gB_Swx9RS1d2_xbV" /><figcaption>Solution is below</figcaption></figure><h3>Solution</h3><p>Let us prove that the last number will be odd.</p><ul><li>What happens when you choose any two numbers <strong>a</strong> and <strong>b</strong>, remove them and add <strong>|a — b|</strong> to the sequence?</li></ul><p>Let us consider the sum of all the elements in the initial sequence and call it <strong>S</strong>.</p><pre>S = the sum of all elements in the initial sequence</pre><p>Now let us go ahead and pick any two numbers <strong>a </strong>and <strong>b</strong> and remove them from the sequence. When a and b are removed, S gets reduced by a + b.</p><blockquote><strong>S = S - a - b</strong></blockquote><p>Now let us add |a — b| to the sequence and see what happens to the sum.</p><ul><li><strong>Case 1: a &gt; b</strong></li></ul><blockquote><strong>S = S - a - b + |a-b| = S - a - b + a - b = S - 2b</strong></blockquote><ul><li>Case 2: a &lt; b</li></ul><blockquote><strong>S = S - a - b + |a-b| = S - a - b + b - a= S - 2a</strong></blockquote><p>We can observe that in each move,<strong> S</strong> <em>decreases</em> either by <strong>2b</strong> or <strong>2a</strong>, both of which are <strong>even</strong> numbers. Initially, <strong>S </strong>is equal to <strong>1 + 2 + … + 2n</strong> <strong>= n(2n + 1)</strong>. This is an <strong>odd</strong> number. Do you see it now ?</p><p>Since in each move, we decrease <strong>S</strong> by an <strong>even</strong> number and <strong>S</strong> is initially and <strong>odd</strong> number, the final number will be odd. <strong>QED</strong>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=29ac99d1f009" width="1" height="1" alt=""><hr><p><a href="https://medium.com/puzzle-sphere/test-your-problem-solving-ability-29ac99d1f009">Test Your Problem-Solving Ability</a> was originally published in <a href="https://medium.com/puzzle-sphere">Puzzle Sphere</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Try This Knights and Knaves Puzzle]]></title>
            <link>https://medium.com/puzzle-sphere/try-this-knights-and-knaves-puzzle-f88797493d5c?source=rss-ad3b953ade7a------2</link>
            <guid isPermaLink="false">https://medium.com/p/f88797493d5c</guid>
            <category><![CDATA[logic-puzzles]]></category>
            <category><![CDATA[critical-thinking]]></category>
            <category><![CDATA[knights-and-knaves]]></category>
            <category><![CDATA[logic]]></category>
            <dc:creator><![CDATA[Gismet_Majidov]]></dc:creator>
            <pubDate>Sun, 22 Sep 2024 12:11:28 GMT</pubDate>
            <atom:updated>2024-09-22T12:11:28.985Z</atom:updated>
            <content:encoded><![CDATA[<p>This knights and knaves puzzle is different than the previous one.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/0*4JRnRcv9aDrwwENB" /><figcaption><strong>Michael Stillwell from Pinterest</strong></figcaption></figure><h3><strong>Puzzle Statement</strong></h3><p>Once a man visited the island of knights and knaves. He found two inhabitants resting under a tree. The man asked one of them — <em>“Is either of you a knight?”. </em><strong>An answerer responded and the man knew the answer to<em> his question.</em></strong></p><p><strong>What is the person to whom the question was addressed</strong> — Is he a knight or a knave? And <strong>what is the other one?</strong> There is enough information to solve this puzzle.</p><blockquote>A knight is one who always tells the truth.</blockquote><blockquote>A knight is one who always lies.</blockquote><blockquote><strong>Please give it a go before you look at the solution below</strong></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/226/0*XlXFYE8RuuEE6wTx" /></figure><h3>Solution ✅</h3><p>Let’s analyze the the cases where the person to whom the question was addressed is a <strong>knight</strong>, meaning the one who always tells the truth. In the following cases, the first one is the one who got asked the question.</p><ul><li><strong>Case 1 =&gt; A knight and a knave</strong></li><li><strong>Case 2 =&gt; A knight and a knight</strong></li></ul><p>In both of these cases, the one who was asked the question is a knight. Since at least one of them is a knight, the man would get “Yes” as the answer as he asked the knight.</p><p>Now let’s look at the cases where the person to whom the question was addressed is a <strong>knave</strong>.</p><ul><li><strong>Case 3=&gt; A knave and a knave</strong></li><li><strong>Case 4=&gt; A knave and a knight</strong></li></ul><p>In case 3, the answer to the question would be “Yes”. Because there is no knight and the man was asking a knave, the answer is “Yes”. Remember a knave always lies.</p><p>In case 4, the answer of the question would be “No”. In this situation, there is a knight and the knave who was asked the question must lie, saying “No” to the question.</p><blockquote><strong>So what is the answer?</strong></blockquote><p>We have 4 cases, but how do we know which one is the actual case. Well, there is enough information in the puzzle statement. The fact that the man knew the answer to his question helps us solve this puzzle. In three of the above cases — case1, case2, case3, the answer was “Yes”. However, in the last case (case 4), the answer is “No”. The three answers of “Yes” do not tell us anything. But the only “No” tells us that the first must be a knave and the second must be a knight. So the one who was asked the question is a knave and the other one is a knight. So we solve this puzzle by exhausting all the possible cases and seeing that the man can only know the answer to his question if the case 4 happens since in all of the other cases, the answer is “Yes”, giving us no information as to who is who.</p><p><strong>I hope you enjoyed this puzzle.</strong> Leave a comment if you encounter this kind of puzzles in real life situations.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f88797493d5c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/puzzle-sphere/try-this-knights-and-knaves-puzzle-f88797493d5c">Try This Knights and Knaves Puzzle🧠🤔</a> was originally published in <a href="https://medium.com/puzzle-sphere">Puzzle Sphere</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[An Intriguing Logic Problem to Stretch Your Brain]]></title>
            <link>https://medium.com/puzzle-sphere/an-intriguing-logic-problem-to-stretch-your-brain-a9f4ae98ec1b?source=rss-ad3b953ade7a------2</link>
            <guid isPermaLink="false">https://medium.com/p/a9f4ae98ec1b</guid>
            <category><![CDATA[logic]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[logic-puzzles]]></category>
            <dc:creator><![CDATA[Gismet_Majidov]]></dc:creator>
            <pubDate>Thu, 19 Sep 2024 07:37:37 GMT</pubDate>
            <atom:updated>2024-09-19T07:37:37.367Z</atom:updated>
            <content:encoded><![CDATA[<p>See if you can solve this logic puzzle. Write the answers in the comments.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cedKNXHVOGRqyAcA-CFVGQ.png" /><figcaption>The problem statement</figcaption></figure><h3>Problem Statement</h3><blockquote>There is a class of <strong>31</strong> students. The students of this class have just taken a math exam. Some of them <strong>passed</strong> the exam with grades<strong> A, B, C</strong> while others <strong>failed</strong> with grade <strong>F</strong>. The number of students <strong>who received grade A</strong> is <strong>more</strong> than the rest of the students <strong>who got B, C, or F</strong>. Among the students who <strong>did not received A</strong>, the number of students who <strong>received B</strong> is <strong>more</strong> than the rest of the students (<strong>those who got C or F</strong>). Among the students who <strong>did not received A and B</strong>, the number of students who<strong> got C</strong> is <strong>more</strong> than the rest of the students (<strong>those who got F</strong>). The <strong>failed</strong> students retake a <strong>makeup</strong> exam. In this exam, those who<strong> passed</strong> are <strong>more</strong> than the<strong> failed</strong> ones.<strong> What is the maximum number of students who failed in this exam?</strong></blockquote><p>✏️Please take your time to figure out the solution. The solution will be revealed below.</p><h3><strong>Solution</strong>✅</h3><p><strong>The answer is 1</strong>. Let’s see how.</p><p>the number of students who received grade A is more than those who received B, C, or F. The number of students who got A can be at least 16. Then the number of students who received B, C, or F is 15. Among those who did not get A, the number of students who got B is more than the rest of students — those who got C or F. the number of students with B can be at least 8. Then the students who received either C or F is 7. Among those who did not get A and B, The number of students who got C is more than those who got F. The number of students with C can be at least 4. So 3 students failed. They retake the exam. Since the number of passed students in this exam is ore than failed ones, at most 1 student can fail. So <strong>the answer is 1.</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a9f4ae98ec1b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/puzzle-sphere/an-intriguing-logic-problem-to-stretch-your-brain-a9f4ae98ec1b">An Intriguing Logic Problem to Stretch Your Brain🧠</a> was originally published in <a href="https://medium.com/puzzle-sphere">Puzzle Sphere</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Try to solve this classic knights and knaves logic puzzle]]></title>
            <link>https://medium.com/puzzle-sphere/try-to-solve-this-classic-knights-and-knaves-logic-puzzle-aecebc098037?source=rss-ad3b953ade7a------2</link>
            <guid isPermaLink="false">https://medium.com/p/aecebc098037</guid>
            <category><![CDATA[critical-thinking]]></category>
            <category><![CDATA[puzzle]]></category>
            <category><![CDATA[logic]]></category>
            <dc:creator><![CDATA[Gismet_Majidov]]></dc:creator>
            <pubDate>Fri, 13 Sep 2024 20:53:21 GMT</pubDate>
            <atom:updated>2024-09-13T20:53:21.741Z</atom:updated>
            <content:encoded><![CDATA[<p>Are you a knight or a knave? come on, don’t lie. Give this puzzle a try.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/0*IUZ0Mxv2lTAU823p" /><figcaption><strong>Michael Stillwell from Pinterest</strong></figcaption></figure><h3>Knight and Knave puzzles</h3><p>There are a vast number of puzzles about an island where only two types of inhabitants live. One type of the inhabitants is called “Knaves” and the other type is called “Knights”. Knaves always lie, on the other hand, Knights always tell the truth. Every inhabitant on this island is either a Knight or a Knave.</p><h3><strong>Puzzle</strong></h3><p>There were three inhabitants — A, B, C, standing together in a garden. A stranger passed by and asked A, “Are you a knight or a knave?” A answered but the answer was inaudible, so the stranger could not understand what he said. Then the stranger asked B, “What did A say?”, B answered “A said he is a knave.” At that moment, C said “Do not believe B, he is lying!”.</p><p>Please find what B and C are.</p><blockquote>Before moving on to look at the solution, please take your time and fire some neurons.</blockquote><h3>Solution</h3><p>Let’s see what is happening. C denied what B said. So they can’t not both be the same type, meaning that B and C can not both be knights nor can they be knaves since their comments are contradictory to each other. So they must be different types. Let’s squeeze some information from B’s comment. B said “A said he is a knave”. Please suppose B is telling the truth, that is, he is a knight. Closely inspect what he said. “A said he is a knave”. Since B is a knight, this statement must be true, meaning that A is a knave. So we come to conclude that A is a knave but wait! is he?. If A is a knave, then then he must lie. A knave can not say he is a knave because he would tell the truth. Then A can not say that he is a knave. Then A must be a knight??. Not really, Since A knight would be lying if he said that he was a knave. Of course, we can not know what A is but one thing we know is that B is lying!. A can not say that he is a knave regardless of whether A is a knight or a knave. So B is a knave. (Our first assumption is wrong! this is sort of the same reasoning by contradiction used in mathematical proofs by contradiction). C says that “Don’t believe B, he is lying”, C is telling the truth, B is actually lying. So C is a knight.</p><p>The answer is B is a knave, C is a knight (and A can not be determined).</p><h3>Comping-up</h3><p>There are a lot of variations of knight and knave puzzles, some really challenging. There are more to come. Keep your mind sharp till then.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=aecebc098037" width="1" height="1" alt=""><hr><p><a href="https://medium.com/puzzle-sphere/try-to-solve-this-classic-knights-and-knaves-logic-puzzle-aecebc098037">Try to solve this classic knights and knaves logic puzzle</a> was originally published in <a href="https://medium.com/puzzle-sphere">Puzzle Sphere</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Can you solve this number theory puzzle?]]></title>
            <link>https://medium.com/puzzle-sphere/can-you-solve-this-number-theory-puzzle-5661e4b6d9e6?source=rss-ad3b953ade7a------2</link>
            <guid isPermaLink="false">https://medium.com/p/5661e4b6d9e6</guid>
            <category><![CDATA[brute-force]]></category>
            <category><![CDATA[puzzle]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[number-theory]]></category>
            <dc:creator><![CDATA[Gismet_Majidov]]></dc:creator>
            <pubDate>Thu, 12 Sep 2024 19:32:11 GMT</pubDate>
            <atom:updated>2024-09-12T19:32:11.683Z</atom:updated>
            <content:encoded><![CDATA[<p>I found a nice problem in one of the math texts book for 5th graders. Give it a try, see if you can solve this interesting problem. It is quite challenging indeed.</p><h3>Problem statement</h3><p>You are given an integer with <strong>3000</strong> digits. The number formed by every two adjacent digits is the <strong>product of 3 distinct prime numbers</strong>. Find the remainder when the given number is divided by 9. A picture is worth a thousand words.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Nu4RqAemQ7DK7JYMXO2hGg.png" /><figcaption>A description of the problem</figcaption></figure><h3>Solution</h3><p>First, let’s think about all the two-digit integers that are product of 3 distinct prime numbers. Let’s try to list them all. I actually also find the following sequence <a href="http://oeis.org/"><strong><em>oeis.org</em></strong></a>. Check out <a href="https://oeis.org/A007304"><strong><em>this link</em></strong></a></p><blockquote><strong><em>2 * 3 * 5 = 30</em></strong></blockquote><blockquote><strong><em>2 * 3 * 7 = 42</em></strong></blockquote><blockquote><strong><em>2 * 3 * 11 = 66</em></strong></blockquote><blockquote><strong><em>2 * 3 * 13 = 78</em></strong></blockquote><blockquote><strong><em>2 * 5 * 7 = 70</em></strong></blockquote><p>Let’s now suppose a1a2 is 30 ( the first product). What can we deduce from this? a2 is 0. So a2a3 would look like 0a3. This can not be a proper integer. So a1a2 can not be 30. We eliminate 30. For this reason, 70 would not work either. Now let’s think a1a2 is 42. We can conclude that a2 is 2. So a2a3 should look like 2a3. However, we do not have any integer starting with 2 in our list above. So this case is not possible. The same would happen if we took 78. a1a2 would be 78 and a2 would be 8, which means a2a3 is like 8a3. We don’t have any integer that starts with 8.</p><p>So we are only left with 66. If a1a2 is 66, then a2 is 6. The integer a2a3 would be like 6a3. We have an integer that starts with 6, which is 66 in our list. So the same reasoning goes on. Now we know that a3a4 would be like 6a4. So all the digits of the given 3000-digit number will be 6. Now it is easy to find the remainder when this integer is divided by 9.</p><p>Let’s remember the divisibility rule of 9.</p><blockquote>If the sum of the digits of the given integer is divisible by 9, then the integer itself is divisible by 9<em>.</em></blockquote><p>We have an integer with all of its digits being 6. Namely, 666666….</p><p>We have 3000 digits of 6. The sum of digits is 18000, which is divisible by 9. So the number itself is divisible by 9. Then, the remainder is 0. The <strong>answer</strong> is 0.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5661e4b6d9e6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/puzzle-sphere/can-you-solve-this-number-theory-puzzle-5661e4b6d9e6">Can you solve this number theory puzzle?</a> was originally published in <a href="https://medium.com/puzzle-sphere">Puzzle Sphere</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode 3266. Final Array State After K Multiplication Operations II-Weekly Contest 412 — Hard]]></title>
            <link>https://medium.com/@gismetmajidov/leetcode-3266-final-array-state-after-k-multiplication-operations-ii-weekly-contest-412-hard-71b1cab8af5e?source=rss-ad3b953ade7a------2</link>
            <guid isPermaLink="false">https://medium.com/p/71b1cab8af5e</guid>
            <category><![CDATA[heap]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[leetcode-hard]]></category>
            <dc:creator><![CDATA[Gismet_Majidov]]></dc:creator>
            <pubDate>Wed, 11 Sep 2024 14:54:32 GMT</pubDate>
            <atom:updated>2024-09-11T14:54:32.049Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode <a href="https://leetcode.com/problems/final-array-state-after-k-multiplication-operations-ii/">3266. Final Array State After K Multiplication Operations II</a>-Weekly Contest 412 — Hard</h3><p>This problem got 1.2 % acceptance rate during the contest and it rose to 3% after the contest. At the time of publishing this post, it was 9.8%. So it seems like a challenging problem. Let’s see if it actually is</p><h3>Problem description</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/739/1*-1VSKCXHIlUuBrzXgBd_FQ.png" /><figcaption>Original problem description</figcaption></figure><p>You are given an <strong>array of integers</strong>, an integer <strong>k</strong>, and an integer <strong>multiplier.</strong></p><p>You will do <strong>k</strong> operations on the array. The following describes what you should do at each operation.</p><ul><li>Choose the minimum value <strong>x</strong> in the array and replace it with x * multiplier. If there are more than one occurrence of the minimum value, choose the one that appears first.</li></ul><p>You have to return the final state of the array after applying <strong>module</strong> 10⁹ + 7 to every value.</p><h3>Solution</h3><p>Before we actually get to the main idea, let’s develop some understanding by walking through an example</p><h4>Walk-through on an example</h4><p>We have the following</p><blockquote>nums = [2,1,3,5,6], k = 5, multiplier = 2</blockquote><ul><li>At operation 1. Choose 1 and multiply it by 2 (multiplier). new array state =&gt; [2, 2, 3, 5, 6]</li><li>At operation 2. Choose 2 at index 0 and multiply it by 2. new array state =&gt; [4, 2, 3, 5, 6]</li><li>At operation 3. Choose 2 and multiply it by 2. new array state =&gt; [4, 4, 3, 5, 6]</li><li>At operation 4. Choose 3 and multiply it by 2. new array state =&gt; [4, 4, 6, 5, 6]</li><li>At operation 5. Choose 4 at index 0 and multiply it by 2. new array state =&gt; [8, 4, 6, 5, 6]</li><li>Apply modulo 10⁹ + 7 to every value. new array state =&gt; [8, 4, 6, 5, 6]</li></ul><p>We have done 5 operation in total and the final array state is [8, 4, 6, 5, 6]</p><p>What do we need to do at each operation? We need to find the minimum value. And then multiply it by the given multiplier and replace the old value. So we need a quick way to find the minimum value ?</p><p>Of course, we can do a linear scan every time but that is costly. You are most likely familiar with min heap data structure (priority queue in C++). We can make use of min heaps to quickly find the minimum value. Okay that’s great. Then let’s push all the values in the initial array to the min heap and find minimum value, remove it from min heap, multiply it by the given multiplier and add it back to the min heap. We should do this k times. Finding the minimum value in a min heap is <strong>O(log n). </strong>We will find the minimum value k times so we end up having a time complexity of <strong>O(k * log n). It seems like promising until you see the problem constraints.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/303/1*RhiSg0aJSF-6BJbbpdnpjg.png" /><figcaption><strong>Problem constraints</strong></figcaption></figure><p>k could be as big as <strong>10⁹</strong>, which renders our mere <strong>O(k * log n)</strong> solution too slow. Therefore, simulating the entire process is not possible.</p><h4>A refinement of simulation idea</h4><p>Well, our previous idea of simulation the entire k operations awfully fails to yield a fast solution. However, let’s not just be too quick to throw our idea in dustbin. Maybe we can refine this idea to be faster. Let’s take another example.</p><blockquote>nums = [2, 5, 8, 9, 11, 50] k = 21 and multiplier = 2</blockquote><p>At operation 14, we have [32, 40, 32, 36, 44, 50]. The minimum is 32 at index 0. By multiplying it by 2, we obtain [64, 40, 32, 36, 44, 50]. After operation 14, we stop. But why? We have 21 operations to do, why stop after 14. The reason is because a pattern emerged. Let’s sort the current state of the array. [32, 36, 40, 44, 50, 64]. Now it is easy to find the minimum value. Let’s proceed doing the operation.</p><ul><li>At operation 15, the array becomes [64, 36, 40, 44, 50, 64]</li><li>At operation 16, the array becomes [65, 72, 40, 44, 50, 64]</li><li>At operation 17, the array becomes [65, 72, 80, 44, 50, 64]</li><li>At operation 18, the array becomes [65, 72, 80, 88, 50, 64]</li><li>At operation 19, the array becomes [65, 72, 80, 88, 100, 64]</li><li>At operation 20, the array becomes [65, 72, 80, 88, 100, 128]</li></ul><p>Did you notice something while going from operation 15 to 20. Every time we multiply the minimum value by the given multiplier, the next value becomes the next minimum value. But wait, isn’t it because the array was sorted? Not really, Look at this array nums = [2, 7, 9] and multiplier = 2. The minimum value is 2 and multiply it by 2, you get 4. Now array becomes [4, 7, 9]. This does not make the next value (7) the next minimum. The next minimum is 4. The actual reason why the above happens is because each value is within a multiple of the given multiplier. What do I mean? The array we got after operation 14 is [32, 36, 40, 44, 50, 64] (in sorted order). For example, 32 is within a multiple of 2 away from 36. Let me clarify my point further. For example, in our example array, [2, 7, 9], when we multiply the minimum value 2 by 2, we got 4 and 4 is still the minimum value. But our array after operation 14, [32, 36, 40, 44, 50, 64], has kind of a special property. No element in the array remains the minimum value after multiplied by the given multiplier, which means when you multiply the minimum value at index i, the next minimum value is bound to be at index (i + 1). And when you multiply the minimum value at index (i + 1), the next minimum must be at index (i + 2). This goes on till the end of the array. At the operation 20, we reach the end of the array. Now we have [65, 72, 80, 88, 100, 128]. It is sorted again and has the same property. If we have to do more operations, when a value gets multiplied, the next value immediately after it will the next minimum. Let’s say we have a <strong>sorted</strong> array with such property <strong>[a1, a2, a3, a4] and k = 9 and multiplier = m.</strong> The following happens</p><ul><li>[a1 * m, a2, a3, a4]</li><li>[a1 * m, a2 * m, a3, a4]</li><li>[a1 * m, a2 * m, a3 * m, a4]</li><li>[a1 * m, a2 * m, a3 * m, a4 * m] ( a new cycle of operations begin again)</li><li>[a1 * m * m, a2 * m, a3 * m, a4 * m]</li><li>[a1 * m * m, a2 * m * m, a3 * m, a4 * m]</li><li>[a1 * m * m, a2 * m * m, a3 * m * m, a4 * m]</li><li>[a1 * m * m, a2 * m * m, a3 * m * m, a4 * m * m] ( a new cycle of operations begin again)</li><li>[a1 * m * m * m, a2 * m * m, a3 * m * m, a4 * m * m]</li></ul><p>After 9 operations, we end up with [ a1 * m³, a2 * m², a3 * m², a4 * m²]</p><p>The 9 operations have been distributed among the 4 values evenly. 9 operations each value gets multiplied by <strong>m</strong> 2 times and there is a reminder of 1, which goes to first value.</p><p>So we actually need to simulate until we get an array with the property above. Please try to understand the explanation of the property above. How do we get it? We simulate until the minimum value * multiplier &gt; the maximum value in the initial array. After that we can distribute the remain number of k operations on each value.</p><h3><strong>Edge cases</strong></h3><p>When the multiplier is 1, the array element never changes. So we return the nums array as it is.</p><p>When there is a single element in the array, we do all the operations on this element. We handle these two cases separately.</p><h3>Time complexity</h3><p>The smallest value could 1 and the largest value could be 10⁹ and the smallest multiplier could be 2 (not considering the edge case when it is 1). It would only take log2(10⁹) operations for the smallest value to become greater than the largest value. So we have <strong>O(N * log(N) + log(N) * log(K))</strong>. In the strictest sense, it is<strong> O(N * log(N)</strong>.</p><h3>Code</h3><pre>#define vv std::vector<br>#define pp std::pair&lt;long long, int&gt;<br>#define LOG(x) std::cout &lt;&lt; #x &lt;&lt; &quot; : &quot; &lt;&lt; x &lt;&lt; &#39;\n&#39;;<br>const int MOD = int(1e9) + 7;<br><br><br>class Solution {<br>public:<br>    vector&lt;int&gt; getFinalState(vector&lt;int&gt;&amp; nums, int k, int m) {<br><br>        if(m == 1)<br>        {<br>            return nums;<br>        }<br><br><br>        int maxNum = *(std::max_element(nums.begin(), nums.end()));<br>        int n = nums.size();<br><br>        if(n == 1)<br>        {<br>            nums[0] = ((long long)nums[0] * binpow(m, k)) % MOD;<br>            return nums;<br>        }<br><br>        std::priority_queue&lt;pp, vv&lt;pp&gt;, std::greater&lt;pp&gt;&gt; pq;<br><br>        for(int i = 0; i &lt; n; i++)<br>        {<br>            pq.push({nums[i], i});<br>        }<br><br>        while(k &gt; 0 &amp;&amp; pq.top().first &lt;= maxNum)<br>        {<br>            k--;<br>            auto num = pq.top(); pq.pop();<br>            num.first *= m;<br>            pq.push(num); <br>        }<br>        <br>         <br>        int power = k / n;<br>        int r = k % n;<br><br>        int x = binpow(m, power);<br>        int y = binpow(m, power + 1);<br><br>        while(!pq.empty())<br>        {<br>            auto top = pq.top();<br>            int finalValue = ((long long)top.first % MOD * (r &gt; 0 ? y : x)) % MOD;<br>            nums[top.second] = finalValue;<br>            pq.pop();<br>            r--;<br>        }<br><br>        return nums;<br>    }<br><br>private:<br>    int binpow(long long a, long long b)<br>    {<br>        if(a == 0) return 0;<br>        if(b == 0) return 1;<br>        long long res = 1LL;<br>        while(b)<br>        {<br>            if(b&amp;1)<br>                res = (res * a) % MOD;<br>            a = (a * a) % MOD;<br>            b &gt;&gt;= 1;<br>        }<br><br>        return res;<br>    }<br><br>};</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=71b1cab8af5e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Binary Search: Part 5 — Solving LeetCode 2187. Minimum Time to Complete Trips]]></title>
            <link>https://medium.com/@gismetmajidov/binary-search-part-5-solving-leetcode-2187-minimum-time-to-complete-trips-d2c0f57c396f?source=rss-ad3b953ade7a------2</link>
            <guid isPermaLink="false">https://medium.com/p/d2c0f57c396f</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[binary-search]]></category>
            <category><![CDATA[interview-questions]]></category>
            <dc:creator><![CDATA[Gismet_Majidov]]></dc:creator>
            <pubDate>Sat, 07 Sep 2024 22:30:03 GMT</pubDate>
            <atom:updated>2024-09-07T22:30:03.373Z</atom:updated>
            <content:encoded><![CDATA[<h3>Binary Search: Part 5 — Solving LeetCode <a href="https://leetcode.com/problems/minimum-time-to-complete-trips/">2187. Minimum Time to Complete Trips</a></h3><p>Let’s solve LeetCode <a href="https://leetcode.com/problems/minimum-time-to-complete-trips/">2187. Minimum Time to Complete Trips</a> in this article.</p><h3>Problem Description</h3><p>There are buses. Each bus can complete one trip in a certain amount of time. This fact is given as an array of integers <strong>time. </strong>Buses can make <strong>multiple</strong> trips <strong>successively</strong>. Immediately one after another. Furthermore, each bus operates <strong>independently</strong>. You are given <strong>totalTrips</strong> — the number of trips all buses should make <strong>in total.</strong> We have to find the minimum time for all buses to complete <strong>at least</strong> <strong>totalTrips</strong> trips.</p><p>Let’s have a look at some examples.</p><h3>Examples</h3><blockquote>time = [1, 2, 3], totalTrips = 5</blockquote><p>We have three buses. The first bus takes 1 unit of time to complete a trip, the second bus takes 2 and the third bus takes 3 units of time to complete one trip. We have to make 5 trips <strong>in total. At time 1 only first bus can complete one trip. We have only 1 trip, not enough . At time 2, the first bus completes 2 trips while the second bus can make 1 trip. We now have 3 trips, again not enough. At time 3, The first bus can make 3 trips, the second one can make 1 trip and the third bus can make 1 trip, this adds up to 5 trips in total, exactly what we want. So the answer for this test case is 3.</strong></p><p>Let’s look at another example.</p><blockquote><strong>times = [1, 3, 4, 2], totalTrips = 7</strong></blockquote><p>We have to make 7 trips in total. This time, let’s start with some larger value. Say, at time 6, The first bus makes 6 trips, the second bus makes 2, the third bus makes 1, the last bus makes 3 trips, in total we have 12 trips, more than enough. So with 6 units of time, we can fulfill the requirement of at least 7 trips easily. <strong>Now the critical question, how about at time 8? Can we again fulfill the requirement of at least 7 trips? <em>If we could do it with 6 units of time, we can also do it more than 6 units of time. Anything more than 6 also works. So this seems like feasible solution. </em></strong>We want to minimize our answer, let’s get down. Since 6 is feasible, now let’s check smaller values to see if there are any smaller values that are feasible? What if we check 4 now? The first bus makes 4 trips, the second bus makes 1 trip, the third bus makes 1 trip, and the fourth bus makes 2 trips. This gives us a total of 8 trips. 8 meets the requirement. Let’s go down to even smaller values. Let’s now check 3. The firs bus makes 3 trips, the second one makes 1 trip, the third one can not make any trips, the last one can make 1 trip. This results in a total of 5 trips. 5 is less than 7, hence does not meet the requirement. 3 is within the <strong>infeasible</strong> search space. If we can’t make at least 7 trips at time 3, we can not certainly make at least 7 trips at a time less than 3. So we honed in on 4. 4 is the minimal.</p><p>How can we bound the answer from above? For example, we have to make 4 trips and the fastest bus takes 2 units of time to complete one trip. Then we need at most 8 units of time. At time 8, the fastest bus will complete the required 4 trips. So the <strong>upper bound</strong> is <strong>the minimum time taken to complete a trip * the number of required trips.</strong> How about the lower bound. Well, no need to come devise something. Just take 1. Now the answer is within the range <strong>[1, upper_bound]</strong>. We can search over than range with binary search.</p><h3>Check function</h3><p>We need to check if for a certain amount of time, we can make at least the required number of trips. That is very easy. We can effortlessly calculate how many trips a bus can make within a certain time. Then we do it for each bus. If at the end, we mange to make at least the required number of trips, then it if fine. This is all. A simple greedy idea.</p><h3>Code</h3><pre>class Solution<br>{<br>    public:<br>        long long minimumTime(vector&lt;int&gt; &amp;time, int totalTrips)<br>        {<br><br>            long long  minElement= *(std::min_element(time.begin(), time.end()));<br>            long long l = 1;<br>            long long r = totalTrips * minElement;<br><br>            while (l &lt; r)<br>            {<br>                long long m = l + (r - l) / 2;<br><br>                if (trips(m, time) &gt;= totalTrips)<br>                    r = m;<br>                else<br>                    l = m + 1;<br>            }<br><br>            return l;<br>        }<br>    private:<br>        long long trips(long long t, std::vector&lt;int&gt; &amp;times)<br>        {<br>            long long trips = 0;<br>            for (int i: times)<br>            {<br>                trips += t / i;<br>            }<br>            return trips;<br>        }<br>};</pre><p>There are tons of problems like this out there on the web. Search and explore them. You can find many more interesting problems which can be solved with binary search.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d2c0f57c396f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Codeforces — D. Quantity of Strings, Rating 1600]]></title>
            <link>https://medium.com/@gismetmajidov/codeforces-d-quantity-of-strings-rating-1600-edde57088d55?source=rss-ad3b953ade7a------2</link>
            <guid isPermaLink="false">https://medium.com/p/edde57088d55</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[combinatorics]]></category>
            <category><![CDATA[codeforces]]></category>
            <dc:creator><![CDATA[Gismet_Majidov]]></dc:creator>
            <pubDate>Fri, 06 Sep 2024 20:53:02 GMT</pubDate>
            <atom:updated>2024-09-06T20:53:02.370Z</atom:updated>
            <content:encoded><![CDATA[<h3>Codeforces — D. Quantity of Strings, Rating 1600</h3><p>This is such a nice problem where you can use graphs to model the problem.</p><h3>Problem description</h3><p>(I will keep the description short). There is a string with the length of exactly n, based on the alphabet of size m. Any of its substrings with length equal to k is a palindrome. Your task is to find the number of such strings.</p><p>The answer might be too big, so find the answer modulo 10⁹ + 7. A palindrome is a string that it can be read the same way in either direction. For example, “abba” , “bccdccb”, “racecar”</p><p><strong>1 ≤ n, m, k ≤ 2000</strong></p><h3><strong>Solution</strong></h3><p>Let’s first resolve cases where k is equal to 1 or k &gt; n.</p><p>When k is equal to 1, any substring of length 1 is a palindrome. For example, any substring of length 1 of the string “abcdfeg” is a palindrome. We can choose any element of the alphabet for each element of the string. The string is of length n and for each element of the string, there are m elements of the alphabet to choose from. So the answer is m^n. (the nth power of m). As absurd as it might seem, when k &gt; n, there are also m^n such strings. Since there is not any substring with length k in this case, all the strings are valid.</p><p>Now let’s get to the cases when k is not 1 and k ≤ n.</p><p>Look at the picture below. Suppose you have a string of length 8 and k is 4.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nP3Iz1ZyCp6mHYwVRve58w.png" /><figcaption>a string of length 8 and k is 4</figcaption></figure><p>You can observe one insight. The relationship between the elements of the string. In the above picture, a substring of length 4 is represented. Since the substring must be a palindrome, the element at index 0 is the same as the element at index 3 and the element at index 1 is the same as the element at index 2. We can draw this relationship arrows for each substring of length 4. It would look like the following. It looks a little messy.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1016/1*48t5FFCtlonAOSmoPJCVeQ.png" /><figcaption>complete relationship arrows</figcaption></figure><p>Let’s now closely look into the different possibilities. There are two possibilities based on the parity of k.</p><p>Case 1: When k is odd</p><p>Arrows (or just lines) that connects the same elements of the string. Let’s call this element unknown x out of the alphabet. Follow the lines and fill in the same elements. After doing this, we get the string the first string in the picture below. Now do this for the empty elements, follow their lines and fill in a different element of the alphabet.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aYqjY7lrEbixj_lBig8RKw.png" /><figcaption>The relation graph when k is odd</figcaption></figure><p>As you can see, The resulting string will be of the form “xyxyxyxy…”. Now we have to only choose elements for ‘x’ and ‘y’ from the alphabet. There are m ways to choose for ‘x’ and m ways to choose for ‘y’, a total of m². So we have m² strings of the form “xyxyxyx…” based on the alphabet of size m.</p><p>Case 2: When k is even</p><p>Let’s repeat the same process for when k is even.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PQ4bTOXhHSTEfLmoYqLdCQ.png" /><figcaption>The relation graph when k is even</figcaption></figure><p>We can see the resulting string will be of the form “xxxxx…”, or in other words, all of the n elements of the string will be the same. There are exactly m such strings where all the elements are the same.</p><p>So this completes all of the possibilities.</p><h3>Code</h3><pre>#include &lt;iostream&gt;<br><br>const int MOD = int(1e9) + 7;<br><br>int binpow(long long a, long long b)<br>{<br>    long long res = 1;<br>    while(b)<br>    {<br>        if(b&amp;1)<br>            res = (res * a) % MOD;<br>        a = (a * a) % MOD;<br>        b &gt;&gt;= 1;<br>    }<br>    <br>    return (int)res;<br>}<br><br><br><br><br>int main()<br>{<br>    int n, m, k;<br>    std::cin &gt;&gt; n &gt;&gt; m &gt;&gt; k;<br>    if(k == 1 || k &gt; n)<br>        std::cout &lt;&lt; binpow(m, n);<br>    else if(k == n)<br>    {<br>        std::cout &lt;&lt; binpow(m, (n+1)/2);<br>    } else <br>    {<br>        if(k&amp;1) std::cout &lt;&lt; m * m;<br>        else std::cout &lt;&lt; m;<br>    }<br>    <br>    return 0;<br>}</pre><p>We need binary exponentiation to calculate (m^n ) % (10⁹ + 7) — the n-th power of m modulo 10⁹ + 7. I will cover binary exponentiation in one of my articles along with a few problems.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=edde57088d55" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Binary search: Part 4 — Solving LeetCode 1870. Minimum Speed to Arrive on Time]]></title>
            <link>https://medium.com/@gismetmajidov/binary-search-part-4-solving-leetcode-1870-minimum-speed-to-arrive-on-time-0a75b4548f9f?source=rss-ad3b953ade7a------2</link>
            <guid isPermaLink="false">https://medium.com/p/0a75b4548f9f</guid>
            <category><![CDATA[leetcod]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[binary-search]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Gismet_Majidov]]></dc:creator>
            <pubDate>Thu, 05 Sep 2024 19:41:39 GMT</pubDate>
            <atom:updated>2024-09-05T19:42:02.711Z</atom:updated>
            <content:encoded><![CDATA[<h3>Binary search: Part 4 — Solving LeetCode <a href="https://leetcode.com/problems/minimum-speed-to-arrive-on-time/">1870. Minimum Speed to Arrive on Time</a></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YgFGxnQc45hVYZRReATbqw.png" /></figure><p>We continue our series of Binary search. In this article, we will solve another nice LeetCode problem similar to the problems in the preceding articles.</p><h3>Problem description</h3><p>You are going to the office and you reach the office in <strong>hour</strong> hours.<strong> hour</strong> is a floating-point number. To commute to the office, you have to take <strong>n</strong> train rides. Each train ride has a distance.</p><p>Each train only <strong>departs at an integer hour.</strong> For example, if the first train ride took 1.2 hours, we have to wait for the <strong>hour 2</strong> in order to take the second train ride.</p><p>We are required to find the <strong>minimum positive integer speed</strong> that all the trains must trail at so that you can reach the office within <strong>hour</strong> hours. The answer is <strong>-1</strong> if it is <strong>impossible</strong>.</p><p>Answer will <strong>not exceed 10⁷</strong> and <strong>hour</strong> will have two digits after the decimal point (for example 3.23).</p><h3><strong>Handling the impossible case</strong></h3><p>In the problem description, it says it is possible that for some test cases, it is impossible to reach the office on time. So we have to return -1 as the answer. Let’s get rid of impossible test cases.</p><p>Take a look at the following test case. <strong>What do you think? Is it possible?</strong></p><blockquote>dist = [1, 3, 2], hour = 1.9</blockquote><p>dist[0] is the distance of the first train ride and so on. <strong>At what speed should we travel so that we can reach the office on time? The fastest speed we can travel at is such that the first n-1 rides takes 1 hour and the last ride takes dist[n-1]/speed.</strong></p><p>For our example, at best our first two rides will take 2 hours. So we already exceeded the give hour. It is not possible to reach the office on time. If we go really “fast”, we will finish the first ride in some hours less than 1 (or say in 1 hour). As the problem description stated, we have to wait till an integer hour so that we can take the next train ride. So at best, any train ride will take 1 hour even if we finish it in less than 1 hour. Note that for the last ride, it will take as much time as it actually takes since there is no train ride after the last ride. For example, if the speed is 5, the first ride would take 1/5 = 0.2 hours. But we have to wait till hour 1. At hour 1, we take the second ride. The second ride takes 3/5 = 0.6 hours. Again we have to wait till hour 2 to take the third ride. At hour 2, which exceeds the given 1.9 hours, we take the third ride. The third ride takes 1/2 = 0.5 hours. Since there is no ride coming up, it takes a total of 2.5 hours to reach office if we go at a speed of 5. Hence, it is impossible. You might wonder how about going even faster? well, it does not really make a difference after a certain speed. If we went at a speed of 10, the first two rides would still take 2 hours. An the last one would take 1/10 = 0.1 hours. This adds up to 2.1 hours, still more than 1.9.</p><blockquote>The fastest we can reach the office is when the n-1 rides takes 1 hours and the last one takes its distance divided by speed. In total it would be n-1 + dist[n-1]/speed.</blockquote><p><strong>How should we choose the speed then to make sure n-1 + dist[n-1]/speed is the smallest?</strong> Well the problem says that the answer will not be more than 10⁷. So I actually chose 10⁷. You can choose something larger such as 10⁹, but 10⁷ is actually enough. I first thought that I could choose the distance of the longest train ride as the speed. For example, look at the following test case</p><p>dist = [2, 3, 2], hour = 2.01. If I choose 3 as the speed (the longest train ride). Then the first two rides would take 2 hours. And the last ride would take 2/3, roughly 0.666. So a total of 2.666 hours. More than 2.01. It seems like it is impossible but nor really. We can increase the speed. In fact, increasing the speed will not change the whole number part, meaning the increased speed will only decrease the fraction part of the 2.666. When the speed gets increased, we will get something 2.xxx, which will be less than 2.666. For example in this case, we can choose 300 instead of 3 as the speed. Then we would get 2.00666 hours, which is less than 2.01. In short, we have to choose such speed that it takes into account that there might be <strong>two digits after the decimal point. </strong>You can choose the longet ride * 100 to take into account the two digits after decimal point. For convenience I chose 10⁷.</p><p>So when n-1 + dist[n-1]/10⁷ is greater than the given hours, it is not possible. So return -1. We are done with the impossible case.</p><h3>Solving the real deal.</h3><p>Let’s speed up.</p><p><strong>What’s the minimum speed we can travel at? It is 1. How about the maximum speed? We chose this as 10⁷. Our answer is somewhere in this range.</strong></p><p>So again we have a range. Let’s see if we can observe the <strong>feasible-infeasible pattern </strong>here. If we go at a speed of <strong>v </strong>and can not reach the office on time, could we reach the office on time if we went at a speed less than v? The answer is no, we could not. So if v is infeasible, then values less than v is also infeasible. If v is feasible (meaning that we can reach the office on time if we travel at a speed of v), any value of speed greater than v will also be feasible. When v is feasible, we will try to minimize v.</p><h3>Code</h3><pre>class Solution {<br>public:<br>    int minSpeedOnTime(vector&lt;int&gt;&amp; dist, double hour) {<br><br>        int l = 1;<br>        int r = int(1e7);<br><br>        double fastest = int(dist.size() - 1) + (double) dist.back() / r;<br><br>        if(fastest &gt; hour) return -1;<br><br>        while(l &lt; r)<br>        {<br>            int mid = l + (r - l)/2;<br>            if(check(dist, mid, hour)) // possible the reach, look for smaller values of speed<br>                r = mid;<br>            else <br>                l = mid + 1;<br>        }<br><br>        return l;<br>    }<br>private:<br>    bool check(vector&lt;int&gt;&amp; dist, int v, double hour)<br>    {    <br>        double h = 0;<br>        for(int i = 0; i &lt; (int)dist.size() - 1; i++)<br>        {<br>            h += (dist[i] + v - 1) / v;<br>        }<br><br>        h += dist.back() / (double)v;<br><br>        return h &lt;= hour;<br>    }<br>};</pre><p>I hope this was helpful. Try to understand the solution and apply this idea to similar problems.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=0a75b4548f9f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Binary search: Part 3— (continued) Pattern to solve LeetCode875. Koko Eating Bananas]]></title>
            <link>https://medium.com/@gismetmajidov/binary-search-part-3-continued-pattern-to-solve-leetcode875-koko-eating-bananas-413acd49ce33?source=rss-ad3b953ade7a------2</link>
            <guid isPermaLink="false">https://medium.com/p/413acd49ce33</guid>
            <category><![CDATA[binary-search]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Gismet_Majidov]]></dc:creator>
            <pubDate>Wed, 04 Sep 2024 21:07:55 GMT</pubDate>
            <atom:updated>2024-09-04T21:07:55.677Z</atom:updated>
            <content:encoded><![CDATA[<p>In this part, we will continue practicing the binary search pattern we introduced in part 2.</p><h3>Problem</h3><p><strong>Koko</strong> (the monkey perhaps) loves eating bananas. There are some piles of bananas with each pile having positive number of bananas. The guards have gone and will be back in <strong>h</strong> hours.</p><p>Koko can decide <strong>k </strong>—<em> the number of bananas she can eat per hour</em>. Each hour she chooses some pile of bananas and eats <strong>k</strong> bananas from the piles. If there are less than <strong>k</strong> bananas in the pile, she eats all the bananas in the pile and will not eat any bananas within that hour.</p><p>Koko likes to eat slowly but she wants to finish all the bananas before the guards come back.</p><p>Help her to decide the minimum integer k such that she can eat all the bananas within <strong>h </strong>hours.</p><h3>Exploring the problem</h3><h4>Example</h4><p>Let’s first take a look at an example. Consider the following input.</p><blockquote><strong>piles = [3, 6, 7, 11], h = 8</strong></blockquote><p>We have four piles and 8 hours to finish all the bananas. <strong>How many bananas per hour Koko should eat at least so that she finishes all the bananas?</strong></p><p>In this case, we have a total of <strong>27</strong> bananas. So Koko should eat at least <strong>ceil(27/8)</strong> bananas. ceil(a/b) is the smallest integer greater than or equal to a/b. So Koko should eat <strong>at least 4 bananas</strong> per hour. <strong>How about at most how many bananas Koko should eat? </strong>Koko should eat <strong>at most 11 bananas</strong>, which is the maximum number of bananas in any pile.</p><p>Now we have a range of<strong> [4, 8] </strong>and our answer lies somewhere within this range. It is time to check feasible-infeasible search space. Let’s say Koko will eat <strong>7</strong> bananas per hour. <strong>Within many hours can Koko finish all the bananas?</strong></p><p>Let’s go over each pile and calculate how many hours it would take Koko to eat it completely.</p><p>The first pile has <strong>3</strong> bananas, which is less than 7. Koko will eat all of them in 1 hour. The second file has 6 bananas, again less than 7. Koko can eat all in 1 hour. The third file has 7 bananas. Koko can eat all of them in 1 hour. The last pile has 11 bananas. Koko can eat all of them in 2 hours (the first 7 in hour 1, and the remaining 4 in hour 2).</p><p>So it takes a total of <strong>4 hours</strong> for Koko to finish all the bananas if she eats 7 bananas per hour. 4 is less than the given time h = 8. So this solution is <strong>possible</strong>. We can verify that if Koko eats more than 7 bananas per hour, she can finish all the bananas within the given time (8 hours). So larger values are also possible. It seems like we are in the <strong>feasible</strong> search space.</p><p><strong>How about k = 5? Can Koko still finish all the bananas within 8 hours?</strong></p><p>It takes Koko exactly 8 hours to finish all the bananas if she eats 5 bananas per hour. So 5 is also within the <strong>feasible search space</strong>. Let’s get even down. Let’s check k = 4. Can Koko still finish all the bananas within 8 hours if she eats 4 bananas per hour? It takes Koko again exactly 8 hours to finish all the bananas when k is 4. So 4 is also <strong>feasible</strong>. Let’s get down. <strong>But wait!! We can’t.</strong> Values less that 4 are outside the range. They will be <strong>impossible</strong>. But let’s just check k = 3 for the sake of completeness.</p><p>It would take Koko <strong>10 hours t</strong>o finish all the bananas if she eats 3 bananas per hours. 10 hours is<strong> not possible</strong> solution because it is more than 8 hours. Any other value less than 3 will <strong>not be possible either</strong>. So 3 and lesser values are within <strong>infeasible search space</strong>. <strong>We do not search there.</strong></p><p><strong>Note: We can also take the lower boundary as 1 since 1 is the minimum number of bananas Koko can eat.</strong></p><p>There you go! We confined our answer within a range<strong> [low, high]. (or [left, right]). </strong>And We also observed feasible-infeasible pattern. Binary search will help us quickly locate our answer within this range.</p><h3><strong>Check function</strong></h3><p>Once again, we need a function to check if Koko can finish all the bananas within<strong> h </strong>hours if she eats <strong>k</strong> bananas per hour. Once again, we can write a greedy algorithm to check this. <strong>For a give number of bananas n, it would take ceil(n/k) hours for Koko to eat them all. Go over each pile and calculate in how many hours Koko can eat all the bananas in this pile. At the end check if the total number of hours exceeds the given hour h. This is the greedy idea.</strong></p><h3>Code</h3><pre>class Solution {<br>public:<br>    int minEatingSpeed(vector&lt;int&gt;&amp; piles, int h) {<br>        long long sum = std::accumulate(piles.begin(), piles.end(), 0LL);<br><br>        long long lowerBound = (int)std::ceil((double)sum / h); // this can also be 1<br>        long long upperBound = *std::max_element(piles.begin(), piles.end());<br><br>        while (lowerBound &lt; upperBound) {<br>            long long mid = lowerBound + (upperBound - lowerBound) / 2;<br><br>            if (canEatAll(piles, h, mid)) { // higher end of range is feasible<br>                upperBound = mid;<br>            } else { // lower end of range is infeasible. Ignore it. <br>                lowerBound = mid + 1; <br>            }<br>        }<br><br>        return lowerBound;<br>    }<br><br>private:<br>    bool canEatAll(vector&lt;int&gt;&amp; piles, int h, long long k) {<br>        long long totalHours = 0;<br><br>        for (int pile : piles) {<br>            totalHours += (pile + k - 1) / k;  // Efficient way to ceil(pile / k)<br>            if (totalHours &gt; h) return false; // Early exit if we exceed the hours<br>        }<br><br>        return totalHours &lt;= h;<br>    }<br>};</pre><p>There we go. We got one problem down. I hope you enjoyed. In the next parts, we will keep solving this kind of problems.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=413acd49ce33" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>