Tag: Bitwise Operations

  • 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.

  • Little Endian and Big Endian : A Complete Guide (2026)

    Little Endian and Big Endian

    Little Endian and Big Endian : Understand the key differences in endianness, how they affect data storage, and why it matters in computer architecture and network communication.

    Imagine this: You’re debugging your first embedded C program on a microcontroller. Everything seems fine — the code compiles, runs, and even prints numbers. But suddenly, your integer values look weird. Instead of 0x12345678, you see 0x78563412.

    You double-check your logic, your memory addresses, even your compiler settings — everything looks perfect. Frustration builds up until your senior calmly asks,

    “Did you check your system’s endianness?”

    That’s the moment it clicks — you’ve just met one of the most fascinating yet confusing concepts in computer architecture: Endianness — the way computers store and read bytes in memory.

    This guide will cover Little Endian and Big Endian The difference between Little Endian and Big Endian , Their advantages and disadvantages , Use cases in processors, networking, and embedded systems , How to detect and handle endianness in programming

    Little Endian and Big Endian : Endianness is an essential concept in computer architecture that determines the byte order used for storing multi-byte data in memory. Different systems use different formats, which can cause compatibility issues when transferring data between processors, file formats, or networks.

    By the end, you’ll have a solid understanding of endianness and how it impacts system design.

    What is Endianness?

    Endianness refers to how bytes are arranged in memory when storing multi-byte data types like integers and floating-point numbers.

    There are two primary types of endianness:

    • Little-endian: The least significant byte (LSB) is stored first (lowest memory address).
    • Big-endian: The most significant byte (MSB) is stored first (lowest memory address).

    Understanding endianness is crucial in system programming, embedded systems, and network communication.

    Little Endian: Explained

    In a little-endian system, the least significant byte (LSB) is stored first, meaning lower memory addresses contain smaller parts of the number.

    Example on Little Endian and Big Endian

    Let\’s store a 32-bit hexadecimal number 0x12345678 in little-endian format:

    Memory AddressValue
    000x78
    010x56
    020x34
    030x12

    Common Little Endian Processors | Little Endian and Big Endian

    • Intel x86/x64 processors
    • ARM (default mode)
    • AMD architectures

    Advantages of Little Endian

    Easier arithmetic operations, as the LSB is stored first
    Common in modern processors, making it widely used

    Disadvantages of Little Endian

    Less intuitive for humans, as numbers appear reversed
    Requires byte-swapping when working with big-endian systems

    What is Big Endian : Explained

    Big Endian : In a big-endian system, the most significant byte (MSB) is stored first, making it more natural for humans to read.

    Example

    Storing 0x12345678 in big-endian format:

    Memory AddressValue
    000x12
    010x34
    020x56
    030x78

    Common Big Endian Processors

    IBM PowerPC
    Motorola 68K
    SPARC architectures

    Advantages of Big Endian

    More intuitive for human reading, as numbers are stored in their natural order
    Used in network protocols, such as TCP/IP

    Disadvantages of Big Endian

    Less efficient for arithmetic operations, since LSB is stored last
    Less common in modern CPUs, requiring conversions

    Little Endian and Big Endian: Key Differences

    FeatureLittle EndianBig Endian
    Byte OrderLSB firstMSB first
    Common ProcessorsIntel, AMD, ARMPowerPC, SPARC, Motorola
    Network UseNo (requires conversion)Yes (network byte order)
    Arithmetic OperationsEasierHarder
    ReadabilityLess intuitiveMore intuitive

    💛 Support Embedded Prep

    If you find our tutorials helpful and want to support our mission of sharing high-quality embedded system knowledge, you can contribute by buying us a coffee. Every small contribution helps us keep creating valuable content for learners like you. ☕

    Thank you for your support — it truly keeps Embedded Prep growing. 💻✨

    How to Check Endianness in Programming?

    Little Endian and Big Endian : Most programming languages provide ways to detect endianness.

    Detecting Endianness in C/C++ | Little Endian and Big Endian

    #include <stdio.h>
    int main() {
        unsigned int num = 1;
        char *ptr = (char*)&num;
        if (*ptr == 1)
            printf(\"Little Endian\\n\");
        else
            printf(\"Big Endian\\n\");
        return 0;
    }
    

    Checking Endianness in Python | Little Endian and Big Endian

    import sys
    print(\"Little Endian\" if sys.byteorder == \"little\" else \"Big Endian\")
    

    Byte Swapping in C | Little Endian and Big Endian

    To convert between endian formats:

    #include <stdint.h>
    #include <stdio.h>
    uint32_t swap_endian(uint32_t num) {
        return ((num >> 24) & 0xFF) | ((num >> 8) & 0xFF00) |
               ((num << 8) & 0xFF0000) | ((num << 24) & 0xFF000000);
    }
    

    Endianness in Networking (Network Byte Order)

    Most network protocols (like TCP/IP) use big-endian format (also called \”network byte order\”).

    Converting to Network Byte Order in C

    #include <arpa/inet.h>
    uint32_t ip = htonl(0x12345678); // Converts to network byte order (big-endian)
    

    Significance of Most Significant Byte (MSbyte) in Little and Big Endian

    When dealing with computer architecture, memory storage, and data representation, endianness plays a crucial role in how multi-byte data is organized. The Most Significant Byte (MSbyte) is a key component in this representation, and its position varies based on whether the system follows Little Endian or Big Endian format.

    1. What is the Most Significant Byte (MSbyte)?

    The MSbyte is the byte containing the most significant (largest) part of the data. In a multi-byte number, it holds the highest order bits. For example:

    • In a 4-byte integer:
      • 0x12345678 → 0x12 is the MSbyte.
    • In a 2-byte value:
      • 0xABCD → 0xAB is the MSbyte.

    2. Little Endian vs. Big Endian Representation

    Little Endian

    • In Little Endian systems, the least significant byte (LSbyte) is stored first in memory, and the most significant byte is stored last.
    • Memory order: Value: 0x12345678 Memory: 78 56 34 12
    • The MSbyte (0x12) is placed at the highest memory address.

    ✅ Advantages of Little Endian:

    • Simpler arithmetic operations, as the least significant part comes first.
    • Commonly used in x86 and ARM architectures.

    Big Endian

    • In Big Endian systems, the most significant byte is stored first, followed by the less significant bytes.
    • Memory order: Value: 0x12345678 Memory: 12 34 56 78
    • The MSbyte (0x12) is placed at the lowest memory address.

    ✅ Advantages of Big Endian:

    • Easier to read hex dumps and memory representations (since the bytes are in the same order as the actual value).
    • Used in network protocols (TCP/IP) and certain RISC architectures.
    Little Endian and Big Endian : A Complete Guide (2025)
    Little Endian and Big Endian : A Complete Guide (2025)

    3. Importance of MSbyte in Endian Representation

    A. Data Interpretation

    The position of the MSbyte determines how a system reads and interprets multi-byte data.

    • On a Little Endian system, the MSbyte is at the higher address, which can lead to potential issues if interpreted incorrectly on a Big Endian system.
    • Example:
      • Value: 0x1234
      • Little Endian memory: 34 12
      • Big Endian memory: 12 34
      • Incorrect interpretation due to endianness mismatch can lead to data corruption or unexpected values.

    B. Communication Protocols

    In network protocols, such as TCP/IP, Big Endian (also called network byte order) is used.

    • When sending data between Big Endian and Little Endian systems, the MSbyte’s position must be properly adjusted to avoid communication errors.

    C. Performance and Efficiency

    • On Little Endian systems, operations like arithmetic and bitwise shifts are more efficient since they start processing from the least significant side.
    • On Big Endian systems, reading memory in a human-readable format is straightforward due to the MSbyte-first ordering.

    4. Pitfalls and Compatibility Issues

    • Cross-platform incompatibility: When moving binary data between Little Endian and Big Endian systems, incorrect handling of the MSbyte can lead to incorrect values.
    • File formats and serialization:
      • Some file formats specify endianness, while others do not.
      • Improper handling of the MSbyte can result in corrupted data when interpreting file headers.

    5. Conclusion on Little Endian and Big Endian

    The Most Significant Byte (MSbyte) plays a vital role in multi-byte data representation. Its position varies based on the endianness of the system:

    • In Little Endian, the MSbyte is stored last.
    • In Big Endian, the MSbyte is stored first.

    FAQ: Frequently Asked Questions | Little Endian and Big Endian

    1. Why is Endianness Important?

    Endianness affects data storage and transfer between different systems. It is critical for cross-platform compatibility.

    2. Which Endianness is Better?

    Neither is inherently better; little-endian is preferred in modern CPUs, while big-endian is used in networking.

    3. How Do I Convert Between Endianness?

    By byte-swapping, using built-in functions like htonl() and ntohl() in C or struct.pack() in Python.

    4. Does Endianness Affect Single-Byte Data?

    No, endianness only applies to multi-byte data types.

    5. What is Network Byte Order?

    Network protocols use big-endian (network byte order) for consistent data transfer between different systems.

    Top Interview Questions on Little Endian and Big Endian

    Now that you have a complete understanding of Little Endian and Big Endian, you are ready to confidently tackle related problems and ace interviews in one shot. Focus on mastering questions such as:

    • What is endianness, and why does it matter?
    • Explain the difference between little-endian and big-endian.
    • Which processors use little-endian vs. big-endian?
    • How would you check a system\’s endianness in C?
    • How does endianness affect network communication?
    • What is byte swapping, and when is it needed?
    • Why do network protocols use big-endian format?
    • How does endianness impact embedded systems?
    • What are real-world examples where endianness caused problems?
    • How do you handle endianness in cross-platform applications?

    Conclusion on Little Endian and Big Endian

    Endianness is a fundamental concept in computer architecture, networking, and embedded systems. Understanding it helps in writing cross-platform applications, debugging low-level software, and preventing data corruption.

    Thank you for exploring this Little Endian and Big Endian : A Complete Guide tutorials ! Stay ahead in embedded systems with expert insights, hands-on projects, and in-depth guides. Follow Embedded Prep for the latest trends, best practices, and step-by-step tutorials to enhance your expertise. Keep learning, keep innovating!

    You can also Visit other tutorials of Embedded Prep