33 Must Know CP Question

A small request:

If you find value in what we’re doing, please subscribe to our YouTube channel and share this initiative with others in your network. Together, we can build a stronger tech community. ❤️

1. Suppose you have an array with 11 digits. Five numbers each appear exactly twice, and one number appears only once. How can you find the single number without using any extra array or map, and with a time complexity of O(n)?

function singleNumber(nums) {
  let result = 0;
  for (let i = 0; i < nums.length; i++) {
    result ^= nums[i]; //bitwise XOR operation
  } 
  return result;
}

389. Find the Difference: You are given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position. Return the letter that was added to t.

Brute force Approach

class Solution {
public:
    char findTheDifference(string s, string t) {
        if (s.size() < 1)
            return t[0];

        unordered_map<char,int> mapping;

        for (int i = 0; i < t.size(); i++) {
            mapping[t[i]]++;
        }
        for (int i = 0; i < s.size(); i++) {
            mapping[s[i]]--;
        }

        for (auto it : mapping) {
            if (it.second != 0) {
                return it.first;
            }
        }

        return 'a';
    }
};

Optimal Approach

class Solution {
public:
    char findTheDifference(string s, string t) {
        s += t;
        int ans = 0;

        for(auto it : s ){
            ans ^= it;
        }
        return ans;            
    }
};

2. Reverse the array without any additional array! (Two Pointer Approach)

 int array[] = {1, 2, 3, 4, 5, 6, 7};
    int start = 0;
    int end = 6;

    while (start < end){ //  (Two Pointer Approach )
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
        start++;
        end--; 
    }

   for(auto it : array){
       cout << it << sp;
   }

3. Given a number. Find the sum of the digits of the number ?

int number = 123456;
    int count = 0;
    while (number > 0)
    {
        int digit = number % 10;
        count += digit;
        number = number / 10;
    }
    cout << count << endl;

4. Merge these two sorted arrays using one loop?

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr1[] = {0, 1, 2, 3, 4};
    int arr2[] = {3, 4, 6, 7, 9};
    
    int arr1Size = sizeof(arr1) / sizeof(arr1[0]);
    int arr2Size = sizeof(arr2) / sizeof(arr2[0]);
    
    int arr1Pointer = 0;
    int arr2Pointer = 0;
    
    vector<int>mergedArray;
    
    // Mergin Two Array with Comparison
    while(arr1Pointer < arr1Size && arr2Pointer < arr2Size){
        if(arr1[arr1Pointer] > arr2[arr2Pointer]){
            mergedArray.push_back(arr2[arr2Pointer]);
            arr2Pointer++;
        }
        else{
            mergedArray.push_back(arr1[arr1Pointer]);
            arr1Pointer++;
        }
    }
    // Add Leftover array 1 values
    for(int i = arr1Pointer ; i < arr1Size; i++){
        mergedArray.push_back(arr1[i]);
    }
    // Add Leftover array 2 values
    for(int i = arr2Pointer; i < arr2Size; i++){
        mergedArray.push_back(arr2[i]);
    }
    // Printing New Merged Array
    for(auto index : mergedArray){
        cout << index << " ";
    }
    
}

5. Find out which is the last /previous palindrome number of a given number. (Example: 20 is given, so 11 is the palindrome number) [Reverse a Number]

bool checkPalindrome(int n)
{
    int reverse = 0;
    int temp = n;
    while (temp != 0)
    {
        reverse = (reverse * 10) + (temp % 10);
        temp = temp / 10;
    }
    return (reverse == n);
}

void solve()
{
    int n;
    cin >> n;

    for (int i = n; i > 0; i--)
    {
        int temp = i;
        if (checkPalindrome(temp))
        {
            cout << "Last Palindrome : ";
            cout << temp << endl;
            break;
        }
    }
}

6. An array of letters from a-z is given. Find out the first non-repeated letter. (like array [A, B,V,C,A,C,V,P] is given, here B is the first non-repeated letter).

int firstUniqueChar(string s) {
    vector<int> count(26, 0);

    for (auto it : s) {
        count[it - 'a']++;
    }
    for (int i = 0; i < s.size(); i++) {
        if (count[s[i] - 'a'] == 1)
            return i;
    }
    return -1;
 }
 
int main() {
  string s = "abvcacvp";
  char ans = firstUniqueChar(s) + 'a';
  cout << ans;
}

7. Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

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

 class Solution {
  public:
      bool containsDuplicate(vector<int>& nums) {
          unordered_map<int,int> mp;
          for(auto i : nums) mp[i]++;
          
          bool flag = false;
          for(auto i : mp){
              if(i.second >= 2) return true;
          }
          return flag;
      }
  };

