problem-solving-dsa

Problem Solving with Data Structures & Algorithms.

---

Project maintained by Ch-sriram Hosted on GitHub Pages — Theme by mattgraham

Solving problems, one step at a time 🤓

I’ve created this repository for my own reference and practice purposes. If you come across this repository, feel free to explore, scrutinize and comment on my solutions, or just help yourself pondering about my code.

I like a lot of languages (I’m language agnostic), but I prefer to write code in C/C++ & sometimes in Java, Python & JavaScript.

NOTE: The code is in the form of GitHub Gists and therefore there is no code inside the repo.

Resources 📚📖

• General Resources

  • MAXimal :: algo
  • Vivekanand Khyade’s YouTube Channel
  • Tushar Roy’s YouTube Channel
  • Amazing Blog Resource on Codeforces
  • Explanations of Interview Questions on iDeserve

• Mathematics

  • Finding Trailing Zeros in Factorial of a Number
  • Euclidean Algorithm to find GCD
  • Extended Euclid’s Algorithm to find Inverse Modulo
  • List of Prime Numbers up to 1,000,000,000,000

Contents ©

• In each section, the list of problems (along with their solutions) are ordered in terms of their difficulty level from top to bottom.
• Number of $’s signify the importance of the data-structure/algorithm in question. $$ < $$$ < $$$$ < $$$$$ < $$$$$$ in terms of importance.
• In the commits, the one with the difficulty and a + sign are worth going through because those problems introduce a new concept/trick altogether. Example: We’ve the following commit: Two Numbers with Odd Occurrences (Easy+) — we can see that it has Easy+, which means that problem difficulty is easy, but it is tricky to understand, and also, there’s a concept (or concept refresher) related to the particular problem.

Bit Manipulation 0️⃣1️⃣

1. Find First Set Bit: Solution in C++
2. Rightmost Different Bit: Solution in C++
3. Given an integer N, find 2^N: Solution in C++
4. Given X^th & Y^th bit positions, WAF to create a number where X^th & Y^th bit are set: Solution in C++
5. Check K-th bit is Set or Not: Solution in C++ (v1) & Solution in C++ (v2)
6. Given an integer - N, count the number of set bits in N: Solution-1 in C++ & Solution-2 in C++ $$
7. Check if given ‘N’ is Power of 2: Solution in C++ [logarithmic time] & Solution in C++ [constant time]
8. Given an integer N, find its binary representation: Solution in C++
9. Exceptionally Odd — Print the number which occurs odd number of times in an array where every other number occurs even number of times: Solution in C++
10. Bit Difference — Given two integers A & B, find the number of bits that need to be flipped in B to convert it to A: Solution in C++ (v1) & Solution in C++ (v2)
11. Given an unsigned 32-bit integer N, reverse the bits in the binary representation of the integer, and print the new integer formed: Solution in C++
12. Swap All Odd & Even Bits: Solution in C++ (v1) & Solution in C++ (v2)
13. Number is Sparse or Not — Sparseness Property states that “Given Number Should NOT contain any consecutive Set Bits”: Solution in C++
14. Maximum AND Value — find the Maximum AND Value generated by any pair of elements from the array of size N: Solution in C++ $$
15. Two Numbers w. Odd Occurrences: Solution in C++ $$
16. Given integers A & N, compute A^N: Naive Solution in C++: O(N) & Optimal Solution in C++ (fast-exponentiation): O(log N) $$
17. Given an array of unique integer elements, print all the subsets of the given array in lexicographical order [O(2^N)] :Solution in C++ $$
18. Given N, Count Total Set Bits from [1, N]: Solution in C++ [logarithmic time] $$$
19. Maximum XOR in Array — return an integer denoting the maximum XOR value in the given positive integer array: Solution in C++ $$$$$
20. Maximum XOR Subset — find the maximum XOR value of the elements from all the possible subsets of given positive integer array arr[]: Solution in C++ $$$$$

Math ➕➖✖➗

