embeddedprep.com

Category: Coding Interview Preparation

  • How Stack Grows and Shrinks | Master Beginner-Friendly Guide with Examples (2026)

    How stack grows and shrinks explained with real-life examples and C code. Learn stack memory growth and shrinkage in an easy beginner-friendly way.

    A Real-Life Story to Understand the Stack

    Imagine you are in a restaurant kitchen. The chef keeps plates stacked one over another:

    • When a new customer order comes, the chef adds a new plate on top of the pile.
    • When an order is served, the chef removes the top plate first.

    The chef never touches the plates at the bottom until the top ones are removed. This is exactly how the stack in memory works when your program runs.

    • Every new function call is like placing a new plate on the stack (the stack grows).
    • When the function finishes, it’s like removing that plate (the stack shrinks).

    When learning memory management in programming, one of the most important concepts is the stack. Many beginners hear terms like stack grows and stack shrinks but find them confusing. This article explains the concept in a clear, step-by-step, beginner-friendly way, so you understand how the stack works in real programs.

    What is the Stack?

    The stack is a special area of memory used by programs to keep track of function calls, local variables, and return addresses. Think of it as a pile of plates:

    • You add a new plate on top (push).
    • You remove the top plate when it’s no longer needed (pop).

    This “last-in, first-out” (LIFO) behavior makes the stack very efficient.

    How the Stack Grows

    The stack grows when:

    1. A new function is called.
    2. Local variables are created inside that function.
    3. Temporary data (like function arguments or return addresses) are stored.

    Example in C:

    #include <stdio.h>

void displayNumber(int x) {
    int y = x + 5;  // local variable stored on the stack
    printf("Value: %d\n", y);
}

int main() {
    displayNumber(10);  // stack grows here
    return 0;
}
    • When main() calls displayNumber(10), memory for x and y is added to the stack.
    • This is called stack frame allocation.

    So, each function call creates a new stack frame, and the stack grows downward in memory (on most systems).

    How the Stack Shrinks

    The stack shrinks when:

    1. A function finishes execution.
    2. Its local variables and temporary data are no longer needed.
    3. The system pops the function’s stack frame, releasing memory automatically.

    Continuing with the example above:

    • After displayNumber(10) finishes, the memory used by x and y is removed from the stack.
    • The stack pointer moves back, and the program returns to main().

    This process is automatic — the programmer doesn’t need to free stack memory manually.

    Why Understanding Stack Grows and Shrinks is Important

    1. Avoiding Stack Overflow – If too many functions are called without finishing, the stack memory can run out, causing a stack overflow error.
    2. Debugging Programs – Many runtime errors can be understood by analyzing the stack.
    3. Efficient Programming – Understanding how the stack works helps in writing better functions and managing recursion.

    Key Differences Between Stack Stack Grows and Shrinks

    AspectStack GrowthStack Shrinkage
    When it happensOn function call or variable allocationOn function return or variable release
    Memory effectIncreases stack sizeDecreases stack size
    Programmer controlAutomatic, managed by systemAutomatic, managed by system

    Example Code: How the Stack Stack Grows and Shrinks

    //code for Stack Grows and Shrinks
#include <stdio.h>

void thirdFunction() {
    int c = 30;  // local variable stored on stack
    printf("➡ Entering thirdFunction (stack grows, variable c = %d)\n", c);
    printf("⬅ Leaving thirdFunction (stack shrinks)\n");
}

void secondFunction() {
    int b = 20;  // local variable stored on stack
    printf("➡ Entering secondFunction (stack grows, variable b = %d)\n", b);

    thirdFunction();  // stack grows again

    printf("⬅ Leaving secondFunction (stack shrinks)\n");
}

void firstFunction() {
    int a = 10;  // local variable stored on stack
    printf("➡ Entering firstFunction (stack grows, variable a = %d)\n", a);

    secondFunction();  // stack grows again

    printf("⬅ Leaving firstFunction (stack shrinks)\n");
}

int main() {
    printf("➡ Program started (main function stack frame created)\n");

    firstFunction();  // stack grows again

    printf("⬅ Back to main (stack shrinks after all calls)\n");
    return 0;
}

    Expected Output for Stack Grows and Shrinks

    When you run the program, the output shows clearly how the stack grows when a function is entered and shrinks when the function finishes:

    ➡ Program started (main function stack frame created)