8. How To Check If a Value Is A Power Of 2 Or Not ?

bool isPowerOfTwo(int number){
    if(number == 0) return false;
    
    while(number%2 == 0){
        number /= 2;
    }
    
    if(number == 1) return false;
    else return true;
}
 
int main() {
    int value = 7 ;
    int powerOf2 = isPowerOfTwo(value); // Best Solution : powerOf2 = n & (n - 1);

    if (powerOf2 == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

9.1. Find All Substrings of a String

class Solution {
public:
    string substrings(string s) {
        int size = s.size();
        vector<string> substrings;

        for (int i = 0; i < size; i++) {
            string temp = "";
            for (int j = i; j < size; j++) {
                temp += s[j];
                substrings.push_back(temp);
            }
        }

        for(auto it : substrings){
            cout << it << endl;
        }
    }
};

9.2. Find Substring in a String

void solve()
{
    //* Sometimes you win, sometimes you learn..." - Good Wisher
    string s = "I am a student of Shahjalal University of Science and Technology";
    string sub = "student";

    int s_length = s.length();
    int sub_length = sub.length();
    bool found = false;
    int index = -1;

    for (int i = 0; i <= s_length - sub_length; i++)
    {
        bool match = true;
        for (int j = 0; j < sub_length; j++)
        {
            if (s[i + j] != sub[j])
            {
                match = false;
                break;
            }
        }
        if (match)
        {
            found = true;
            index = i;
            break;
        }
    }

    cout << index << endl; // index of first occurrence of sub in s

    if (found)
        cout << "Found" << endl;
    else
        cout << "Not Found" << endl;
}

Time Complexity: O(N * M)

Best Complexity: KMP Algorithm = O(N + M)

10. How do you swap two numbers without using a third variable

int a = 2, b = 3 ;
b = b + a; // now b is sum of both the numbers b = 5
a = b - a; // b - a = (b + a) - a = b (a is swapped) a = 5 - 2 = 3
b = b - a; // (b + a) - b = a (b is swapped) b = 5 - 3  = 2
// a = 3 , b = 2

11. GCD of Two Numbers

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

12. A string of 9 characters will be given. There will be 3 blocks of 3 characters in the String. each character will have a numerical value. you need to find the sum of the numerical values of each block and then finally concave the answer of each block and form a string. rw-x-r-rw Here r = 4 , x = 2, w = 1, - = 0 What is the answer?

void solve()
{
    //* Sometimes you win, sometimes you learn..." - Good Wisher
    //string str = "910209091";
    string str = "410204041";
    string ans = "";
    int temp = 0;

    for (int i = 1; i <= str.size(); i++)
    {
        if (i % 3 != 0)
        {
            temp += str[i - 1] - '0';
        }
        else
        {
            temp += str[i - 1] - '0';
            cout << temp << endl;

            string blockSum = "";
            
            // Corner Case : Sum > 9
            while (temp > 0)
            {
                int lastDigit = temp % 10;
                blockSum += lastDigit + '0';
                temp = temp / 10;
            }

            reverse(blockSum.begin(), blockSum.end());
            ans += blockSum;
            temp = 0;
        }
    }

    cout << ans << endl;
}

13. Write code to Calculate frequency of characters in a string

void solve()
{   //* Sometimes you win, sometimes you learn..." - Good Wisher
    string s;
    map<char, int> mp;
    cin >> s;

    for (int i = 0; i < s.size(); i++){
        mp[s[i]]++;
    }
    for (auto it : mp){
        cout << it.first << " = " << it.second << endl;
    }
}

14. Write code Check if the given string is Palindrome or not

void solve()
{   //* Sometimes you win, sometimes you learn..." - Good Wisher
    string s;
    cin >> s;

    bool palindrome = true;
    int first = 0;
    int last = s.length() - 1;

    while (first <= last) {
        if (s[first] != s[last]){
            palindrome = false;
            break;
        }
        first++;
        last--;
    }

    cout << palindrome << endl;
}

15. Find the Missing Number Between 1-N: 268. Missing Number

void solve(){
  //* Sometimes you win, sometimes you learn..." - Good Wisher
    int arr[] = { 1, 3, 7, 5, 6, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);

    int total = n * (n + 1) / 2; // Sum of n natural numbers
    for(int i = 0; i < n; i++)
    {
        total -= arr[i];
    }
    cout << total << endl;
}

16. Write code to Check if two strings are Anagram or not : 242. Valid Anagram

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

bool isAnagram(string s, string t)
{
    int countCharacter[26] = {0};

    for (auto index : s){
        countCharacter[index - 'a']++;
    }

    for (auto index : t){
        countCharacter[index - 'a']--;
    }
    
    for (auto index : countCharacter){
        if (index != 0){
            return false;
        }
    }

    return true;
}

17. 2nd Smallest Number in an Array

void solve(){
    //* Sometimes you win, sometimes you learn..." - Good Wisher
    int arr[] = {111, 13, 25, 9, 34, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    int first = INT_MAX, second = INT_MAX;
    for (int i = 0; i < n; i++){
        first = min(first, arr[i]);
    }

    for(int i = 0; i < n; i++){
        if(arr[i] != first){
            second = min(second, arr[i]);
        }
    }
    cout << "First : " << first << " Second : " << second << endl;
}

18. Write code of Perfect number (Divisors of a Number)

bool checkPerfectNumber(int num) {
        vector<int> divisors;
        
        for (int i = 1; i * i <= num; i++) {
            if (num % i == 0) {
                if (i == num / i) {
                    divisors.push_back(i);
                } else {
                    divisors.push_back(i);
                    divisors.push_back(num / i);
                }
            }
        }

        int sum = 0;
        for (auto it : divisors) {
            if(it == num) continue; // corner cae
            cout << it << endl;
            sum += it;
        }
        cout << "Sum = " <<sum <<endl;

        if(sum == num)
            return true;
        return false;
    }

19. Write a code for Binary Search

int binarySearch(int arr[], int n, int target) {
 int low = 0, high = n - 1;
 while (low <= high){
    int mid = (high + low) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] < target)
        low = mid + 1;
    else
        high = mid - 1;
}
return -1;

void solve()
{
    //* Sometimes you win, sometimes you learn..." - Good Wisher
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate the size of the array here
    int target = 3;

    int result = binarySearch(arr, n, target);
  
    if (result == -1)
        cout << "Element is not present in array" << endl;
    else
        cout << "Element is present at index " << result << endl;
}

20. Find non-repeating characters in a string

void solve()
{
    //* Sometimes you win, sometimes you learn..." - Good Wisher
    string s = "google";
    int n = s.size();

    map<char, int> count;

    for (int i = 0; i < n; i++)
    {
        count[s[i]]++;
    }

    for (auto it : count)
    {
        if (it.second == 1)
        {
            cout << it.first << endl;
        }
    }
}

21. Find Excel column name from a given column number

void solve(){
    //* Sometimes you win, sometimes you learn..." - Good Wisher
    int number;
    cin >> number;
    string s = "";

    while (number > 0){
        int rem = number % 26;
        if (rem == 0){
            s += 'Z';
            number = (number / 26) - 1;
        }
        else{
            s += (rem - 1) + 'A';
            number = number / 26;
        }
    }

    reverse(s.begin(), s.end());
    cout << s << endl;
}

22. Kth Largest Element in an Array

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        priority_queue<int> pq;
        
        // Max heap Default : Highest Value at Top
        for (int i = 0; i < nums.size(); i++) {
            pq.push(nums[i]); // inserting values in priority queue(Max Heap)
                              // Min Heap : use '-' Sign = -nums[i]
        }

        int temp = 0;
        while (!pq.empty()) {

            temp++;
            if (temp == k) {
                return pq.top(); //get the top value
            }

            cout << pq.top() << endl;
            pq.pop(); // if not remove the top value
        }

        return -1;
    }
};