1. Given an integer N, find the number of trailing zeroes in N! [“N factorial”]: Solution in C++ (v1) & Solution in C++ (v2) $$
2. Quadratic Equation Roots — Given a quadratic equation in the form ax2 + bx + c. Find its roots: Solution in C++
3. Digits in Factorial — Given an integer N, find the number of digits in N!: Solution in C++ $$
4. Given two integers A and B, find their GCD & LCM: Solution in C++ (v1) & Solution in C++ (v2) $$
5. GCD of Array: Solution in C++ $$
6. Addition Under Modulo: Solution in C++
7. Series AP: Solution in C++
8. Given an array of size N, it contains all the numbers from 1 to N+1 inclusive, except one number. You have to find the missing number: Solution in C++
9. Check whether a given N is Prime or NOT: Solution in C++ (v1) & Solution in C++ (v2) $$
10. Exactly 3 Divisors: Solution in C++ $$
11. Count Primes in Range [O(N) for sieve of Eratosthenes + O(N) for prefix sum + O(Q * 1) for finding count of primes in given range for each query] [Total Time Complexity = O(2N + Q)]: Solution in C++ & Solution in Java $$$
12. Prime Generator (SPOJ) [O(R * X), where R = Max Range of 10^5 & X = sqrt(N)]: Solution in C++ $$
13. Largest Prime Factor: Solution in C++ $$
14. Kth Smallest Factor: Solution in C++ $$
15. GP Term: Solution in C++
16. Multiplicative Modular Inverse: Naive Solution in C++ $$$
17. Prime Generator (SPOJ: PRIME1) (Using Segmented Sieve): Solution in C++ $$$
18. Product of Primes: Solution in C++ (Bitmask Sieve) & Solution in C++ (Vector Sieve) $$$

Recursion 🔁🌪

1. Sum of N natural numbers: Solution in C++
2. Given an integer N, return the N^th integer in the Fibonacci Sequence: Naive Solution in C++ O(2^N)
3. Given N, return N! [“N factorial”]: Solution in C++
4. Towers of Hanoi/Brahma/Lucas: Solution in C++ $$
5. Given N pairs of parentheses, write a function to generate all combinations of well-formed valid parentheses: Solution in C++ $$$
6. Permutations of a given string: Solution in C++ $$$$

Sorting 1️⃣2️⃣3️⃣4️⃣5️⃣6️⃣7️⃣8️⃣9️⃣🔟

1. Bubble Sort Recursive Algorithm O(N²): Solution in C++
2. Insertion Sort Recursive Algorithm O(N²): Solution in C++ $$
3. Selection Sort Recursive Algorithm O(N²): Solution in C++
4. Find the two repeating elements in a given array: Solution in C++
5. Migratory Birds using Counting Sort [O(N)]: Solution in C++
6. Sum of Pairs: Given an array of integers and a number K, check if there exist a pair of indices i,j s.t. a[i] + a[j] = K and i!=j: Solution in C++
7. Largest Concatenated Number: Solution in C++ $$
8. Power Game: Solution in C++
9. Sort the Half Sorted: Solution in C++
10. Merge Sort Implementation O(N * log(N)): Solution in C++ $$
11. Inversion Count of an Array O(N * log(N)): Solution in C++ $$$
12. Sort an array of 0s, 1s and 2s [Count Sort]: Solution in C++
13. Sort elements by frequency (a.k.a Frequency Sort): Solution in C++ $$
14. HACKEREARTH - Micro and Array Update [Time: O(N) where N is the number of inputs & Space: O(1)]: Solution in C++ $$

Hashing 🍁🚬🚭

1. Two Sum [Leetcode]: Solution in C++ $$
2. Count distinct pairs with difference k, where (A[i]-A[j] = k) and (i != j): Solution in C++
3. Triplet Sum in Array: Accepted Solution in C++ — Time: O(N²) & Space: O(N) & Unaccepted Solution in C++ — Time: O(2N + N²) & Space: O(N) $$
4. First repeated character in the given string [Time: O(N) & Space: O(26) for HashSet]: Solution in C++ for relative version & Solution in C++ for absolute version
5. Count Distinct Elements in a Window of size K [sliding-window] [Time: O(N) & Space: O(N)]: Solution in C++ $$

Searching 🔍

1. Searching for a number in a list - Linear Search [O(N)]: Solution in C++
2. Searching an element in a sorted array - Recursive Binary Search [O(N + log(N))]: Solution in C++ $$$
3. Cube root of a number using recursive binary search [O(log(N))]: Solution in C++ for smaller range & Solution in C++ for larger range: -10¹⁸ to 10¹⁸ $$$
4. Find floor of given X in a sorted array of size N [Binary Search - O(log(N))]: Solution in C++ & Solution in Python +++
5. Find the element that appears once in sorted array [Binary Search - O(log(N))]: Solution in C++ $$
6. Number of occurrences - given an array and x, find the frequency of x [Binary Search]: Solution in C++ & Solution in Python ++
7. Painters Partition Problem (aka Allotting Books to Students Problem) [Binary Search - O(N*log(Sum(A[0:N-1])))]: Solution in C++ & Solution in Java $$$$$
8. Aggressive Cows (SPOJ Problem) [Binary Search - O(2 * (N * log(N)))]: Solution in Java $$$$$