➡ Entering firstFunction (stack grows, variable a = 10)
➡ Entering secondFunction (stack grows, variable b = 20)
➡ Entering thirdFunction (stack grows, variable c = 30)
⬅ Leaving thirdFunction (stack shrinks)
⬅ Leaving secondFunction (stack shrinks)
⬅ Leaving firstFunction (stack shrinks)
⬅ Back to main (stack shrinks after all calls)

    How This Code Matches the Story

    • Just like stacking plates in a kitchen:
      • thirdFunction() is the top plate → it must be removed first.
      • Then secondFunction() → removed after third.
      • Finally firstFunction() → removed last.

    That’s why the stack follows a Last-In, First-Out (LIFO) order.

    Advantages of Stack Grows and Shrinks

    1. Automatic Memory Management – The stack grows and shrinks automatically without programmer effort.
    2. Fast Execution – Stack operations (push/pop) are very efficient compared to heap allocations.
    3. Predictable Behavior – Memory is released as soon as a function returns, making the program more reliable.
    4. Good for Function Calls – Ideal for storing local variables, return addresses, and function arguments.

    Disadvantages of Stack Grows and Shrinks

    1. Limited Size – Stack memory is small compared to heap memory. Too many nested function calls may cause stack overflow.
    2. Temporary Lifetime – Data in the stack is destroyed once the function ends, so it cannot be shared globally.
    3. No Manual Control – Unlike heap memory, you cannot manually manage stack memory size.
    4. Recursive Risks – Deep recursion can quickly exhaust stack space.

    Applications of Stack in Programming

    1. Function Call Management – Each function call creates a new stack frame that stores local variables and return addresses.
    2. Recursion – The stack allows recursive functions to keep track of multiple calls at once.
    3. Expression Evaluation – Compilers and interpreters use stacks for evaluating arithmetic expressions.
    4. Backtracking Algorithms – Stacks are used in solving mazes, puzzles, and depth-first search (DFS).
    5. Interrupt Handling in OS – Operating systems use the stack to save the current state before switching tasks.

    Real-World Example

    • Web Browsers → Use stacks for the Back/Forward navigation system.
    • Programming Languages → C, C++, Java, and Python rely heavily on stack growth/shrinkage during function calls.
    • Embedded Systems → Use stacks for managing tasks, interrupts, and low-level function calls efficiently.

    Frequently Asked Questions (FAQ) of Stack Grows and Shrinks

    1. What does it mean when the stack grows?

    Ans: The stack grows when a new function is called in a program. Each function call creates a stack frame that stores local variables, function arguments, and the return address. This increases the size of the stack.

    2. What does it mean when the stack shrinks?

    Ans: The stack shrinks when a function finishes execution. Its stack frame is removed, freeing up memory automatically. This is why you don’t need to manually release stack memory.

    3. Does the stack always grow downward in memory?

    Ans: On most systems, the stack grows downward (from higher memory addresses to lower ones). However, the actual direction depends on the system architecture and compiler.

    4. What is a stack overflow?

    Ans: A stack overflow happens when the stack grows too large and exceeds the memory limit. This usually occurs with very deep recursion or too many nested function calls.

    5. How is stack growth different from heap growth?

    Ans: Stack growth is automatic and temporary. It happens when functions are called and shrinks when they return.
    Heap growth happens when memory is allocated dynamically (using malloc in C or new in C++). Heap memory must be managed manually by the programmer.

    6. Why is understanding stack growth and shrinkage important?

    Ans: It helps beginners avoid common errors like stack overflow, improves debugging skills, and builds a strong foundation for understanding function calls, recursion, and memory management in C, C++, and embedded systems.

    You can also Visit other tutorials of Embedded Prep 

  • Circular Linked List | Master Interview ready Guide (2026)

    Last Updated: 31 Aug, 2025

    Beginner-friendly guide to Circular Linked List. Learn types, structure, advantages, disadvantages, applications, and C code examples. When learning data structures, most beginners start with arrays and linked lists. Among different types of linked lists, the Circular Linked List is an important concept that offers flexibility in memory management and traversal. In this article, we will explain what a circular linked list is, its types, advantages, and real-world applications in a beginner-friendly way.

    A Circular Linked List is a special type of linked list in which the last node is connected back to the first node, forming a closed loop. Unlike arrays, circular linked lists are dynamic in nature, meaning they can grow or shrink during program execution.

    What is a Circular Linked List?

    A Circular Linked List is a type of linked list where the last node points back to the first node instead of pointing to NULL. This creates a circular connection, allowing continuous traversal of the list in a loop.

    Unlike a Singly Linked List, which ends at NULL, or a Doubly Linked List, which has two pointers, the circular linked list makes navigation seamless without an endpoint.

    Types of Circular Linked List

    Singly Circular Linked List

    A singly circular linked list is just like a normal singly linked list, but with one small twist. In this structure, every node has two parts: the data it stores and a pointer to the next node. The difference is that the last node doesn’t point to NULL; instead, it connects back to the very first node. This creates a circular chain where you can keep moving forward from one node to the next without ever reaching an end. Imagine it like kids standing in a circle holding hands—if you keep walking around, you’ll return to the starting point. This kind of list is useful when you need to repeatedly go through data, such as in round-robin scheduling or playlist management in music players.

    Singly Circular Linked List
    Singly Circular Linked List

    Doubly Circular Linked List

    A doubly circular linked list is an advanced version of the circular linked list. In this structure, every node contains three parts: the data, a pointer to the next node, and another pointer to the previous node. Unlike a simple doubly linked list, the last node doesn’t end with NULL. Instead, its next pointer connects back to the first node, and the first node’s previous pointer links to the last node. This creates a complete circular chain where you can move forward or backward through the list without ever reaching an endpoint. You can think of it like a train running on a circular track—you can travel clockwise or counterclockwise and always come back to where you started. This makes doubly circular linked lists very handy in situations like navigation menus, music or video playlists, and simulations where movement in both directions is needed.

    Doubly Circular Linked List
    Doubly Circular Linked List

    Basic Structure of a Circular Linked List

    Here’s a simple structure in C language:

    struct Node {
    int data;
    struct Node* next;
};

    For a Doubly Circular Linked List, we add a previous pointer:

    struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

    What is Node Representation of Circular Linked List

    C++ Example (Node Class):

    class Node {
public:
    int data;
    Node* next;

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

    C Example (Struct):

    struct Node {
        int data;
        struct Node* next;
    };

    Operations on Circular Linked List

    1. Insertion
      • At the beginning
      • At the end
      • At a given position
    2. Deletion
      • From the beginning
      • From the end
      • From a given position
    3. Traversal
      • Visit all nodes continuously in a loop.

    Circular Linked List Implementations

    C++ Implementation of Circular Linked List

    #include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class CircularLinkedList {
private:
    Node* last;
public:
    CircularLinkedList() { last = nullptr; }

    void insertEnd(int value) {
        Node* newNode = new Node(value);
        if (last == nullptr) {
            last = newNode;
            last->next = last;
        } else {
            newNode->next = last->next;
            last->next = newNode;
            last = newNode;
        }
    }

    void display() {
        if (last == nullptr) return;
        Node* temp = last->next;
        do {
            cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != last->next);
        cout << "(back to start)" << endl;
    }
};