Combining these two parts:

• The time complexity for inserting all elements into the priority queue (building the max-heap) is O(nlog⁡n)

• The time complexity for extracting the k-th largest element is O(klog⁡n).

Overall Time Complexity

Therefore, the overall time complexity of the code is: O(nlog⁡n+klog⁡n)

In the worst case, k is proportional to n making the complexity: k=== n

O(nlogn+nlogn) = O(nlogn)

23. Find a number is a prime or not

• Complexity: Root(N)

prime = true;
notPrime = false;

if( n == 1) return notPrime;

for(int i = 2 ; i*i <= n ; i++){
	if(n%i != o) return notPrime;
}

return prime;

• Complexity : N*Log(Log(N)

int countPrimes(int n) {
        bool prime[n+1];
        for(int i = 0; i <= n; i++) prime[i] = true;
        for (int p = 2; p * p <= n; p++) {
            if (prime[p] == true) {
               for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        int cnt = 0;
        for(int i = 2; i < n; i++) 
        {
            if(prime[i] == true) cnt++;
        }
        return cnt;
    }

24. Circular rotation of an array by K positions

void solve()
{
    //* Sometimes you win, sometimes you learn..." - Good Wisher
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    int ans[n] = {0};

    int k;
    cin >> k;

    k = k % n; // corner case : k > n

    for (int i = k; i < n; i++)
    {
        cout << arr[i] << sp;
    }

    for (int i = 0; i < k; i++)
    {
        cout << arr[i] << sp;
    }

    cout << endl;
}

25.Dynamic Programming: Climbing Stairs

class Solution {
public:
    int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

        vector<int> dp(n + 1);
        dp[0] = dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
};

26. Maximum Depth of Binary Tree

int maxDepth(TreeNode* root) {
    if (!root)
        return 0;
    int maxLeft = maxDepth(root->left);
    int maxRight = maxDepth(root->right);
    return max(maxLeft, maxRight) + 1;
}

27. Diameter of Binary Tree: The diameter of a binary tree is the length of the longest path between any two nodes in a tree.

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int longestPath = 0;
        diameter(root, longestPath);
        return longestPath;
    };

    int diameter(TreeNode* curr, int& longestPath) {
        if (curr == NULL)
            return 0;
        // Recursively calculate the diameter of left and right subtrees
        int left = diameter(curr->left, longestPath);
        int right = diameter(curr->right, longestPath);

        // Update the maximum diameter encountered so far
        longestPath = max(longestPath, left + right);

        // Return the depth of the current node
        return max(left, right) + 1;
    }
};

28. Linked List Cycle: Determine if the linked list has a cycle in it.

1. Use two pointers, walker and runner.

2. walker moves step by step. runner moves two steps at time.

3. if the Linked List has a cycle walker and runner will meet at some point.

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == NULL)
            return false;

        ListNode* walker = head;
        ListNode* runner = head;

        while (runner->next != NULL && runner->next->next != NULL) {
            walker = walker->next;
            runner = runner->next->next;
            if (walker == runner)
                return true;
        }
        return false;
    }
};

