Cubes
Implementation of interesting algorithms in C++ and their related problems on online Judges.
Index
- Numbers
- Bits
- Strings
- Sorting
- Cumulative Array
- Window
- Two Pointers
- Recursion
- BFS
- DFS
- DP
- Randoms
- Support
- Contribute
- License
Numbers
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Is Prime | Check if a number is prime or not. | Input: 5 Output: true |
O(sqrt(n)) | — |
Prime Numbers | Returns all prime numbers till N using Sieve implementation. | Input: 10 Output: {2, 3, 5, 7} |
O(n * ln * ln) | B. Prime Matrix |
Divisors | Returns all divisors of a number. | Input: 10 Output: {1, 10, 2, 5} |
O(sqrt(n)) | B. Easy Number Challenge, B. Duff in Love |
Factorize | Returns all prime factors of a number. | Input: 4 Output: {2, 2} |
O(sqrt(n)) | — |
Count Range Divisors | Returns the count of divisors for each number from 1 to N. | Input: 10 Output: 27 |
O(N) | — |
Factorial | Returns the factorial of a number. | Input: 5 Output: 120 |
O(N) | — |
GCD & LCM | Returns the greatest common divisor and least common multiple of given two numbers. | Input: 6, 28 Output: GCD=2, LCM=84 |
— | A. Fox and Number Game |
Big Mod | Given B, P, & M, Find: B^P % M. | Input: B=2147483647, P=2147483647, M=46340 Output: 13903 |
O(LogP) | Big Mod |
Bits
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Bit Manipulations | Implementing various snippets: • Check if bit 0 or 1. • Set a bit to 1. • Given N, return 2^k, k is th position of least significant 1-bit. • Given n1 & n2, get number of different bits. • Count number of 1 bits. |
Check Test Cases in src/Bits/Bit Manipulations | O(N) | B. Fedor and New Game, B. The Child and Set |
Binary Conversions | Convert decimal to binary number(integer/string), and back to decimal. | Input: 10 Output: {"1010", 10} |
O(logN), O(N) | B. New Year and Old Property |
Generate Combinations | Generate combinations with all possible sizes. | Input: {1, 2} Output: {}, {1}, {2}, {1, 2} |
O(N * 2^N) | B. Preparing Olympiad, 324. Problem Set |
Strings
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Remove Consecutive | Remove consecutive characters. | Input: "abacabaabacabaa" Output: a |
O(N) | A. Plug-in, Parentheses Balance |
Alpha Characters | Get all strings with only consecutive aplha characters | Input: ".omar.is.brilliant." Output: {omar, is, brilliant} |
O(N) | Andy's First Dictionary |
Palindrome Characters | Check if a string is Palindrome. | Input: abcba Output: true |
O(N) | Pesky Palindromes, C. Little Frog, Mother bear |
Palindrome Substrings | Check if a string is Palindrome by substrings of length K; Comparing substrings instead of characters. Given that the length of string is divisible by K. |
Input: "abckfgabc", K=3 Output: true |
O(N) | — |
Sub Strings | Generates all possible substrings. | Input: "hello" Output: {h, he, hel, hell, hello, e, ...} |
O(N^3) | Pesky Palindromes |
Words Values | Return summation of values for each word(if exist) in the given string. | Input: string="hello world", values={"hello" => 5, "john" => 2} Output: 5 |
O(N) | Hay Points, Babelfish |
Frequent Character | Count frequency of each character in a string, and get the max character(s) occurred. | Input: "The characTer T is The mosT frequenT characTer in This sTring" Output: character=T, count=9 |
O(N) | — |
Sequence of Characters | Check if a sequence of characters exists or not in the given string. | Input: string="can you find the given characters in order?", sequence="fire" Output: true |
O(N) | B. Suffix Structures |
Anagram | Given string A and B, return true if A occurs as an anagram in B. | Input: A="car", B="xdfacrcytvharc" Output: true at (3,5), (11,13) |
O(A*B) | — |
Replace Characters | Given a string of lower case characters, and a set of queries, each query has two characters. For every query, Replace first character with second in the given string, and vice-versa, and then return the resulting string. |
Input: string="aabbccdd", queries={('a', 'b'), ('c', 'd'), ('d', 'a')} Output: bbddaacc |
O(max(N, queries)) | B. Rebranding |
Hamming Distance Sum | Given a string X of length <= 10^5 with 1s and 0s, and string Y with length <= length of X. Get summation of numbers of different bits for each sub-string of X with string Y. | Input: Y="01", X="00111" Output: 3 |
O(N) | B. Hamming Distance Sum |
Sorting
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Count Sort | Sort an array by counting. | Input: {3, 1, 0, 1, 4, 8, 11, 4, 34, 2} Output: {0, 1, 1, 2, 3, 4, 4, 8, 11, 34} |
O(NLogN) | A. Helpful Math |
Reverse Subarray | Is it possible to sort the array by reversing exactly one segment(part) of it? | Input: {6, 78, 63, 59, 28, 24, 8, 96, 99, 120} Output: [1 -> 6] |
O(N) | B. Sort the Array |
Shifting | Find minimum number of operations to sort array by moving the last element to the beginning | Input: {4, 5, 6, 2, 3} Output: 2 |
O(N) | B. Little Pony and Sort by Shift |
Stairs | What's the minimum number of array elements to be erased so that we can have array in this form: a1 < a2 < ... < ai - 1 < ((ai)) > ai + 1 > ... > an - 1 > an. |
Input: {1, 1, 2, 2, 3, 3} Output: min=1, array={1, 2, 3, 2, 1} |
O(N) | B. Sereja and Stairs |
Cumulative Array
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Range Sum(1D Array) | Given an array, and set of queries: start and end, what is sum of values in range [start, end]. | Input: array={1, 3, 4, 2, 5}, start=2, end=5 Output: 14 |
O(N) | — |
Max 1D Subarray(Fixed Length) | Given array, what's the max sub array of length L. | Input: array={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, L=3 Output: 27 |
O(N) | — |
Adjacent Characters | Given 2D array N x M of '.' & '#' characters, and set of queries, each query with two numbers c1 & c2. For each query, return the summation of numbers of two adjacent '.' characters in each row from column c1 to c2. | Input: array= ....#..# .#...... ##.#.... ##..#.## ........ N=5,M=8, queries={(1,3),(2,5)} Output: {6, 9} |
O(N * M), O(N * queries) | C. New Year and Domino |
Window
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Max 1D Subarray(Fixed Length) | Given array, what's the max sub array of length L. | Input: array={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, L=3 Output: 27 |
O(N) | — |
Max 1D Subarray(Variable Length) | Given array, find subarray with maximum sum. | Input: {1, 10, -3, 2, -40, -4, 5, 3, 18, -2} Output: range=[6, 8], sum=26 |
O(N) | Maximum Sum |
Max 2 Subarrays | Given array, find the largest 2 sub arrays(not interleaved) of length L. | Input: array={1, 2, 1, 15, 2, 3, 6, 8, 3, 3, 8, 6}, L=3 Output: [3 -> 5], [6 -> 8] |
O(N) | B. Maximum Absurdity |
Two Pointers
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Max Subarray(Less than or equal value) | Given array, find max subarray <= t. | Input: array={6, 8, 14, 9, 4, 11, 10}, t=13 Output: [3 -> 4] |
O(N) | B. Books |
Max Subarray of Similar Characters | Given a string contains only two characters; 'a' & 'b'. You can change at most K characters; either 'a' to 'b' or vice-versa. Find max subarray. | Input: str="aabaabaa", K=1 Output: aabaa |
O(N) | C. Vasya and String |
Guess the Number | Given a set of queries like: ">=1", "<2", ">-3", ...etc. Guess the range of numbers that achieves these queries. |
Input: queries={{">=", 1}, {">=", 3}, {">", -3}, {"<=", 55}} Output: [3, 55] |
O(N) | 416A - Guess a number! |
Zuma | Given array, and a tnum number that will be inserted at index tindex. If there are three or more contiguous similar numbers, they should be destroyed(erased). This rule is applied until there are no more three or more contiguous similar numbers. Count the destroyed numbers. Initially, there is no three or more contiguous similar numbers. |
Input: array={5, 4, 4, 2, 2, 4, 4, 5, 5, 1, 7, 6}, tnum=2, tindex=4 Output: 10 |
O(N) | B. Balls Game |
Exact Sum | Given array of 10^5 elements, Find All Xs & Ys, where X + Y = goal | Input: {1, 2, 4, 6, 10, 5, 13, 8, 14, 5}, goal=10Output: {2, 8}, {4, 6}, {5, 5} |
O(NLogN) | Exact Sum |
3SUM | Given array of 10^5 elements, Find All Is & Js & Ks, where I + J + K = goal. | Input: array={1, 2, 4, 6, 10, 5, 13, 8, 14, 5}, goal=10 Output: {1, 4, 5} |
O(N^2) | — |
Recursion
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Print Number | Given a number print it and print number in bits recursively. | Input: 213 Output: decimal=213, binary=11010101 |
O(N) | — |
Fibonacci | Calculate the fibonanci value of N, and print the first N numbers in the fibonanci series. | Input: 7 Output: F(n)=13, series={0,1,1,2,3,5,8} |
— | — |
3n+1 | Given a number, if even divide by 2, if odd, multiply by 3, and add 1. Count the steps till number = 1 recursively. |
Input: 7 Output: 17 |
— | The 3n + 1 problem |
BFS
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
4&7 | Generate all possible children nodes starting from 4 & 7 until you find the goal. |
Input: goal=447 Output: {4, 7, 44, 47, 74, 77, 447} |
O(2^len(goal)) | B. Lucky Numbers (easy) |
DFS
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Permutation | Given array, generate all permutations. | Input: {4, 5, 6} Output: {{4, 5, 6}, {4, 6, 5}, {5, 4, 6}, ...} |
O(N * N!) Printing the numbers takes O(N). | Generating Fast |
Combination | Given array, generate all combinations of length L. | Input: array={1, 7, 2}, L=2 Output: {1, 2}, {1, 7}, {7, 2} |
O(N! / ( (N-L)! * L!)) | — |
Beautiful Numbers | Generate all possible numbers that has a number of digits N and consists of any number from 1 to K. | Input: K=2, N=3 Output: {{1, 1, 1}, {1, 1, 2}, {1, 2, 1}, ...} |
O(K^N) | BNUMBERS |
Max Path | Given 2D array, starting from (0, 0), move only to right and down. Find the maximum sum by exploring all possible paths. Can you improve your solution (hint: using DP (Recursive and Iteration) / Dijkstra (MinPath) )? |
Input: {{1, 5}, {2, 4}} Output: 10 |
— | Minimum Path Sum |
Maze | Given 2D array, starting from (0, 0), move to up, left, right and down. Find the goal node by exploring all possible paths. |
Input: array= . . X . . X . G . . . X X . X X Output: [1, 3] |
— | C. Maze |
Connected Cells | Given 2D array, starting from (0, 0), Return the number of connected blocks | Input: array= . . X . X X X X . . . X X . X X Output: 3 |
— | — |
Generate Binaries | Generate all binary numbers of length N and has given number of 1s L, . Print them sorted (in ascending lexicographical order) |
Input: N=4, L=2 Output: {0011, 0101, 0110, 1001, 1010, 1100} |
O(N! / ( (N-L)! * L!)) | The Hamming Distance Problem |
Lowest Common Ancestor | Given two nodes in a tree(with and without parent pointers). Return their lowest common ancestor. |
Check Test Case in src/DFS/Lowest Common Ancestor Check Amazon Live Coding - Number of edges between two nodes |
O(h), O(N) | — |
DP
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Fibonacci | Calculate the fibonanci value of N. | Input: 5 Output: 8 |
O(2N ~ N) | — |
Divide | Given a number, get f(n) where f(n) = f(n/2) + f(n/2), f(0) = f(1) = 1, and n <= 2^31. (i.e. If n = 7, then f(7) = f(3) + f(4)) |
Input: 7 Output: 7 |
— | TRUCKL |
Randoms
Code Name | Problem Statement | Test Case | Complexity | Related Problems |
---|---|---|---|---|
Unique Numbers | Given array of numbers, return count of unique values, and print them. | Input: {7, 2, 4, 5, 16, 2, 0, 2, 4, 6} Output: count=7, numbers={7, 2, 4, 5, 16, 0, 6} |
O(N) | A. Inna and Alarm Clock, A. Valera and Antique Items, A. I Wanna Be the Guy, A. Asphalting Roads, A. Bulbs |
Unique Characters | Given string of characters, what's the count of unique characters and print them. | Input: "hMshMZ" Output: count=4, characters={h, M, s, Z} |
O(N) | A. Inna and Alarm Clock, A. Valera and Antique Items, A. I Wanna Be the Guy, A. Asphalting Roads, A. Bulbs |
Equal Lists | What's the min number of strings to be removed so that both lists can have same strings regardless of their order. | Input: list1={ "foo", "bar", "baz", "foo", "foo", "yard" }, list2={ "bar", "bar", "baz", "yard", "foo", "yard" } Output: 4 |
O(N) | Just Prune The List |
Unique Sets(Fixed Length) | Generate max number of unique sets of length L. It's not valid to use one array element more than once. |
Input: {1, 2, 3, 4, 4, 4, 7, 8, 9, 10}, L=2 Output: {{4, 10}, {4, 9}, {8, 7}, {4, 3}, {2, 1}} |
O(NlongN) | — |
Unique Sets(largest possible sizes) | Generate & Get the max number of unique sets with largest possible sizes. | Input: {1, 2, 3, 4, 1, 2, 3, 1, 2, 1} Output: {{1,2,3,4}, {1,2,3}, {1,2}, {1}}, max=4 |
O(N) | B. Beautiful Paintings |
The Block Number | Given an array of numbers. Print the number of ways you can choose contiguous subarrays of length L. Given that any subarray shouldn't contain number >= block number | Input: array={2, 2, 0, 7, 3, 2, 9, 2, 3, 1} block=7, L=3 Output: 2; at (0, 2) and 1 at (7, 9) |
O(N) | B. Prison Transfer, A. Queue on Bus Stop, C. DZY Loves Sequences, B. Domino Effect, A. Alena's Schedule, A. PawnChess, B. Chocolate, C. Watchmen, B. Books |
Generate Subarrays | Given array, Loop through each subarray of length L. | Input: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, L=5Output: {12345, 23456, 34567, ...} |
O(N*L) | — |
Painting Grid | Given a grid, and set of operations, each operation will paint all cells in a row or a column in a color(initial color is 0). What's the resulting grid. Each operation consists of 3 numbers; row or column(row=1 or col=0), index (1-indexed), and color. |
Input: {{1, 1, 3}, {0, 2, 1}, {1, 2, 2}} Output: {{3,1,3}, {2,2,2}, {0,1,0}} |
O(NxM) | B. Print Check |
Total Attacks | How many tanks can attack each other? Given N tanks, each tank represented by a number. Two tanks can only attack each other if they have the same number. Return number of total attacks. |
Input: {1, 2, 5, 1, 5, 7, 2, 6, 2, 6} Output: 6 |
O(N) | B. Wet Shark and Bishops, C. Watchmen |
The K-th Element | Given array of 10^5 element, which generates the following sequence of numbers. For example, array=[10,4,18,3,...], generates the sequence: "10,10,4,10,4,18,10,4,18,3,...". Return the K-th(1-Indexed) number. |
Input: array={10, 4, 18, 3}, K=5 Output: 4 |
O(N) | B. Game of Robots, A. Summer Camp |
Cakes | Given two arrays with N ingredients, and additional K grams. The 1st array for the needed grams, and 2nd for the available grams for each ingredient. Return the max number of cakes we can bake using the additional K grams. • The needed grams for each ingredient can bake one cake, i.e available=4, needed=2, then cakes=4/2=2 • To prepare one cookie you need to use all N ingredients. |
Input: needed={4, 3, 5, 6}, available={11, 12, 14, 20}, K=3 Output: 3 |
O(NxK) | D1. Magic Powder - 1 |
Regular Expression | Applying common regular expression patterns for matching, searching and replacing strings using regex. |
Check src/Randoms/Regular Expression | — | — |
Support
I've written these snippets in my free time during my studies. If you find it useful, please support the project by spreading the word.
Contribute
Contribute by creating new issues, sending pull requests on Github or you can send an email at: [email protected]
License
Built under MIT license.