int main() {
    CircularLinkedList cll;
    cll.insertEnd(10);
    cll.insertEnd(20);
    cll.insertEnd(30);
    cll.display();
    return 0;
}

    Output:

    10 -> 20 -> 30 -> (back to start)

    Java Implementation of Circular Linked List

    class Node {
    int data;
    Node next;

    Node(int value) {
        data = value;
        next = null;
    }
}

class CircularLinkedList {
    private Node last;

    CircularLinkedList() {
        last = null;
    }

    void insertEnd(int value) {
        Node newNode = new Node(value);
        if (last == null) {
            last = newNode;
            last.next = last;
        } else {
            newNode.next = last.next;
            last.next = newNode;
            last = newNode;
        }
    }

    void display() {
        if (last == null) return;
        Node temp = last.next;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != last.next);
        System.out.println("(back to start)");
    }

    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        cll.insertEnd(10);
        cll.insertEnd(20);
        cll.insertEnd(30);
        cll.display();
    }
}

    Output:

    10 -> 20 -> 30 -> (back to start)

    Python Implementation of Circular Linked List

    class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.last = None

    def insert_end(self, value):
        new_node = Node(value)
        if self.last is None:
            self.last = new_node
            self.last.next = self.last
        else:
            new_node.next = self.last.next
            self.last.next = new_node
            self.last = new_node

    def display(self):
        if self.last is None:
            return
        temp = self.last.next
        while True:
            print(temp.data, end=" -> ")
            temp = temp.next
            if temp == self.last.next:
                break
        print("(back to start)")

