Skip to content

OmarElgabry/Cubes

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

54 Commits

assets

assets

 
 

src

src

 
 

LICENSE

LICENSE

 
 

README.md

README.md

 
 

Repository files navigation

Screenshot

Cubes

Implementation of interesting algorithms in C++ and their related problems on online Judges.

Index

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=10
Output:
{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=5
Output:
{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: omar.elgabry.93@gmail.com

License

Built under MIT license.

About

Implementation of interesting algorithms in C++

Topics

c-plus-plus algorithms competitive-programming algorithm-challenges

Resources

Readme

License

MIT license
Activity

Stars

24 stars

Watchers

3 watching

Forks

6 forks
Report repository

Releases 1

Cubes 1.0 Latest
Oct 3, 2016

Packages

No packages published

Languages