<?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 Harshitdaga on Medium]]></title>
        <description><![CDATA[Stories by Harshitdaga on Medium]]></description>
        <link>https://medium.com/@harshitdaga7?source=rss-1d5f5313f4f5------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*jDDoJaeEPUjD76fI.jpg</url>
            <title>Stories by Harshitdaga on Medium</title>
            <link>https://medium.com/@harshitdaga7?source=rss-1d5f5313f4f5------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 10:12:18 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@harshitdaga7/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[Distance and Center of a Tree or Graph]]></title>
            <link>https://medium.com/@harshitdaga7/distance-and-center-of-a-tree-or-graph-4d608371d70a?source=rss-1d5f5313f4f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/4d608371d70a</guid>
            <dc:creator><![CDATA[Harshitdaga]]></dc:creator>
            <pubDate>Wed, 03 May 2023 07:03:07 GMT</pubDate>
            <atom:updated>2023-05-03T07:05:07.877Z</atom:updated>
            <content:encoded><![CDATA[<p>There are many metrics to measure tree or a graph. This includes center, diameter, radius, length , etc. This metrics try to give an overview of some properties of graph like its topographical structure without actually looking or fully traversing the graph or tree. This helps in quickly summarizing the graph and helps in some algorithmic tasks.</p><h3>What is a Tree ?</h3><p>A tree is a special type of graph . A tree is an undirected vertex in which any two vertices are connected by exactly one path, or equivalently a connected acyclic graph. A tree with n nodes will have exactly n-1 edges. A tree can be a graph , but not all graphs are trees.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*T4u0ZE_LZHKEYb2d3sNP4g.png" /><figcaption>Example of a Binary Tree</figcaption></figure><p>Tree has many applications including decision tree in machine learning, minimum spanning tree for shortest path, binary search tree is used in a read optimized databases for retrieval of information.</p><p>There are various metrics related to tree like length , distance , eccentricity , diameter , radius , center of a tree, etc.</p><p>These metrics are used to summarize the tree in one or two lines and understand the properties of tree in a higher level sense.</p><h3><strong>Here are some of the metrics relevant to center and distance of a tree/graph</strong>.</h3><h3>Eccentricity of a Tree / Graph :</h3><p>It is defined as the maximum distance of one vertex to all other vertices. The maximum distance between a vertex to all other vertices is considered as the eccentricity of the vertex. It is denoted by E(v) , where v is the vertex of which eccentricity is being calculated.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/321/1*wRA-Yj6eyb6TaU2NHGonoQ.jpeg" /></figure><p>Here , Distance (A,A) = 0<br>Here , Distance (A,B) = 1<br>Here , Distance (A,C) = 2<br>Here , Distance (A,D) = 1</p><p>Here , eccentricity of A is 2 ( as maximum distance is 2)</p><h3><strong>Centre of a Tree/Graph</strong></h3><p>It consists of all the vertices whose eccentricity is minimum. Eccentricity has many applications. For instance, If the school is at the center of town it will reduce the distance buses has to travel. If eccentricity of two vertex is same and minimum among all other both of them can be center of the graph.</p><p>To put it in simple terms, center of a tree is the vertex , which is topologically centered, i.e., has the minimum maximum distance that needs to traversed to go to other vertex.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/437/1*5CIxIZBf912PtYnriHjddA.png" /></figure><p>Here , eccentricity (A) = 3<br>Here , eccentricity (B) = 4<br>Here , eccentricity (C) = 5<br>Here , eccentricity (D) = 4<br>Here , eccentricity (E) = 5<br>Here , eccentricity (F) = 4<br>Here , eccentricity (G) = 4<br>Here , eccentricity (H) = 3<br>Here , eccentricity (I) = 4<br>Here , eccentricity (J) = 5</p><p>Here , minimum eccentricity of is 3 and center can be H or .</p><h3>Steps to calculate eccentricity :</h3><ol><li>Input two vertex A and B</li><li>Traverse the graph between A and B.</li><li>Find the distance between A and B.</li><li>This is distance of d(A,B)</li><li>Repeat this process for every pair of vertex(A,B[i]) and the maximum is the eccentricity of vertex A or E(A).</li></ol><h3>Steps to calculate center :</h3><ol><li>n , no of edges</li><li>N[i] , ith node</li><li>eccentricities = []; store of eccentricities of each vertex.</li><li>for i in range(n): eccentricities.push(eccentricity(N[i])</li><li>center = minimum (eccentricity)</li></ol><h3>Applications :</h3><ol><li>Distance between two nodes in a graph can be used to model and identify time between two cities.</li><li>Network Design : The graph centre is the node or set of nodes that minimize the maximum distance to all other nodes in graph . This property is useful in designing efficient networks that minimize the total distance travelled by information or resources.</li><li>Social Network Analysis : A graph center can represent the most influential individual or person in a social network graph.</li></ol><h3>Questions</h3><ol><li>What is a Tree ?</li><li>What is eccentricity ?</li><li>What is Centre of a Tree ?</li><li>Steps to calculate center ?</li><li>Applications of center of a Tree ?</li></ol><h3>Acknowledgment</h3><p>Dr Rekha Sharma Associate Professor Department of computer engineering, Thakur College of Engineering and Technology</p><h3>References</h3><ul><li><a href="https://csacademy.com/app/graph_editor/">CS Academy</a></li><li><a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree - Wikipedia</a></li><li><a href="https://en.wikipedia.org/wiki/Tree_(graph_theory)">Tree (graph theory) - Wikipedia</a></li><li><a href="https://www.geeksforgeeks.org/graph-measurements-length-distance-diameter-eccentricity-radius-center/">Graph measurements: length, distance, diameter, eccentricity, radius, center - GeeksforGeeks</a></li><li><a href="https://en.wikipedia.org/wiki/Graph_center">Graph center - Wikipedia</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4d608371d70a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solution of count the contiguous subarrays having product less than k]]></title>
            <link>https://medium.com/@harshitdaga7/solution-of-count-the-contiguous-subarrays-having-product-less-than-k-80475e6cc71f?source=rss-1d5f5313f4f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/80475e6cc71f</guid>
            <category><![CDATA[dynamic-programing]]></category>
            <dc:creator><![CDATA[Harshitdaga]]></dc:creator>
            <pubDate>Fri, 28 Jan 2022 06:21:23 GMT</pubDate>
            <atom:updated>2022-01-28T06:21:23.200Z</atom:updated>
            <content:encoded><![CDATA[<p>Given an array of integers numsand an integer k, return <em>the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than </em>k.</p><p><a href="https://leetcode.com/problems/subarray-product-less-than-k/">Subarray Product Less Than K - LeetCode</a></p><p>This article will be about solution to the given leetcode problem.</p><p>Lets , take an array = [10,5,2,6] and k = 100. The continuous subarrays having product less than 100 ( as k = 100) are :</p><pre>[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]</pre><p>Here , all the subarrays have product less than 100 . Hence the count is 8.</p><h3>Naïve Solution:</h3><p>A naïve way to solve will be the brute-force approach. You can find all the continuous subarrays and calculate its product , if the resultant product is less than k , then you can increase the count.</p><p>This approach works , but it is not efficient. The time complexity in this case can be O(n*n), where n is the size of the array.</p><h3>Dynamic Programming Solution:</h3><p>With dynamic programming we can solve this problem in O(n).</p><p>Dynamic programming solution , usually involves following steps:<br>- Observation ( Understand the problem , try to convert it to a standard problem, etc. ) <br>- Initializing the dp array ( 2d , 3d, etc. ) <br>- Defining dp[i] <br>- Finding recurrence relation ( finding how to calculate i’th element using k’th element , where k can be 1 ≤ i ≤ n).</p><h4>Observation:</h4><p>Let the array be [1,2,3,4,5] and k = 25. Lets for sometime, forget about counting continuous subarrays whose product is less than k . Instead lets find the largest continuous subarray whose product is less than k.</p><p>Here , [1,2,3,4] (1*2*3*4 = 24) is the largest continuous subarray whose product is less than 25.</p><p><strong>The observation is , if a subarray S has product less than k , then the resulting subarrays of S will also have product less than k .</strong></p><p>Here , [1,2,3,4] has product less than 25 , so all the subarrays of [1,2,3,4] will also have product less than 25.</p><p>Using this observation we will construct our solution.</p><h4>DP array :</h4><p>Initialize the dp array with intial value 0 and size n, where n is the size of array.</p><p>Let dp[i] = count of continuous subarrays having product less than k , for the array ranging from 1&#39;st to i’th element.</p><p>Here , dp[n] will be count of continuous subarrays having product less than k , for the array ranging from 1&#39;st to n’th element, dp[n] will be the solution for the original problem.</p><p>We will store for each i the largest continuous subarray which ends in i , whose product is less than k and add the unique subarrays to the count</p><h4>Code :</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5a1dc32993e030f13eec6e50a3d80ccf/href">https://medium.com/media/5a1dc32993e030f13eec6e50a3d80ccf/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=80475e6cc71f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Sieve of Eratosthenes, finding prime numbers upto n]]></title>
            <link>https://medium.com/@harshitdaga7/sieve-of-eratosthenes-finding-prime-numbers-upto-n-4d1f9ccac953?source=rss-1d5f5313f4f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/4d1f9ccac953</guid>
            <category><![CDATA[sieve]]></category>
            <category><![CDATA[finding-primes]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[primes]]></category>
            <category><![CDATA[sieve-of-eratosthenes]]></category>
            <dc:creator><![CDATA[Harshitdaga]]></dc:creator>
            <pubDate>Tue, 21 Dec 2021 11:47:38 GMT</pubDate>
            <atom:updated>2022-01-28T09:50:39.168Z</atom:updated>
            <content:encoded><![CDATA[<h3>Sieve of Eratosthenes, finding prime numbers up to n</h3><p>Given a number <em>n</em> , find all prime numbers in range of 1 to <em>n</em>.</p><h4>What is a prime number ?</h4><ul><li>A prime number is a number that is divisible only by itself and 1.</li><li>2,3,5,7 are some examples of a prime number.</li></ul><h3>How to check if a number is prime or not ? O(n)</h3><p>Given a number n , how to check if the given number is prime or not ?</p><p>The naïve way to do is very simple. We just check if the given number is divisible by any numbers in the range of 1 to <em>n</em>, and if only 1 and <em>n</em> are the numbers which divide <em>n</em>, then the given number <em>n</em> is a prime.</p><p>For example, take number 7</p><ul><li>1 and 7 are the only numbers that divide 7</li><li>2,3,4,5,6 don&#39;t divide 7.</li><li>Hence , 7 is a prime number.</li></ul><p>The above method has a time complexity of <strong><em>O(n)</em></strong></p><h3>Optimized way to check if a number is prime or not ? O( sqrt(n) )</h3><p>We can do better than the above method , instead of checking all numbers in the range 1 to <em>n</em> , if they divide number n ; we only check the numbers in the range <strong>1 to <em>sqrt(n).</em></strong></p><p>For example , consider number 13, we check only till sqrt(13) , i.e. 4</p><ul><li>1 divides 13</li><li>2,3,4 do no divide 13</li><li>Hence 13 is a prime number</li></ul><p>Lets take number 9</p><ul><li>1 divides 9</li><li>2 does not divide 9</li><li>3 divides 9</li><li>Hence 9 is not a prime number</li></ul><h4>Why this works ?</h4><p>This optimization works because , factors come in pairs.</p><p>For example , for number 21 , if we know 3 is a factor than we know 7 is also a factor, as 3*7 = 21.</p><p>For given number n , we do not need to check divisibility of n for every number , because if we know all the factors of a number up to sqrt(<em>n</em>) , then we know all the factors of the number <em>n</em> , and we can determine if the number is prime or not.</p><p>Hence we don&#39;t need to check if every number in the range 1 to <em>n</em> divides <em>n</em> , checking only till sqrt(<em>n</em>) is sufficient. By doing this we reduce the time complexity by factor of n , i.e. <strong><em>O(sqrt(n))</em>.</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1de266b093737109a0537808cf78a513/href">https://medium.com/media/1de266b093737109a0537808cf78a513/href</a></iframe><h3>Finding all prime numbers in the range of 1 to n ? O(n*sqrt(n))</h3><p>We know how to find if a number is prime or not , but how to find all the prime numbers in the range of 1 to n ?</p><p>The process is very simple , we iterate through all the numbers in the range of 1 to n and check if the current number is prime or not (described in above section).</p><p>For example , consider task of finding all prime numbers up to 7. We will iterate through 1 to 7 and check if each number is prime or not . In result the prime numbers list will be [ 2,3,5,7].</p><p>Time complexity of the above method is O(n*sqrt(n))</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cfcfe6ce227c6a9d3bdc2685d7b1f99d/href">https://medium.com/media/cfcfe6ce227c6a9d3bdc2685d7b1f99d/href</a></iframe><h3>Sieve method to find all the primes in range of 1 to n ? O( n log (log n) )</h3><p>We can do better than the method given above using Sieve of Eratosthenes.</p><p>The basic idea of sieve method is if x is a prime , then any multiple of x wont be a prime.</p><p>For example, if 2 is a prime than 4,6,8,10…. cannot be prime. The sieve method builds on this idea to find all prime numbers up to range n.</p><ul><li>Lets take an example to better understand the method. Lets find all the prime numbers up to 16</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/994/1*4VKdTMwOlNir0-I3lpD15g.png" /><figcaption>Note : 1 is a trivial case . Initially all numbers are assumed to be prime (except 1).</figcaption></figure><ul><li>Now we go to 2 , and since it is green , we make all the factors of 2 ,i.e. 4,6,8,10,12,14,16 red.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/903/1*QvL_ZV2AfC2v9KFWFk0fIg.png" /><figcaption>all the multiples of 2 are red now</figcaption></figure><ul><li>We repeat the process for 3 , and make 6,9,12,15 red</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/940/1*OX8G4frqmITTEJH0H1KC_g.png" /><figcaption>multiples of 3 are also red</figcaption></figure><ul><li>Now since 4 is already red , we will skip it and repeat the process for 5.</li><li>This will go on until we end the list</li><li>If red skip</li><li>If green mark all the multiples up to n red.</li><li>The final result will be [ 2,3,5,7,11,13]</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/940/1*OX8G4frqmITTEJH0H1KC_g.png" /><figcaption>final list of all primes up to 14</figcaption></figure><p>The algorithm can be described as follows :</p><ul><li>Initially , mark all numbers up to n as prime , ( except 1)</li><li>Iterate through the list of n numbers</li><li>If current number is prime , mark all the multiples as not prime</li><li>If current number is not prime , skip to the next number</li></ul><p>Time complexity of the above method is O(n * log log (n))</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ff07f3e594dd49d03d3a4bf3bed04195/href">https://medium.com/media/ff07f3e594dd49d03d3a4bf3bed04195/href</a></iframe><p>The above method can also be further optimized</p><ul><li>instead of iterating through 1 to n , we can iterate through 1 to sqrt(n).</li><li>mark all the even numbers not prime (except 2) , and only loop through odd numbers.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4d1f9ccac953" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>