{"id":701,"date":"2025-07-21T14:03:01","date_gmt":"2025-07-21T08:33:01","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=701"},"modified":"2025-07-21T14:55:01","modified_gmt":"2025-07-21T09:25:01","slug":"minimum-bit-flips-to-convert-number","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/","title":{"rendered":"Minimum Bit Flips to Convert Number | Leetcode 2220 | Optimal Solution in Python"},"content":{"rendered":"\n<p>A&nbsp;<strong>bit flip<\/strong>&nbsp;of a number&nbsp;<code>x<\/code>&nbsp;is choosing a bit in the binary representation of&nbsp;<code>x<\/code>&nbsp;and&nbsp;<strong>flipping<\/strong>&nbsp;it from either&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>1<\/code>&nbsp;or&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>0<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>For example, for&nbsp;<code>x = 7<\/code>, the binary representation is&nbsp;<code>111<\/code>&nbsp;and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get&nbsp;<code>110<\/code>, flip the second bit from the right to get&nbsp;<code>101<\/code>, flip the fifth bit from the right (a leading zero) to get&nbsp;<code>10111<\/code>, etc.<\/li>\n<\/ul>\n\n\n\n<p>Given two integers&nbsp;<code>start<\/code>&nbsp;and&nbsp;<code>goal<\/code>, return<em>&nbsp;the&nbsp;<strong>minimum<\/strong>&nbsp;number of&nbsp;<strong>bit flips<\/strong>&nbsp;to convert&nbsp;<\/em><code>start<\/code><em>&nbsp;to&nbsp;<\/em><code>goal<\/code>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/minimum-bit-flips-to-convert-number\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> start = 10, goal = 7\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:\n- Flip the first bit from the right: 1010 -&gt; 1011.\n- Flip the third bit from the right: 1011 -&gt; 1111.\n- Flip the fourth bit from the right: 1111 -&gt; 0111.\nIt can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> start = 3, goal = 4<br><strong>Output:<\/strong> 3<br><strong>Explanation:<\/strong> The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps:<br>- Flip the first bit from the right: 011 -&gt; 010.<br>- Flip the second bit from the right: 010 -&gt; 000.<br>- Flip the third bit from the right: 000 -&gt; 100.<br>It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>0 &lt;= start, goal &lt;= 10<sup>9<\/sup><\/code><\/li>\n<\/ul>\n\n\n<div class=\"wp-block-ub-table-of-contents-block ub_table-of-contents\" id=\"ub_table-of-contents-44c53712-7940-43fa-8a40-dc029e01bad3\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"false\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"true\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column \">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#0-solution-1-optimal-approach-bitwise-shift\" style=\"\">Solution 1: Optimal Approach (Bitwise Shift)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#8-solution-2-optimal-approach-while-loop\" style=\"\">Solution 2: Optimal Approach (While Loop)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-bit-flips-to-convert-number\/#16-summary\" style=\"\">Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-optimal-approach-bitwise-shift\">Solution 1: Optimal Approach (Bitwise Shift)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Imagine you have two binary numbers, like two strings of lights where some are on (1) and some are off (0). To make the first string match the second, you need to flip the switches that are different. The quickest way to spot the differences is using XOR &#8211; it highlights exactly where the bits don&#8217;t match (gives 1 where different). Then, we just count how many 1s are in that XOR result &#8211; that&#8217;s the number of flips needed!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Compute XOR<\/strong>: Do start ^ goal to get a number where each 1 bit represents a position that needs flipping.<\/li>\n\n\n\n<li><strong>Count Set Bits<\/strong>: Loop through each possible bit position (0 to 31 for 32-bit integers) and check if that bit is set (1) in the XOR result.<\/li>\n\n\n\n<li><strong>Increment Count<\/strong>: Every time a bit is set, add 1 to our count &#8211; that&#8217;s one flip needed.<\/li>\n\n\n\n<li><strong>Return the Count<\/strong>: This gives the minimum flips since each differing bit must be flipped exactly once.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def minBitFlips(self, start: int, goal: int) -&gt; int:\n        ans = start ^ goal  # XOR to find differing bits\n        count = 0           # Counter for number of flips\n        \n        # Check each of the 32 bits\n        for i in range(0, 32):\n            # If the i-th bit is set (1), increment count\n            if ans &amp; (1 &lt;&lt; i) != 0:\n                count += 1\n        \n        return count\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">minBitFlips<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">start<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">goal<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans = start ^ goal  <\/span><span style=\"color: #6A9955\"># XOR to find differing bits<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        count = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">           <\/span><span style=\"color: #6A9955\"># Counter for number of flips<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Check each of the 32 bits<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">32<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># If the i-th bit is set (1), increment count<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> ans &amp; (<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> &lt;&lt; i) != <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                count += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> count<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>We first XOR the two numbers, which creates a new number where every bit that&#8217;s different between start and goal is set to 1. Then, we loop through all 32 possible bits (since integers are 32-bit). For each bit position i, we use a bitwise AND with (1 shifted left by i) to check if that bit is 1. If it is, we know that&#8217;s a difference, so we add 1 to our flip count. This way, we&#8217;re basically counting how many bits need to be flipped without converting to binary strings.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s take start = 10 (binary: 1010), goal = 7 (binary: 0111)<\/p>\n\n\n\n<p><strong>Step 1: XOR<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>1010 ^ 0111 = 1101 (13 in decimal)<\/li>\n<\/ul>\n\n\n\n<p><strong>Step 2: Count Set Bits<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>i=0: 1101 &amp; 0001 = 0001 \u2260 0 \u2192 count=1<\/li>\n\n\n\n<li>i=1: 1101 &amp; 0010 = 0000 = 0 \u2192 count=1<\/li>\n\n\n\n<li>i=2: 1101 &amp; 0100 = 0100 \u2260 0 \u2192 count=2<\/li>\n\n\n\n<li>i=3: 1101 &amp; 1000 = 1000 \u2260 0 \u2192 count=3<\/li>\n\n\n\n<li>Higher bits are 0, so stop<\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;3 flips needed<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(1) &#8211; We always loop 32 times, regardless of input size (fixed for 32-bit integers)<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(1) &#8211; We only use a few integer variables<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This is like comparing two binary fingerprints and counting the smudges (differences). XOR does the comparison in one go, and the loop just tallies up the mismatches. Super fast and no extra space needed!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-solution-2-optimal-approach-while-loop\">Solution 2: Optimal Approach (While Loop)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>Again, we use XOR to find the differing bits, just like in the first approach. But instead of checking each bit position one by one, we can keep dividing the XOR result by 2 (right shift) and check if the last bit is 1 each time. It&#8217;s like peeling off the bits one by one from the end and counting how many are standing up (set to 1).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Compute XOR<\/strong>: Same as before &#8211; start ^ goal gives us the differing bits.<\/li>\n\n\n\n<li><strong>While Loop<\/strong>: While the XOR result is greater than 0, check if it&#8217;s odd (last bit is 1), add to count if yes.<\/li>\n\n\n\n<li><strong>Divide by 2<\/strong>: Divide the number by 2 to shift right and check the next bit.<\/li>\n\n\n\n<li><strong>Repeat<\/strong>: Continue until all bits are processed (number becomes 0).<\/li>\n\n\n\n<li><strong>Return the Count<\/strong>: This is our minimum flips.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def minBitFlips(self, start: int, goal: int) -&gt; int:\n        ans = start ^ goal  # XOR to find differing bits\n        count = 0           # Counter for number of flips\n        \n        # While there are bits left to check\n        while ans &gt; 0:\n            # If last bit is 1 (odd number), increment count\n            if ans % 2 == 1:\n                count += 1\n            # Divide by 2 to shift right\n            ans = ans \/\/ 2\n        \n        return count\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">minBitFlips<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">start<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">goal<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans = start ^ goal  <\/span><span style=\"color: #6A9955\"># XOR to find differing bits<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        count = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">           <\/span><span style=\"color: #6A9955\"># Counter for number of flips<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># While there are bits left to check<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> ans &gt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># If last bit is 1 (odd number), increment count<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> ans % <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\"> == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                count += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Divide by 2 to shift right<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            ans = ans \/\/ <\/span><span style=\"color: #B5CEA8\">2<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> count<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>After XOR, we get a number with 1s where bits differ. In the while loop, we check if the number is odd (ans % 2 == 1), which means the least significant bit is 1 &#8211; that&#8217;s a flip needed! Then we divide by 2 (integer division) to remove that bit and shift everything right. We repeat this until the number is 0. This effectively counts all the 1 bits in the binary representation.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s take start = 10 (binary: 1010), goal = 7 (binary: 0111)<\/p>\n\n\n\n<p><strong>Step 1: XOR<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>1010 ^ 0111 = 1101 (13 in decimal)<\/li>\n<\/ul>\n\n\n\n<p><strong>Step 2: While Loop<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>ans=13 (1101), 13%2=1 \u2192 count=1, ans=6 (0110)<\/li>\n\n\n\n<li>ans=6 (0110), 6%2=0 \u2192 count=1, ans=3 (0011)<\/li>\n\n\n\n<li>ans=3 (0011), 3%2=1 \u2192 count=2, ans=1 (0001)<\/li>\n\n\n\n<li>ans=1 (0001), 1%2=1 \u2192 count=3, ans=0 (0000)<\/li>\n\n\n\n<li>Loop ends<\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;3 flips needed<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(log n) &#8211; We loop as many times as there are bits in the number (up to 32 for integers)<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(1) &#8211; Just a few variables, no extra space<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This is like slicing off the end of a binary number repeatedly and checking if it&#8217;s a 1 each time. If it is, that&#8217;s a flip! It&#8217;s even simpler than the first method because there&#8217;s no fixed loop &#8211; it stops when there are no more bits to check.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"16-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Difficulty<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Bitwise Shift (Optimal 1)<\/td><td>O(1)<\/td><td>O(1)<\/td><td>Easy<\/td><td>Fixed-loop lovers<\/td><\/tr><tr><td>While Loop (Optimal 2)<\/td><td>O(log n)<\/td><td>O(1)<\/td><td>Easy<\/td><td>Dynamic looping<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Both solutions are super efficient and use the power of XOR to find differences quickly. The first one is great if you like explicit bit checking, while the second is more concise and adapts to the number&#8217;s size. In interviews, either works, but mention XOR as the key trick!<\/p>\n\n\n\n<p>If you&#8217;re practicing for LeetCode or interviews, try implementing these yourself and experiment with different numbers. Got questions? Drop them in the comments &#8211; happy coding! \ud83d\ude80<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>A&nbsp;bit flip&nbsp;of a number&nbsp;x&nbsp;is choosing a bit in the binary representation of&nbsp;x&nbsp;and&nbsp;flipping&nbsp;it from either&nbsp;0&nbsp;to&nbsp;1&nbsp;or&nbsp;1&nbsp;to&nbsp;0. Given two integers&nbsp;start&nbsp;and&nbsp;goal, return&nbsp;the&nbsp;minimum&nbsp;number of&nbsp;bit flips&nbsp;to convert&nbsp;start&nbsp;to&nbsp;goal. Here&#8217;s the [Problem Link] to begin with. Example 1: Input: start = 10, goal = 7 Output: 3 Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert<\/p>\n","protected":false},"author":1,"featured_media":702,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,4],"tags":[31,8],"class_list":{"0":"post-701","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-beginner","9":"tag-bit-manipulation","10":"tag-easy"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/minimum-bit-flips-to-convert-number-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/701","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=701"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/701\/revisions"}],"predecessor-version":[{"id":716,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/701\/revisions\/716"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/702"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=701"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=701"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=701"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}