# Example usage
cll = CircularLinkedList()
cll.insert_end(10)
cll.insert_end(20)
cll.insert_end(30)
cll.display()

    Output:

    10 -> 20 -> 30 -> (back to start)

    JavaScript Implementation of Circular Linked List

    class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class CircularLinkedList {
  constructor() {
    this.last = null;
  }

  insertEnd(value) {
    let newNode = new Node(value);
    if (this.last === null) {
      this.last = newNode;
      this.last.next = this.last;
    } else {
      newNode.next = this.last.next;
      this.last.next = newNode;
      this.last = newNode;
    }
  }

  display() {
    if (this.last === null) return;
    let temp = this.last.next;
    let result = "";
    do {
      result += temp.data + " -> ";
      temp = temp.next;
    } while (temp !== this.last.next);
    console.log(result + "(back to start)");
  }
}

// Example usage
let cll = new CircularLinkedList();
cll.insertEnd(10);
cll.insertEnd(20);
cll.insertEnd(30);
cll.display();

    Output:

    10 -> 20 -> 30 -> (back to start)

    Advantages of Circular Linked List

    • Efficient Memory Usage – No need for a NULL pointer.
    • Continuous Traversal – Useful in applications where we need to cycle through data repeatedly.
    • Dynamic Size – Unlike arrays, circular linked lists can grow and shrink easily.
    • Queue Implementation – Particularly helpful in designing circular queues.
    • Saves memory – No NULL pointer
    • Uniform traversal in a loop.

    Disadvantages of Circular Linked List

    • Complex Implementation – Requires extra care while inserting and deleting nodes.
    • Infinite Loops – Careless traversal may lead to infinite looping.
    • More Memory Per Node – Extra pointers (in the case of a doubly circular linked list).
    • Requires more memory in case of doubly circular list.

    Applications of Circular Linked List

    • Operating Systems – Used in CPU scheduling (Round-Robin Scheduling).
    • Music or Video Playlists – When songs or videos repeat in a loop.
    • Multi-Player Games – Switching turns between players in a continuous cycle.
    • Data Buffers – Implementing circular queues and memory buffers.
    • Traffic Systems → Repeated light cycles.

    Traversing a Circular Linked List in C

    #include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void traverse(struct Node* head) {
    struct Node* temp = head;
    if (head != NULL) {
        do {
            printf("%d -> ", temp->data);
            temp = temp->next;
        } while (temp != head);
    }
}

int main() {
    struct Node* head = malloc(sizeof(struct Node));
    struct Node* second = malloc(sizeof(struct Node));
    struct Node* third = malloc(sizeof(struct Node));

    head->data = 10; head->next = second;
    second->data = 20; second->next = third;
    third->data = 30; third->next = head;

    traverse(head);
    return 0;
}

    Output:

    10 -> 20 -> 30 ->

    Insertion at the End of Circular Linked List

    #include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

void insertEnd(Node*& last, int value) {
    Node* newNode = new Node(value);

    if (last == nullptr) {
        last = newNode;
        last->next = last; // Self loop
    } else {
        newNode->next = last->next;
        last->next = newNode;
        last = newNode;
    }
}

void display(Node* last) {
    if (last == nullptr) return;

    Node* temp = last->next;
    do {
        cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != last->next);
    cout << " (back to start)\n";
}

