<?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 Abhimanyu Shekhawat on Medium]]></title>
        <description><![CDATA[Stories by Abhimanyu Shekhawat on Medium]]></description>
        <link>https://medium.com/@abhimanyutimes?source=rss-dcb3ce5a8245------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*8lfBLSfxmBN9bXg0dZDjyA.jpeg</url>
            <title>Stories by Abhimanyu Shekhawat on Medium</title>
            <link>https://medium.com/@abhimanyutimes?source=rss-dcb3ce5a8245------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 15:36:34 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@abhimanyutimes/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[What is SGID in Linux?]]></title>
            <link>https://medium.com/codestories/what-is-sgid-in-linux-cb98d49a309f?source=rss-dcb3ce5a8245------2</link>
            <guid isPermaLink="false">https://medium.com/p/cb98d49a309f</guid>
            <category><![CDATA[linux-file-permission]]></category>
            <category><![CDATA[command-line]]></category>
            <category><![CDATA[linux]]></category>
            <category><![CDATA[security]]></category>
            <dc:creator><![CDATA[Abhimanyu Shekhawat]]></dc:creator>
            <pubDate>Fri, 26 Nov 2021 13:10:13 GMT</pubDate>
            <atom:updated>2021-11-26T13:10:13.811Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6QQFeNMi419rlFrUTbm7sw.jpeg" /></figure><p>A few weeks ago, I stumbled upon an interesting problem.<br>In Linux, if you check the file permissions you will notice the name of the file owner along with the group which owns the file.</p><p>Note that, It is <strong>not</strong> necessary for the owner to be a part of the group but usually that is the case.</p><h3><strong>Imagine this scenario:</strong></h3><blockquote>There are 3 processes operating in a system:</blockquote><blockquote><strong><em>P1:</em></strong><em> </em>Runs as root</blockquote><blockquote><strong><em>P2</em></strong><em>:</em> Creates the directories during the install.</blockquote><blockquote><strong><em>P3</em></strong><em>:</em> It access files created by P1.</blockquote><p>Further, P2 &amp; P3 are the part of the same group, say <em>user_grp</em> and both run as owner <em>user</em>.<br>Now consider a directory which is created by our installer process P2 and its permission looks like this:</p><pre>drwxr-x---  5 user user_grp  4096 Jul 31 19:56 docs</pre><p>P1 gets into the directory and wants to create a file called <strong><em>readme.txt</em></strong><em> </em>for process P3 to read.<br>Please note that there is an additional constraint here, the read, write &amp; execute access for OTHERS is prohibited.<br>Nevertheless, P1 goes ahead and creates the file whose permission looks like this:</p><pre>-rwxr-----  1 root root  4096 Jul 31 19:56 readme.txt</pre><h3><strong><em>Can you spot the problem here?</em></strong></h3><p>After carefully examining the situation, it is not difficult to judge that Process P3 will fail in reading the file <em>readme.txt</em> because it is neither the owner of file <em>readme.txt</em> nor part of the same group.</p><p>There are a lot of ways one can go about solving this access limitation. For example, you can just issue <em>chgrp</em> for the file to change its group to <em>user_grp</em> so that process P3 can access, as it will then belong to the same group. But if there are a lot of files like this in the docs directory and you want P3 to read all of them, rather than firing <em>chgrp</em> for each file, you can opt for a more elegant approach.</p><p>Let’s issue this command on <em>docs </em>directory to set <em>GID bit</em>, we will come back to what it actually means in a moment.</p><pre>$ chmod g+s docs</pre><p>Look at the file permission of the <strong><em>docs</em></strong> directory:</p><pre>drwxr-s---  5 user user_grp  4096 Jul 31 19:56 docs</pre><p>Notice there is a <strong><em>‘s’</em></strong> in place of <strong><em>‘x’</em></strong> in the directory permissions. Now let’s allow process P1 to create a file <strong>readme2.txt</strong> in the docs directory.</p><pre>-rwxr-----  1 root user_grp  4096 Jul 31 19:56 readme2.txt</pre><blockquote>This is the magic of SGID!</blockquote><p>When you set the SGID on a directory, all the files and directories inside it will inherit the parent directory’s group.</p><p>So even though <strong><em>root</em></strong><em> </em>is creating the file <strong><em>readme2.txt</em></strong> inside <strong><em>docs</em></strong>, the process P3 can easily read it because the file now has the same group as process P3, i.e. <strong>user_grp</strong> instead of <strong>root</strong>. Hence, SGID bit can be very useful for dealing with situations like the one above.</p><blockquote><strong>Linux holds deeper truths, we just have to MAN [1] up to get there!</strong></blockquote><h3>Notes</h3><p>[1] I am not trying to label courage as a masculine trait. It is just that Linux manual is called MAN pages. So a <em>puny</em> pun 😛</p><blockquote><em>If you liked this post, you can find more by:</em></blockquote><blockquote><em>Following me on </em><strong><em>Twitter</em></strong><em>: </em><a href="https://twitter.com/abshekha"><em>@abshekha</em></a><em> [Super active here!]</em></blockquote><blockquote><em>Connecting on </em><strong><em>LinkedIn</em></strong><em>: </em><a href="https://www.linkedin.com/in/abhimanyubitsgoa/"><em>abhimanyubitsgoa</em></a></blockquote><p>Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cb98d49a309f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codestories/what-is-sgid-in-linux-cb98d49a309f">What is SGID in Linux?</a> was originally published in <a href="https://medium.com/codestories">Code Stories</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A visual guide to 0–1 BFS]]></title>
            <link>https://medium.com/codestories/a-visual-guide-to-0-1-bfs-6f71b64d9a98?source=rss-dcb3ce5a8245------2</link>
            <guid isPermaLink="false">https://medium.com/p/6f71b64d9a98</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[graph-theory]]></category>
            <dc:creator><![CDATA[Abhimanyu Shekhawat]]></dc:creator>
            <pubDate>Sat, 26 Dec 2020 17:08:58 GMT</pubDate>
            <atom:updated>2020-12-26T17:08:58.245Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Z5ikGW71jo3oBXvE3JzzwQ.png" /><figcaption>Illustrated guide to an interesting Shortest Path Algorithm</figcaption></figure><p>Novel problems require tailored solutions. Sometimes, taking a detour and a fresh look at the problem can significantly reduce its complexity. Today we’ll talk about one such technique called <strong><em>0–1 </em>B</strong>readth <strong>F</strong>irst <strong>S</strong>earch.</p><blockquote>Welcome! To the brand new article of <a href="https://medium.com/codestories/code-stories-an-introduction-d8c100aa562a">Code Stories</a> where we solve interesting problems using the fundamentals of Computer Science. 🚀</blockquote><p>Just like our last post regarding <a href="https://medium.com/codestories/division-dynamic-programming-88b6b9d33b90">Dynamic Programming</a>, we’ll first understand the problem statement. After that, we’ll start exploring solution approaches and gradually develop the intuition for <strong>0–1 BFS</strong>. Following that, we will code the entire solution. 🎉</p><blockquote>This article assumes that you have a <em>basic</em> understanding of graphs and how they are traversed.</blockquote><h3>The Problem ❓</h3><p><em>Captain </em><strong><em>Dlon Husk</em></strong><em> has finally embarked on an adventure to discover new worlds beyond his own. He is using the latest </em><strong><em>SpaceY</em></strong><em> Shuttle for this adventure. 🚀</em></p><p><em>After a few wormhole jumps he enters into a Space-Time Matrix of </em><strong><em>NxM </em></strong><em>dimensions</em><strong><em>(1 ≤ N, M ≤ 2000)</em></strong><em>. Since it’s a 2-D matrix his Shuttle too can just move in 4 directions </em><strong><em>Top, Bottom, Left and Right.</em></strong></p><p><em>He finds out that this part of the universe is pretty </em><strong><em>strange</em></strong><em>, as certain cells of the Matrix have the influence of </em><strong><em>Dormammu</em></strong><em>, the destroyer of the worlds. Landing on one of these would mean instant death. Luckily he is currently on a Martian cell </em><em>[R,C]. Dlon likes Martian cells as they give him faith.</em></p><p><em>But this is not all, he discovers that the space-time jumps have damaged the thrusters which move the Shuttle Left and Right. So now he can only move Left and Right </em><em>X and </em><em>Y times respectively </em><strong><em>(0 ≤ X, Y≤ 10⁹)</em></strong><em>. Note that there are </em><strong><em>NO</em></strong><em> restrictions on the Up and Down movement.</em></p><p><em>Dlon is already missing his son (The one named after a coupon code) and wants to return home. But he needs faith for the journey back home. </em><strong><em>Your task is to help Dlon determine the number of Martian cells within his reach.</em></strong></p><h3>The Strategy 💡</h3><p>Since this problem involves a lot of visualization, let’s look at the following illustration to understand it better.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3fq1RDCPtar-JaLZmrIdmQ.png" /><figcaption>Captain Dlon’s Dilemma</figcaption></figure><p>So simply put, Starting from the cell situated at [R, C] (R is Row and C is Column) we want to find out how many Martian cells we can potentially reach while avoiding Dormammu cells. (Martians cells are denoted by <strong>.</strong> while the others with <strong>*</strong>for simplicity).</p><p><em>Remember, we can only move Left &amp; Right, </em><em>X &amp; </em><em>Y times.</em></p><blockquote>I will urge you to pause here for 5 minutes and think of how you can approach this problem. This part is very crucial as it will prime your brain to be more receptive to the content ahead</blockquote><p>I hope after thinking for a while, you must have realized the caveat here. If there would have been no restriction on the number of Left and Right moves, we could have made a simple graph traversal (DFS or BFS) to compute all the cells that we could reach.</p><blockquote>But the fact that there are certain moves that are fundamentally more costly than others implores us to have a <em>priority based traversal</em>.</blockquote><p>To put it differently, we understand that there is <em>no point</em> in using a Left or Right move to reach a cell if it could be reached without it. Since those moves are already limited, we may want to trade them with unlimited Up-Down moves, whenever we can.</p><p>Therefore from the source cell, we will like to first traverse to a cell that doesn’t require a Left-Right move. Only when we have exhausted all such cells, we can start exploring cells that require us to spend our limited Left-Right moves.</p><p>The following idea will become clearer as we model this priority based traversal on the lines of an interesting technique.</p><h4>A special kind of BFS</h4><p>Breadth First Search is a type of graph traversal where we visit nodes of a graph in <em>increasing</em> <em>order of their distance from the source</em>. Therefore, in an <em>unweighted </em>graph, the moment we reach a particular node the number of edges from the source to that node is also the <em>shortest distance</em>.</p><p>But this only works when all the edge weights are equal (the graph is <em>unweighted</em>). When we are given a weighted graph we can’t just sum up all the edge lengths to get the shortest path because unlike the previous case, <em>we can in fact use more edges to reach the target node but still end up with a shorter distance</em>. This idea is illustrated below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Qiv_0SOs0lx7FQSEZSWMmw.png" /><figcaption>Shortest paths in unweighted and weighted graphs</figcaption></figure><p>Therefore we seek out Algorithms like <em>Dijkstra</em>, <em>Bellman-Ford</em>, etc for a weighted graph. However if the edge weights are <em>more constrained</em>, say either 0 or 1, we can apply an intelligent technique to solve the shortest path conundrum.</p><p>We can simply opt to segregate the edge weights encountered during the traversal into 2 buckets. Because we know that all the edge in this graph will be either 0 or 1 at each node, we are faced with just 2 kinds of edge weights.</p><p>So to segregate the edges, we can have a <em>Doubly Ended Queue (Deque)</em> to push the edges with 0 weight in the front and those with 1 weight to the back of the Deque.</p><p>Also, we will ensure that for the purpose of a BFS traversal we always pop the front element in the Deque.</p><p>This step is very crucial as it will <em>always </em>ensure that we pick nodes with distance K before touching nodes with distance K+1 in the Deque.</p><p>This leads to a very interesting <em>Queue invariant </em>for our BFS traversal. It is this invariant that makes <strong><em>0–1 BFS</em></strong> so special.</p><blockquote>At any instant, the Deque can only contain nodes having a total distance of K or (K+1)</blockquote><p>Let me explain why this will always hold true. When you are on a node situated at distance K the choices of edge weights are only 0 &amp; 1.<br>Therefore any neighbours you add after traversing those edges can only increase the total distance to K+1 .</p><p>Hence, the nodes in the Deque are <strong><em>always sorted</em></strong> as per their distance from the source node. As long as we keep popping from the front while adding the edges with weight 0 to front &amp; 1 to the back, our <strong><em>Deque Invariant</em></strong> will remain intact. This is the key idea behind <strong><em>0–1 BFS </em></strong>as illustrated below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iZhYbONcpOh69IdawP-zfQ.jpeg" /><figcaption>0–1 BFS in action</figcaption></figure><h4>Applying 0–1 BFS to the problem</h4><p>Let’s now see how the above idea fits into the current problem. <br>As mentioned earlier we charted out with an intention to do a priority-based traversal. We further saw how <strong><em>0–1 BFS</em></strong> always have a preference to lower edge weights ( 0 over 1). It is time to connect the dots now 😛</p><p>Our problem is very similar. Here, too we will prefer the cells which are reachable via an Up-Down move to the cells which require a Left-Right move.<br>Consequently adding the former in the front and the latter at the back.</p><p>Hence our matrix is equivalent to a graph where all the cells situated in the vertical direction of the current cell is exactly like nodes connected with 0 edge weight. <br>While cells in the horizontal direction to the current cell behaves like nodes with 1 edge weight.</p><blockquote><em>You may ask why we need the shortest path algorithm here?</em></blockquote><p>Since 0–1 BFS will reach every node in the graph via a minimum cost path, we too will be able to visit each cell in the matrix optimally.</p><p>So, if it is not possible to visit a cell via the shortest path for the given constraints, we can safely say, the cell is out of our reach.</p><p>Another way to look at it, if we plan to travel to a cell C with a longer path than the shortest path, we might waste our precious Left-Right moves and reduce our reach further. Let’s see this idea in action below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jHkZLzRkOieWIxlHx7dbeg.png" /><figcaption>Application of 0–1 BFS</figcaption></figure><p>We now have a solid understanding of our solution approach. It is time to get Captain Dlon Husk home 🌍</p><h3>The Code 🎉</h3><p><strong><em>Input (1 based indexing)</em></strong></p><pre>4 5  // NxM<br>3 2  // R,C<br>1 2  // X,Y<br>.....<br>.***.<br>...**<br>*....</pre><p><strong><em>Output</em></strong></p><pre>10  //Number of cells reachable</pre><p><strong><em>Code in C++14</em></strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/142d7f8226eb8325b04e5870b228e634/href">https://medium.com/media/142d7f8226eb8325b04e5870b228e634/href</a></iframe><p><strong><em>Congratulations! Captain, you are home 🏡</em></strong></p><blockquote>Want more content like this? <br>Let me know in the comments below.</blockquote><blockquote>You can connect with me on Twitter here:<strong> </strong><a href="https://twitter.com/abshekha"><strong>abshekha</strong></a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6f71b64d9a98" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codestories/a-visual-guide-to-0-1-bfs-6f71b64d9a98">A visual guide to 0–1 BFS</a> was originally published in <a href="https://medium.com/codestories">Code Stories</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Division & Dynamic Programming]]></title>
            <link>https://medium.com/codestories/division-dynamic-programming-88b6b9d33b90?source=rss-dcb3ce5a8245------2</link>
            <guid isPermaLink="false">https://medium.com/p/88b6b9d33b90</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Abhimanyu Shekhawat]]></dc:creator>
            <pubDate>Sun, 06 Dec 2020 14:57:52 GMT</pubDate>
            <atom:updated>2020-12-07T06:00:09.391Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mddf3sCOhomdwZzAsJQdLA.png" /><figcaption><strong>You can only connect the dots by looking backward</strong></figcaption></figure><p>Problems can’t be considered easier or difficult in isolation. <br>It is essential to define the scale at which they need to be solved.<br>Today we will deal with an interesting problem that will reiterate this point.</p><blockquote><strong>Welcome! To the brand new article of </strong><a href="https://medium.com/codestories/code-stories-an-introduction-d8c100aa562a"><strong>Code Stories</strong></a><strong> where each week we solve interesting problems using the fundamentals of Computer Science. 🚀</strong></blockquote><p>We will begin by understanding the problem statement in detail. <br>After that, we will focus on various solution approaches.<br>Finally, we will code the solution. 🎉</p><blockquote>This article assumes that you have a basic understanding of Dynamic Programing. If you are new to the idea, please refer to this <a href="https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/">tutorial</a>.</blockquote><h3>The Problem ❓</h3><p><em>You are given a non-negative integer </em><strong><em>N</em></strong><em>, it has at most </em><strong><em>1000 digits</em></strong><em> without any leading zeroes. Along with an integer </em><strong><em>K </em></strong><em>which is an integer between </em><strong><em>1 to 100</em></strong><em>.</em></p><p><em>You have to determine if it is possible to remove some of the digits (possibly 0) so that the result contains at least 1 digit, forms a non-negative integer, doesn’t have leading zeroes &amp; is divisible by </em><strong><em>K</em></strong><em>.</em></p><p><em>Please note, you can’t rearrange the digits which are left, after removals.<br>If a solution exists, you should print it. (Print any, if multiple).</em></p><h3>The Strategy 💡</h3><p>After reading the problem statement, we can quickly summarise the input constraints. This step is crucial for selecting the type of strategy we can employ.</p><pre><strong>Constraints:</strong></pre><pre><em>1 </em>≤ <em>lenght(N) </em>≤ <em>1000<br>1 </em>≤ <em>K </em>≤ <em>100</em></pre><p>Okay, let’s approach this problem in a simple way. We need to remove some digits from a ridiculously long number so that it is divisible by a number <strong>K</strong>.</p><p>There are <strong><em>2 </em></strong><em>challenges</em> in front of us:</p><h4>Operating a 1000 digit number as an integer</h4><p>Let’s consider that our language doesn’t have the support to operate upon such a large integer. In that case, we need to write our <strong><em>custom divisibility checker </em></strong>module to find out the divisibility of potential candidates.</p><p>You may argue, that you can do it or use a language that has a <strong>BIG INT </strong>support. <em>Fair, enough!</em> Let’s look at the other caveat.</p><h4>Generating all possible candidate solutions</h4><p>We are allowed to remove a certain number of digits from the number so that it can be divisible by <strong>K</strong>.</p><p>Since <strong>K </strong>can be anything, you need to generate all the candidate solutions and compare each of them against <strong>K</strong> for divisibility.</p><p>But, here is the catch. <em>The idea of generating all the candidates is equivalent to generating subsets of a given set.</em></p><pre>Say your <strong>N</strong> = 123</pre><pre>Now you want to generate candidate solutions by removing:<br>- <strong>0 digits:</strong> 123 <br>- <strong>1 digits:</strong> 23, 13, 12<br>- <strong>2 digits: </strong>1, 2, 3</pre><pre><strong>NOTE:</strong><em> We can&#39;t remove all the 3 digits as per the questions</em></pre><p>Just like above, where we have 2³-1 = 7 candidate solutions, there can be (2^lenght(N))-1 subsets for any <strong>N</strong>.</p><p>In the worst case, your <strong>subset generation module </strong>will timeout purely because <strong>2¹⁰⁰⁰</strong> is pretty large!</p><p>How large? Typically, you can perform <strong><em>10⁶ operations (10⁶ ~ 2²⁰) </em></strong><em>in </em><strong><em>1 second</em></strong><em>.</em></p><pre><strong><em>2²⁰ </em></strong>= 1 Second<strong><em><br>2⁸⁰ </em>= </strong>37 Billion Years! <em>(Universe is </em><strong><em>only</em></strong><em> 13.77 Billion Years Old)</em></pre><p>So we can’t continue with the approach. We definitely need to look beyond the obvious now.</p><p>Since we can’t ascertain a general rule for the divisibility with <strong>K</strong>, we ought to surely search the entire subspace. <br>We do so while dividing the problems into overlapping subproblems and solving each of them <strong><em>only once</em></strong>.</p><p>Let’s try to think in terms of <strong>Dynamic Programming.</strong></p><h4>Defining states</h4><p>Let’s define a State <strong>S[i, j] </strong>such that <strong>i </strong>is<strong> <em>0≤ i ≤ len(N) </em></strong>and <strong>j</strong> is <strong><em>0 ≤ j &lt; K</em></strong>.<br>Also, let <strong>Arr[len(N)] </strong>be an array of digits of integer <strong>N</strong>.</p><p>Here <strong>S[i, j] </strong>will be <strong><em>true</em></strong> only if we can add some digits from the array segment <strong>Arr[i, len(N)-1] </strong>to make it divisible by <strong>K</strong>.</p><p>The <em>second</em> state parameter, <strong>j </strong>stores the remainder against <strong>K</strong> for the number till now. Clearly, if we can have this remainder as <strong>0 </strong>that will give us a number which is divisible by <strong>K</strong>. That will be our answer. For instance:</p><pre>Consider <strong>N = 123</strong> and <strong>K = 2</strong></pre><pre>Now, state <strong>S[0,1]</strong> depicts the case where you are on choosing the <strong>first</strong> digit (index 0) and taking its remainder with <strong>2 </strong>(which is 1). You can see its value will be <strong>true </strong>as you can just include the second digit and the combined number <strong><em>12 </em></strong>will be divisible by <strong>2</strong>. </pre><pre>Thereforce, S[0,1] will evaluate to <strong><em>true</em></strong><em>.</em></pre><h4>Defining transitions</h4><p>The next step in a Dynamic Programing technique is to define <strong>transitions </strong>between the states. Since you are breaking down your bigger problem into smaller constituent problems, you need a way to relate them.</p><blockquote><em>Formally a transition is: </em><strong><em>S[i, j] →S[i`, j`]</em></strong></blockquote><p>Consider an arbitrary state <strong>S[i, j] </strong>from <strong>Arr[len(N)]</strong>.</p><p>Now you can either choose to delete the current digit <strong>Arr[i] </strong>or not. So at each index of the array,<strong><em> you have exactly 2 choices</em></strong>.</p><p>If you are <strong>not</strong> deleting the current digit then you need to change the parameter <strong>j </strong>to take into consideration this digit, while computing the remainder of the number formed till now.</p><pre>j` = ((j * 10) + Arr[i]) % K<br>i` = i + 1 </pre><p>Contrarily, if you are deleting the current digit then, you need <strong>not</strong> perform any such transition to parameter <strong>j </strong>and can just move to the next index.</p><pre>j` = j<br>i` = i + 1</pre><blockquote>So we can recurse down to both these states and check from what transition are we getting <strong>true</strong> (if at all) as a return value.<br>Depending upon that we can assign the value for the current state <strong>S[i, j] </strong>as either <strong>true</strong> or <strong>false</strong>.</blockquote><h4>Getting the number</h4><p>Now we need to get the number that was divisible by <strong>K</strong>.</p><p>For that, as we are progressing towards the end of the digits, the moment we get a remainder as <strong>0</strong>, we return <strong>true </strong>for all the preceding parent recursive calls that led us to this state. Based on this, we can simply store the digits whose inclusion led us to this <strong>true </strong>state.</p><p>Since we are describing a recursive solution here, that simply means pushing the current digit to a <strong>stack</strong> whenever we receive a <strong>true </strong>return value for a choice where we have retained the current digit. This will be clearer when we will see the code.</p><h3><strong>The Code 🎉</strong></h3><blockquote><strong>Input</strong></blockquote><blockquote><em>356652<br>8</em></blockquote><blockquote><strong>Output</strong></blockquote><blockquote><em>3552</em></blockquote><blockquote><strong>Code in C++14</strong></blockquote><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e756fc6fc0fa295836023b2d7740fe5a/href">https://medium.com/media/e756fc6fc0fa295836023b2d7740fe5a/href</a></iframe><p><strong><em>Voila! 🌠</em></strong></p><blockquote><em>Want more content like this?</em></blockquote><blockquote><em>You can connect with me on Twitter here:</em><strong><em> </em></strong><a href="https://twitter.com/abshekha"><strong><em>abshekha</em></strong></a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=88b6b9d33b90" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codestories/division-dynamic-programming-88b6b9d33b90">Division &amp; Dynamic Programming</a> was originally published in <a href="https://medium.com/codestories">Code Stories</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Code Stories: An Introduction]]></title>
            <link>https://medium.com/codestories/code-stories-an-introduction-d8c100aa562a?source=rss-dcb3ce5a8245------2</link>
            <guid isPermaLink="false">https://medium.com/p/d8c100aa562a</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[code]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Abhimanyu Shekhawat]]></dc:creator>
            <pubDate>Fri, 27 Nov 2020 10:43:12 GMT</pubDate>
            <atom:updated>2020-12-02T19:18:33.402Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zQXjtQ-Hv-4UiQk0Sd8ykg.png" /><figcaption>Making Computer Science simple bit by bit</figcaption></figure><blockquote>If you can’t explain it simply, you don’t understand it well.</blockquote><p>Computer Science is often seen as an esoteric discipline. Most of the learners approach it in a convoluted fashion. You hear complex mathematical jargon thrown around in corridors. <br>On top of that Pop culture left no stone unturned to depict Programming as a niche skill possessed by socially anxious (awkward) individuals.</p><p>However, I can’t blame them entirely. The complexity of a subject depends on a variety of things like:</p><ul><li><em>Are you exposed to similar branches of knowledge?</em></li><li><em>What do you want to achieve by studying it?</em></li><li><em>How much time &amp; interest do you have?</em></li><li><em>How do you plan to approach the subject?</em></li></ul><p>Often learners skip the part where they honestly answer these questions. <br>This leads to all kinds of problems. <br>It ultimately results in their dry outlook towards a rather succulent and creative branch of knowledge.</p><p>Being a Computer Science graduate, I can assure you, things are not as difficult as they look like. Sure, they require novel thinking and good problem-solving skills. But like I said, these are skills and can be developed.</p><p>Therefore today, I am starting a series of articles that will take a programming problem and deconstruct it into intuitive puzzles.</p><p>You will see, how typical problems can be solved without any complex mumbo-jumbo if we ask ourselves the right questions and approach them systematically.</p><p><em>In the coming series of essays, we will follow a consistent structure:</em></p><ul><li><strong>The Problem</strong> ❓</li><li><strong>The Strategy </strong>💡</li><li><strong>The Code 🎉</strong></li></ul><p>We will start with a detailed problem statement and gradually proceed towards the solution by building upon the <em>existing knowledge </em>and <em>intuition</em>. Towards the end, we will code that solution away.</p><p>I am a big fan of <strong><em>community learning</em></strong>.<strong><em> </em></strong>When you learn together, it leads to an understanding that is beyond the realm of an isolated study session. <br>The best way to achieve this is to share your learnings with the community that helped you grow.</p><p>I strongly feel that these essays will rekindle your curiosity and soon you will see how fun problem solving is.</p><blockquote>The journey of <strong>thousand </strong>commits begins with a single <strong>init</strong> 🎊</blockquote><p><em>Want more of this?</em></p><p><em>You can connect on Twitter here:</em><strong><em> </em></strong><a href="https://twitter.com/abshekha"><strong><em>abshekha</em></strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d8c100aa562a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codestories/code-stories-an-introduction-d8c100aa562a">Code Stories: An Introduction</a> was originally published in <a href="https://medium.com/codestories">Code Stories</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Newton & Square Roots]]></title>
            <link>https://medium.com/codestories/newton-square-roots-c03b1907c8af?source=rss-dcb3ce5a8245------2</link>
            <guid isPermaLink="false">https://medium.com/p/c03b1907c8af</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Abhimanyu Shekhawat]]></dc:creator>
            <pubDate>Sun, 08 Nov 2020 14:43:50 GMT</pubDate>
            <atom:updated>2021-11-26T12:50:55.921Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*FuOPuMRbcjp8EPFvfWa43w.jpeg" /></figure><p>The web is an interesting place, it humbles you down and shows how little you actually know. While hitchhiking through the hyperlinks, I had one such realization recently.</p><p>What if I ask you to calculate the square root of a number? Depending upon your background you are likely to come up with a variety of solutions. Let me talk about that specific fraction of you who will be interested in churning out code for doing so. <em>[No, sqrt()]</em></p><p><em>Binary Search</em> seems to be a valid and intuitive approach, after all, we can easily discard half of the search space in each iteration. But I want you to hold that thought and glance over this small snippet below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1fbcb00296f7aec0160df67742317221/href">https://medium.com/media/1fbcb00296f7aec0160df67742317221/href</a></iframe><p>Magical isn’t it? When I first looked at this, I was really startled by the elegance of this solution. So what is it and why does it work?</p><h3>Sweet Mathematics</h3><p>You just witnessed the glamour of <strong><em>Newton Raphson</em></strong> method.</p><p>In simple terms, it is a way to quickly find a good approximation for the roots of a real-valued function <strong>f(x) = 0</strong>.</p><p>This is our cue, square root for a number can be minimally represented by solving for the roots of <strong>f(x) = x² — N</strong>, where <em>N</em> is the number we have to find the root of.</p><p>That is all cool! But how does it actually work? Let’s look at the simple math behind this:-</p><ol><li>Consider a general function: <strong>y = f(x)</strong>.<br>We start by choosing an arbitrary value <strong>x1</strong> as our starting point[1]. For our specific case, we can choose <strong>N/2</strong> as our starting point and can safely discard values greater than that from the candidature of <strong>√N</strong>.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/880/0*09i28iZehsysW_uJ.png" /></figure><p>2. Now let’s draw a tangent (Differential) to the curve at that point and mark its intersection with the x-axis. Let’s call this <strong>x2</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/880/0*WMUKqdOu5irGMItT.png" /></figure><p>3. Repeat <em>step 2</em> for point <strong>x2</strong> to obtain <strong>x3</strong>. You must have noticed that with each iteration we are nearing the roots of the quadratic equation. Slow and steady!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/880/0*czfYmq9OkTxVkK3I.png" /></figure><blockquote><em>Depending upon the precision, you can decide upon the number of iterations required.</em></blockquote><h3>Formal Expression</h3><p>Let’s try to workout an elegant formula for <strong>f(x) = x² — N </strong>which will get us the compact code we saw in the beginning. Please note that we are aiming to get a relation between <strong>Nth</strong> and <strong>(N+1)th</strong> iteration.</p><ul><li>For any point <strong>X[n]</strong>, by using the equation of line we can get:<br><strong>f’(X[n]) = (f(X[n+1]) — f(X[n]))/(X[n+1] — X[n])</strong><br>[<em>f’(x)</em> being the slope at point <em>x</em>]</li><li>Putting <strong>0</strong> for y coordinate at point <strong>X[n+1]</strong>where tangent crosses x-axis we get:<br><strong>f’(X[n]) = (- f(X[n]))/(X[n+1]- X[n])</strong></li><li>Rearranging the terms &amp; putting <strong>f’(X) = 2X[n]</strong> we have our final expression:<br><strong>X[n+1] = (Xn + n/X[n])/2</strong></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/880/0*QmiFqHHsjWo7gP5o.png" /></figure><blockquote><em>Visualising Newton Raphson method for N = 10000</em></blockquote><h3>Notes</h3><p>[1] For the sake of simplicity, I have omitted the details about choosing the initial value which plays a crucial role in more complex functions.</p><p><em>Special thanks to </em><a href="https://amsi.org.au/"><em>AMSI</em></a><em> for facilitating illustrations</em></p><blockquote><em>If you liked this post, you can find more by:</em></blockquote><blockquote><em>Following me on </em><strong><em>Twitter</em></strong><em>: </em><a href="https://twitter.com/abshekha"><em>@abshekha</em></a><em> [Super active here!]</em></blockquote><blockquote><em>Connecting on </em><strong><em>LinkedIn</em></strong><em>: </em><a href="https://www.linkedin.com/in/abhimanyubitsgoa/"><em>abhimanyubitsgoa</em></a></blockquote><p>Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c03b1907c8af" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codestories/newton-square-roots-c03b1907c8af">Newton &amp; Square Roots</a> was originally published in <a href="https://medium.com/codestories">Code Stories</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>