29. Middle of the Linked List: If there are two middle nodes, return the second middle node.

Each time, walker go 1 step while runner go 2 steps. When runner arrives at the end, walker will arrive right in the middle.

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* walker = head;
        ListNode* runner = head;

        // Check if runner reached endpoint
        while (runner && runner->next) {
            walker = walker->next;
            runner = runner->next->next;
        }

        return walker;
    }
};

30. Merge Two Sorted Lists

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == NULL)
            return list2;
        if (list2 == NULL)
            return list1;

        ListNode* mergeList = list1;

        if (list1->val > list2->val) {
            mergeList = list2;
            list2 = list2->next;
        } else {
            mergeList = list1;
            list1 = list1->next;
        }

        ListNode* currHead = mergeList;

        while (list1 && list2) {
            if (list1->val > list2->val) {
                currHead->next = list2;
                list2 = list2->next;
            } else {
                currHead->next = list1;
                list1 = list1->next;
            }
            currHead = currHead->next;
        }

        if (!list1) {
            currHead->next = list2;
        } else {
            currHead->next = list1;
        }

        return mergeList;
    }
};

31. Reverse Linked List

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *nextNode, *prevNode = NULL;
        while (head) {
            nextNode = head->next;
            head->next = prevNode;
            prevNode = head;
            head = nextNode;
        }
        return prevNode;
    }
};

32. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int currentMax = 0;
        int finalMax = INT_MIN;
        int start = 0, end = 0, tempStart = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (currentMax <= 0) {
                currentMax = nums[i];
                tempStart = i;
            } else {
                currentMax += nums[i];
            }
            if (currentMax > finalMax) {
                finalMax = currentMax;
                start = tempStart;
                end = i;
            }
        }
        
        // Print the Sub-array
        for (int i = start; i <= end; i++) {
            cout << nums[i] << " ";
        }

        return finalMax;
    }
};

33. Integer to Roman & Roman to Integer

Roman to Integer

class Solution {
public:
    int romanToInt(string s) {

        unordered_map<char, int> romanMap = {{'I', 1},   {'V', 5},   {'X', 10},
                                             {'L', 50},  {'C', 100}, {'D', 500},
                                             {'M', 1000}};
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            if (romanMap[s[i]] < romanMap[s[i + 1]]) {
                result -= romanMap[s[i]];
            } else {
                result += romanMap[s[i]];
            }
        }

        return result;
    }
};

Integer to Roman

class Solution {
public:
    string intToRoman(int num) {
        string roman = "";
        int storeInt[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string storeRoman[13] = {"M",  "CM", "D",  "CD", "C",  "XC", "L",
                               "XL", "X",  "IX", "V",  "IV", "I"};

        for (int i = 0; i < 13; i++) {
            while (num >= storeInt[i]) {
                roman += storeRoman[i];
                num -= storeInt[i];
            }
        }

        return roman;
    }
};