<?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 Kingsten Banh on Medium]]></title>
        <description><![CDATA[Stories by Kingsten Banh on Medium]]></description>
        <link>https://medium.com/@kingsten?source=rss-1b9a59d9683a------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*cCmdtzlMoMzn2tZfck0cEQ.jpeg</url>
            <title>Stories by Kingsten Banh on Medium</title>
            <link>https://medium.com/@kingsten?source=rss-1b9a59d9683a------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 04:03:53 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@kingsten/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[Karatsuba’s Multiplication]]></title>
            <link>https://medium.com/@kingsten/karatsubas-multiplication-4035fd4c0f72?source=rss-1b9a59d9683a------2</link>
            <guid isPermaLink="false">https://medium.com/p/4035fd4c0f72</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[programming-interviews]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[karatsuba]]></category>
            <dc:creator><![CDATA[Kingsten Banh]]></dc:creator>
            <pubDate>Sun, 07 Apr 2019 23:18:58 GMT</pubDate>
            <atom:updated>2019-04-07T23:23:13.472Z</atom:updated>
            <content:encoded><![CDATA[<p>I am taking the <a href="https://www.coursera.org/learn/algorithms-divide-conquer/">Divide and Conquer, Sorting and Searching, and Randomized Algorithms</a> course from Coursera. The problem assignment for week 1 is to implement the integer multiplication algorithm using Karatsuba’ multiplication method. As a result, you can multiply two 64-digit numbers:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1f7ff0abb020562cccfa68e2be788038/href">https://medium.com/media/1f7ff0abb020562cccfa68e2be788038/href</a></iframe><p>Try multiply these two numbers you will get</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1fd5593b83cdb1166a08a95308066e9f/href">https://medium.com/media/1fd5593b83cdb1166a08a95308066e9f/href</a></iframe><p>It is the correct result, but it loses a lot of precision because the largest integer JavaScript can display is 2⁵³-1 (<a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER">MDN</a>).</p><p>To solve this problem, we could use Karatsuba’s algorithm and <a href="https://github.com/tc39/proposal-bigint">BigInt prosal</a> from JavaScript T39 committee.</p><p>In Karatsuba’s algorithm, we recursively break down each integer in half until it is less than 10 which consists of one single digit. Then we multiply two single digits together. n is the number of digits for each integer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/717/1*Z6Ga40aVeePrw2UgBwP7Hg.png" /></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/339ea10d586bfe4d08844eb0bc0ce7dd/href">https://medium.com/media/339ea10d586bfe4d08844eb0bc0ce7dd/href</a></iframe><p>Effectively, at each recursive call, the program will try to break each number into a, b, c, d to compute the multiplication based on the formula we have. Instead of truncating the result with a regular integer, BigInt has enough precision to display the complete result as</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2f73ddd6c80804ecd9f8c205ee4e003a/href">https://medium.com/media/2f73ddd6c80804ecd9f8c205ee4e003a/href</a></iframe><p>Hope you find it helpful!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4035fd4c0f72" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[What is a Palindrome?]]></title>
            <link>https://medium.com/@kingsten/what-is-a-palindrome-1c25b0196ae3?source=rss-1b9a59d9683a------2</link>
            <guid isPermaLink="false">https://medium.com/p/1c25b0196ae3</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[freecodecamp]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[learning-to-code]]></category>
            <category><![CDATA[palindrome]]></category>
            <dc:creator><![CDATA[Kingsten Banh]]></dc:creator>
            <pubDate>Tue, 19 Feb 2019 21:49:37 GMT</pubDate>
            <atom:updated>2019-02-19T21:49:37.019Z</atom:updated>
            <content:encoded><![CDATA[<p>A palindrome is a special type of word that can be spelled the same backward and forward.</p><p><strong>Examples of Palindromes: </strong>mom, dad, eye, ewe, noon, poop, peep, etc.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/681/1*ZwZqKkInL-N_v0wuUS_2XA.png" /></figure><p>Palindromes can be words, sentences, groups of numbers, or even equations</p><p><strong>Examples of longer palindromes: </strong>racecar, madam, kayak, redder, etc.</p><p>Sentences can also be written as palindromes. When you write a sentence a palindrome, you can re-arrange punctuation and capital letters.</p><ul><li>Madam, I’m Adam.</li><li>I did, did I?</li><li>He did, eh?</li><li>Never odd or even.</li><li>Nurses run!</li><li>Oh no, Don ho!</li><li>Step on no pets!</li><li>Too hot to hoot</li></ul><p>Some numbers can also be palindromes. Maybe you were even born in a palindromic year!</p><ul><li>2002</li><li>1991</li><li>1771</li><li>100,001</li><li>111,111,111 x 111,111,111 = 12,345,678,987,654,321</li></ul><p>Now you understand what palindrome is. First, let’s write some code to determine if a word is a palindrome.</p><p>Iterative solution</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9063aedf0b58708cef3d754589777f70/href">https://medium.com/media/9063aedf0b58708cef3d754589777f70/href</a></iframe><p><strong>Explanation</strong>: The solution compares every character in the first half to the second half of the word. If the characters are not a mirror of each other, we will return false. If we successfully compare the whole half of the word, we can confirm that the word is a palindrome.</p><p><strong>Space Complexity</strong>: 2 new variables with constant values so O(1)</p><p><strong>Time complexity</strong>: Loop through half of the word so O(n/2) or O(n).</p><p>Recursive solution</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e9c869c2d8f916e962fbd041fd840505/href">https://medium.com/media/e9c869c2d8f916e962fbd041fd840505/href</a></iframe><p><strong>Explanation</strong>: This solution is very similar to the iterative one. Since it is a recursive solution, we need a base case where we can stop the recursive loop. In our case, if the start and end characters are equal, we return true and continue to move inward to the next start and end characters. If the characters are not the same, we return false. Otherwise, when we exhaust all characters, we return true.</p><p><strong>Space Complexity</strong>: Half the length of the word time recursive calls so O(n/2) or O(n).</p><p><strong>Time Complexity</strong>: Similar to iterative O(n/2) or O(n)</p><p>Now let’s modified the solution to check if a sentence is a palindrome. In order for a sentence to be palindromic, we need to remove all the punctuations and special characters and spaces. We can employ the power of regex!!!</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a605d17687a79d0fc6793fe8133b9354/href">https://medium.com/media/a605d17687a79d0fc6793fe8133b9354/href</a></iframe><p>Wow! That’s powerful. replace(/[^\w]/gi, &quot;&quot;) will replace all the special characters and spaces with an empty string for us.</p><p>Let’s see if we can write a function that will check if a number is a palindrome with converting it to a string. Otherwise, it is too easy! I think we can, right?!</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/13db61ab5991b9534968dd6f0110823b/href">https://medium.com/media/13db61ab5991b9534968dd6f0110823b/href</a></iframe><p><strong>Explanation</strong>: The solution is pretty straigh forward. We can apply the same principle as a string. However, we can find the length of a number. So we need a way to extract the leading and trailing digits from the number and modify the number after each iteration. Math is here to rescue us!</p><p><strong>Space Complexity</strong>: We have 2 variables for leading and trailing half of the length of the number which is O(n/2 * 2) or O(n).</p><p><strong>Time Complexity</strong>: Similarly we loop through half of the length of the number O(n/2) or O(n).</p><p>Thank you for reading! Let’s me know what you like me to cover next :D</p><p>Happy Coding!!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1c25b0196ae3" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>