int main() {
    Node* last = nullptr;

    insertEnd(last, 10);
    insertEnd(last, 20);
    insertEnd(last, 30);

    display(last);
    return 0;
}

    Why Learn Circular Linked List?

    • It helps in CPU scheduling algorithms (Round Robin).
    • Useful in repeated task execution like music playlists, traffic signal management, and multiplayer games.
    • Provides constant time insertion at both ends.

    Difference Between Circular Linked List and Regular Linked List

    FeatureRegular Linked ListCircular Linked List
    Last NodePoints to NULLPoints to first node
    TraversalStops at NULLNever ends, continues in a loop
    Memory UsageHas a terminating pointerUtilizes memory efficiently
    ApplicationsBasic data storageScheduling, queues, buffers

    When to Use Circular Linked List Instead of Array?

    Use CaseArrayCircular Linked List
    Fixed size✅❌
    Dynamic growth❌✅
    Random access✅ O(1)❌ O(n)
    Continuous looping❌✅
    Insertion at beginning❌ O(n)✅ O(1)

    Circular Linked List Interview Questions

    Preparing for coding interviews? Here’s a categorized list of Circular Linked List interview questions suitable for beginners, intermediate learners, and experienced professionals.

    Beginner-Level Questions

    1. What is a Circular Linked List?
    2. How does a Circular Linked List differ from a regular Linked List?
    3. What are the types of Circular Linked Lists?
    4. Write the structure of a node in a Circular Singly Linked List.
    5. Write the structure of a node in a Circular Doubly Linked List.
    6. What are the advantages of Circular Linked Lists over arrays?
    7. List some real-world applications of Circular Linked Lists.
    8. What is the time complexity of insertion at the beginning of a Circular Linked List?
    9. What is the time complexity of deletion at the end of a Circular Linked List?
    10. Explain how traversal works in a Circular Linked List.

    Intermediate-Level Questions

    1. Why do we often maintain a pointer to the last node instead of the first node in Circular Linked Lists?
    2. Explain insertion at the beginning, end, and a specific position in a Circular Linked List.
    3. Explain deletion at the beginning, end, and a specific position in a Circular Linked List.
    4. How do you implement a Circular Queue using a Circular Linked List?
    5. How would you check if a linked list is circular?
    6. What is the difference between a Circular Singly Linked List and a Circular Doubly Linked List?
    7. Write pseudocode for traversing a Circular Linked List.
    8. How can you implement Round Robin Scheduling using a Circular Linked List?
    9. Compare time complexities of insertion and deletion in Circular Linked Lists vs Arrays.
    10. What challenges arise while debugging a Circular Linked List?

    Experienced-Level Questions

    1. How do you detect an infinite loop in a Circular Linked List?
    2. How would you reverse a Circular Linked List?
    3. How can a Circular Linked List be used to implement a deque (double-ended queue)?
    4. In which scenarios is a Circular Linked List better than a Doubly Linked List?
    5. How would you merge two Circular Linked Lists into one?
    6. Design an algorithm to split a Circular Linked List into two halves.
    7. How do you handle memory management issues in large Circular Linked Lists?
    8. What are the potential pitfalls in pointer manipulation when inserting nodes into a Circular Linked List?
    9. How does a Circular Linked List improve CPU scheduling performance?
    10. Design a Circular Linked List to handle a real-time system scenario (e.g., traffic light control).

    Conclusion

    A Circular Linked List is a powerful data structure for situations requiring continuous traversal and dynamic memory allocation. Though slightly more complex than singly linked lists, its applications in operating systems, games, and memory management make it worth learning.

    If you are a beginner, start by understanding the structure, then practice insertion, deletion, and traversal operations in circular linked lists. With time, you’ll find this data structure highly useful in real-world applications.

    If you are a beginner, start with circular singly linked lists and then move on to doubly circular linked lists. With practice, you’ll understand how this structure outperforms arrays and regular linked lists in certain scenarios.

    FAQs on Circular Linked List

    1.What is the main difference between singly and circular singly linked list?

    Ans: In singly linked list, traversal ends at NULL. In circular singly linked list, traversal loops back to the first node.

    2.Why is circular linked list used in OS scheduling?

    Ans: Because tasks can be executed in a continuous loop (Round Robin algorithm).

    3.Can we implement queues using circular linked list?

    Ans: Arrays are faster for random access, but circular linked lists are better for dynamic memory and looping tasks. Yes, circular linked lists are best suited for circular queues.

    4.Which is faster — array or circular linked list?

    Ans: Arrays are faster for random access, but circular linked lists are better for dynamic memory and looping tasks.

    5.Why is it better to keep a pointer to the last node instead of the first node in a Circular Linked List?

    Ans: Because insertion at the beginning and the end can be done in O(1) time without traversing the entire list.

    6.How do you detect an infinite loop in a Circular Linked List?

    Ans: By using the Floyd’s Cycle Detection Algorithm (Tortoise and Hare algorithm).

    7.What is the time complexity for insertion and deletion in Circular Linked List?

    Ans: Insertion at beginning/end → O(1)
    Insertion at specific position → O(n)
    Deletion at beginning/end → O(1)
    Deletion at specific position → O(n)

    8.What are the challenges in debugging a Circular Linked Lis

    Ans: Risk of infinite loops if termination conditions are not handled.
    Requires extra care in insertion/deletion to maintain circular structure.

    9.Compare Circular Linked List with Doubly Linked List in terms of memory usage and traversal.

    Ans: Circular Linked List saves memory by avoiding NULL pointers.
    Doubly Circular Linked List requires more memory but supports two-way traversal.

    10.How does a Circular Linked List improve CPU scheduling in an Operating System?

    Ans: In Round Robin Scheduling, processes are arranged in a circular linked list so the CPU can allocate time slices fairly to each process in a loop.

    You can also Visit other tutorials of Embedded Prep 

    Circular Linked List
    Circular Linked List Master Interview ready Guide (2025)

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