Category: LeetCode Solutions

  • Minimum Bit Flips to Convert Number | Master Beginner’s Guide with LeetCode Solution 2026

    Minimum Bit Flips to Convert Number : When working with binary numbers in programming, you might encounter a problem where you need to find the minimum number of bit flips required to convert one number into another. This is a common interview and LeetCode problem that tests your understanding of bit manipulation.

    In this guide, we’ll explain the concept step-by-step, walk through examples, and provide a LeetCode-style C++ solution.

    What Does “Bit Flip” Mean?

    A bit flip means changing a 0 to 1 or a 1 to 0 in a number’s binary representation.

    Example:

    • Original bit: 0 → Flipped bit: 1
    • Original bit: 1 → Flipped bit: 0

    If you have two integers, finding the minimum bit flips means determining the positions where the bits differ.

    Minimum Bit Flips to Convert Number  leetcode solution
    Minimum Bit Flips to Convert Number leetcode solution

    Understanding the Problem

    Problem Statement:
    Given two integers start and goal, return the minimum number of bit flips required to convert start to goal.

    Example

    Input: start = 10, goal = 7
    Binary of 10 → 1010
    Binary of 7  → 0111
    

    Comparing bit by bit:

    1 0 1 0  
    0 1 1 1  
    ↑ ↑   ↑  
    Different bits at positions 1, 2, and 4 → 3 flips needed
    

    Approach

    1. Use XOR to identify different bits:
      • XOR (^) returns 1 for differing bits, 0 for same bits.
    2. Count set bits in the XOR result:
      • The number of 1s = the number of bit flips needed.

    Step-by-Step Example

    For start = 29 and goal = 15:

    1. XOR Operation: 29 (11101) 15 (01111) XOR → 10010
    2. Count set bits in 10010:
      There are 2 set bits → 2 flips needed.

    1. C++ Solution

    #include <iostream>
    using namespace std;
    
    int minBitFlips(int start, int goal) {
        int xorValue = start ^ goal; // Step 1: XOR to find differing bits
        int count = 0;
        while (xorValue > 0) {
            count += xorValue & 1;  // Step 2: Count set bits
            xorValue >>= 1;
        }
        return count;
    }
    
    int main() {
        int start = 10, goal = 7;
        cout << "Minimum Bit Flips: " << minBitFlips(start, goal) << endl;
        return 0;
    }
    

    ✅ Shortcut in C++ (GCC/Clang):

    return __builtin_popcount(start ^ goal);
    

    2. C Solution for Minimum Bit Flips to Convert Number

    #include <stdio.h>
    
    int minBitFlips(int start, int goal) {
        int xorValue = start ^ goal; // XOR to find differing bits
        int count = 0;
        while (xorValue > 0) {
            count += xorValue & 1;  // Count set bits
            xorValue >>= 1;
        }
        return count;
    }
    
    int main() {
        int start = 10, goal = 7;
        printf("Minimum Bit Flips: %d\n", minBitFlips(start, goal));
        return 0;
    }
    

    3. Java Solution for Minimum Bit Flips to Convert Number

    public class Main {
        public static int minBitFlips(int start, int goal) {
            int xorValue = start ^ goal; // XOR to find differing bits
            int count = 0;
            while (xorValue > 0) {
                count += xorValue & 1; // Count set bits
                xorValue >>= 1;
            }
            return count;
        }
    
        public static void main(String[] args) {
            int start = 10, goal = 7;
            System.out.println("Minimum Bit Flips: " + minBitFlips(start, goal));
        }
    }
    

    ✅ Shortcut in Java (Java 8+):

    return Integer.bitCount(start ^ goal);
    

    4. Python Solution for Minimum Bit Flips to Convert Number

    def min_bit_flips(start, goal):
        xor_value = start ^ goal  # XOR to find differing bits
        count = 0
        while xor_value > 0:
            count += xor_value & 1  # Count set bits
            xor_value >>= 1
        return count
    
    # Example
    start = 10
    goal = 7
    print("Minimum Bit Flips:", min_bit_flips(start, goal))
    

    ✅ Shortcut in Python:

    return bin(start ^ goal).count('1')
    

    Time Complexity for All Solutions

    • O(k), where k = number of bits in the integer.

    Real-World Applications

    • Error Detection & Correction in data transmission.
    • Cryptography and data encoding.
    • Digital Circuit Design optimization.

    Key Takeaways

    • Use XOR to detect differences in bits.
    • Count the number of 1s in the XOR result to get the flips.
    • This is a popular LeetCode problem for practicing bit manipulation.

    FAQ for Minimum Bit Flips to Convert Number

    Q1: Is this problem available on LeetCode?

    Yes, it’s a well-known LeetCode problem often asked in coding interviews.

    Q2: What’s the fastest approach?

    The XOR + count set bits method is the fastest and most memory-efficient.

    Q3: Can I solve this in one line in C++?

    Yes, using __builtin_popcount(start ^ goal) in GCC/Clang.
  • Single Number LeetCode Solution C++ | Master XOR Trick | Leetcode Solution (2026)

    Single Number LeetCode Solution C++ : Learn the most efficient way to solve the Single Number problem on LeetCode using C++ and the XOR bitwise operator. Understand time complexity, code explanation, and why this approach works.

    Introduction of Single Number LeetCode Solution C++

    Looking for an efficient Single Number LeetCode Solution in C++? You’re in the right place!

    The Single Number problem is one of the most popular coding interview questions on platforms like LeetCode and helps test your understanding of bit manipulation.

    Let’s dive in and see how you can solve it in linear time and constant space.

    Problem Statement: Single Number

    LeetCode 136. Single Number

    Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

    You must implement a solution with a linear runtime complexity and use only constant extra space.

    Example:

    Input: nums = [4,1,2,1,2]
    Output: 4
    

    How to Solve the Single Number Problem

    At first glance, you might think of using:

    • Hash maps to count occurrences
    • Sorting the array and checking neighbors

    But both use extra space or more than O(n) time.

    Instead, there’s a beautiful trick using the XOR bitwise operator.

    Fantastic — let’s structure your blog to show progressive solutions to the Single Number problem:

    ✅ Brute-force solution (simplest but inefficient)
    ✅ Better (scalable) solution (using a map or set)
    ✅ Perfect solution (optimal XOR trick)

    1. Brute Force Solution (O(n²))

    Approach

    • For each number, count how many times it appears in the array.
    • Return the one that appears only once.

    Code

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int n = nums.size();
            for (int i = 0; i < n; i++) {
                int count = 0;
                for (int j = 0; j < n; j++) {
                    if (nums[i] == nums[j]) {
                        count++;
                    }
                }
                if (count == 1) {
                    return nums[i];
                }
            }
            return -1; // No single number found
        }
    };
    

    Complexity

    • Time: O(n²)
    • Space: O(1)

    ✅ Easy to understand
    ❌ Slow for large arrays

    2. Better Solution Using Hash Map (O(n))

    Approach

    • Use a hash map to count frequencies.
    • Return the number whose frequency is 1.

    Code

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            unordered_map<int, int> freq;
            for (int num : nums) {
                freq[num]++;
            }
            for (auto& pair : freq) {
                if (pair.second == 1) {
                    return pair.first;
                }
            }
            return -1;
        }
    };
    

    Complexity

    • Time: O(n)
    • Space: O(n)

    ✅ Linear time
    ❌ Extra space required

    3. Perfect Solution Using XOR (O(n), O(1))

    Recall these properties of XOR (^):

    • a ^ a = 0 (a number XOR itself is zero)
    • a ^ 0 = a
    • XOR is commutative and associative (order doesn’t matter)

    So if every number appears twice, XOR-ing all numbers cancels out the pairs:

    a ^ a ^ b = 0 ^ b = b
    

    Hence, the Single Number remains after XOR-ing all numbers.

    C++ Code – Single Number LeetCode Solution

    Here’s the optimized solution in C++ that you provided:

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
    
            int result = 0;
            for (int num : nums) {
                result ^= num;
            }
            return result;
        }
    };
    

    Step-by-Step Code Explanation

    Let’s break it down line by line.

    Line 1

    class Solution {
    

    Defines a class named Solution as required by LeetCode’s online judge.

    Line 2

    public:
    

    Marks methods as accessible outside the class.

    Line 3

    int singleNumber(vector<int>& nums) {
    
    • Defines a function singleNumber
    • Takes a reference to a vector of integers nums
    • Returns an int

    Line 4

    int result = 0;
    
    • Initialize result to 0.
    • This variable will hold the XOR of all numbers.

    Line 5

    for (int num : nums) {
        result ^= num;
    }
    
    • Loops through each integer in the array nums.
    • XORs it with result.
    • Duplicate numbers cancel each other out.
    • Only the single number remains.

    Example trace for [4,1,2,1,2]:

    0 ^ 4 = 4
    4 ^ 1 = 5
    5 ^ 2 = 7
    7 ^ 1 = 6
    6 ^ 2 = 4
    

    So the single number is 4.

    Line 8

    return result;
    

    Returns the unique number found.

    Time and Space Complexity

    ✅ Time Complexity: O(n)
    ✅ Space Complexity: O(1)

    This solution is optimal and easily fits the problem’s constraints.

    Summary

    SolutionTimeSpace
    Brute ForceO(n²)O(1)
    Hash MapO(n)O(n)
    XOR (Optimal)O(n)O(1)

    Python Solution

    Focus Keyword: Single Number LeetCode Solution Python

    class Solution:
        def singleNumber(self, nums):
            result = 0
            for num in nums:
                result ^= num
            return result
    

    Explanation:

    • Initialize result = 0.
    • XOR each element into result.
    • Pairs cancel out; single number remains.

    ✅ Time Complexity: O(n)
    ✅ Space Complexity: O(1)

    Java Solution

    Focus Keyword: Single Number LeetCode Solution Java

    class Solution {
        public int singleNumber(int[] nums) {
            int result = 0;
            for (int num : nums) {
                result ^= num;
            }
            return result;
        }
    }
    

    Explanation:

    • result starts at 0.
    • For each num in array, XOR it with result.
    • The unique number remains after all XORs.

    ✅ Time Complexity: O(n)
    ✅ Space Complexity: O(1)

    JavaScript Solution

    Focus Keyword: Single Number LeetCode Solution JavaScript

    var singleNumber = function(nums) {
        let result = 0;
        for (let num of nums) {
            result ^= num;
        }
        return result;
    };
    

    Explanation:

    • result initialized as 0.
    • Loop through nums.
    • XOR all numbers together.
    • Duplicate numbers cancel out, leaving the single number.

    ✅ Time Complexity: O(n)
    ✅ Space Complexity: O(1)

    Advantages of XOR Approach

    • No extra data structures required
    • Runs in linear time
    • Simple and elegant logic

    If you’re preparing for coding interviews, knowing this XOR trick can save you crucial time!

    🔗 Related LeetCode Problems

    Conclusion

    The XOR trick is a brilliant way to solve the Single Number problem efficiently in C++. Understanding how XOR cancels out duplicate numbers is essential for solving similar problems in coding interviews.

    FAQ – Single Number LeetCode Solution

    Q1. What is the Single Number problem on LeetCode?

    The Single Number problem on LeetCode asks you to find the only integer in an array that appears exactly once, while all other integers appear twice. You must solve it in linear time and with constant space complexity.

    Q2. How does the XOR trick help solve the Single Number problem?

    The XOR operator cancels out identical numbers because a ^ a = 0. When you XOR all numbers in the array, duplicates cancel each other, leaving only the unique number behind.

    Q3. What is the time complexity of the XOR solution for Single Number?

    The XOR solution runs in O(n) time, where n is the number of elements in the array.

    Q4. What is the space complexity of the XOR solution for Single Number?

    It uses O(1) space because you only store a single integer result, regardless of the input size.

    Q5. Can the Single Number problem be solved without bit manipulation?

    Yes, but less efficiently. You could use a hash map to count occurrences or sort the array and check neighbors. However, these methods either use extra space or exceed O(n) time complexity.

    Q6. Can the Single Number problem be solved in Python, Java, or JavaScript?

    Absolutely! The same XOR logic works in Python, Java, C++, JavaScript, and many other languages. It’s language-agnostic because XOR is a universal bitwise operation.

    Q7. Is the XOR method safe for negative numbers?

    Yes! XOR works on the bit-level representation of integers, so it handles negative numbers correctly.

    Q8. What LeetCode problems are similar to Single Number?

    • Single Number II (LeetCode 137) – Find the number appearing only once when every other appears three times.
    • Single Number III (LeetCode 260) – Find two numbers appearing once when every other appears twice.

    Q9. Why can’t I just sort the array to solve Single Number?

    While sorting works, it’s O(n log n) time, which doesn’t meet the problem’s linear time requirement. The XOR method is faster and uses constant space.

    Q10. Is Single Number a common coding interview question?

    Yes! The Single Number problem is frequently asked in coding interviews because it tests knowledge of bit manipulation, time complexity, and space optimization.