Heaps 🗻

1. Save Konoha (CodeChef: SAVKONO) [O(N * log(N))] [Uses Max Heap]: Solution in C++

Stacks 📚

1. HACKERRANK - Super Reduced String [Time: O(N) where N is the length of the given string & Space: O(N) for stack]: Solution in C++
2. Parenthesis Checker [Time: O(N) for running through the string; Space: O(N) for stack] (ZESSTA 3^rd round Question 2): Solution in C++ & Solution in JavaScript $$$

Linked List 9️⃣→🔟→5️⃣→0️⃣→1️⃣

1. Detect Loop in a Linked List: Solution in C++ $$

Trees 🎄

1. Height of a Binary Search Tree [TC: O(N) where ‘N’ is the number of nodes]: Solution in C++ $$
2. Depth of each node in the Binary Search Tree [TC: O(N) where ‘N’ is number of nodes in BST]: Solution in C++ $$
3. Level Order Traversal of BST (or Binary Tree) [TC: O(N) where ‘N’ is number of nodes && SC: O(N) where ‘N’ is auxiliary queue size]: Solution in C++ $$
4. Zig-Zag Level Order Traversal of BST/Binary Tree [TC: O(N)]: Solution in C++ & Solution in Python $$
5. Bottom-Up (or Reverse) Level Order Traversal of BST/Binary-Tree
   1. Time: O(2N) & Space O(N) for HashMap — Accepted on GFG: Solution in Java $$
   2. Time: O(N) & Space: O(N) for storing individual depths in each node: Solution in Java $$
6. Diameter of a BST/Binary-Tree
   1. O(N*H) — Unaccepted on GFG: Solution in C++ & Solution in Java $$$
   2. O(N) — Accepted on GFG: Solution in C++ & Solution in Java $$$

Graph Theory 🕸

1. Print Adjacency List: Solution in C++ $$
2. BFS of Graph: Solution in C++ $$$
3. DFS of Graph: Solution in C++ $$$
4. Check if a Path Exists between (u, v) in a Graph: Solution in C++ $$$
5. Count Number of Connected Components: Solution in C++ Using BFS & Solution in C++ Using DFS $$$
6. Detect Cycle in an Undirected Graph: Solution in C++ Using DFS $$$$ (GYTWorkz Technologies Interview Question)
7. Check if Graph is Forest or Not — Uses Cycle Detection Algo in an Undirected Graph: Solution in C++ Using DFS $$$$

Mixed Bag, Strings & Arrays 🔠🔡🎒👜

1. Sort a list of items wrt the frequency of each item (ZESSTA 3^rd round Question 1) — Hashing + Sorting: Solution in JavaScript $$
2. Sub-array with given sum (prefix-sum, sliding window) [Amortized Time: O(N) & Space: O(N+1) for prefix-sum array]: Solution in C++ $$
3. Sort the substring (string manipulation, counting sort) [Time: O(N) & Space: O(26)]: Solution in C++ $$$$
4. Reverse words in a given string - Tokenizing String: Solution in C++ $$
5. Find the number of words, vowels & consonants in the given string [Time: O(N) & Space: O(1)]: Solution in C++ & Solution in Python
6. Check whether given two strings are anagrams of each other or not: Solution in Python
7. Compute the modulo of a very large number (given as a string): Solution in C++ $$
8. HACKEREARTH - Bracket Sequences - (prefix-sum, hashing) [Time: O(N) & Space: O(N) for HashMap]: Solution in C++ $$$
9. 3Sum Closest — Uses two-pointer technique: Solution in C++ $$$ (GYTWorkz Technologies Interview Question)
10. Count the occurrences of a substring in a string using Rabin Karp’s String Matching Algorithm rolling-hash, double-hash — [Time: O(N) & Space: O(N) where N is length of the larger string]: Solution in C++ & Solution in Python $$$$
11. NAJPF - Pattern Find SPOJ: Accepted Solution in C++ — Time: O(M+N) where N: text length $$$$
12. Area of Container with Most Amount of Water — finding-smaller-elements-stack carry-forward-max trapping-rainwater + area-under-histogram : Solution in C++ $$$$$$ (GYTWorkz Technologies Interview Question)

Dynamic Programming 🧨💻

1. Largest Sum in a Contiguous Subarray (Kadane's Algorithm) [Time: O(N) & Space: O(1)]: Solution in C++ & Solution in Python $$$$