Problem Source: Vietnamese: Codeforces - Easy Can be solve with $O(n^2)$ solution Codeforces - Hard Need to be solved in $O(n\log n)$ solution English: Leetcode Give an integer array nums. Return the length of the longest increasing subsequence. An increasing subsequence is a subsequence $a_1,..,a_k$ that $$ \begin{align} &i_1 < i_2 < \dots < i_k,\\\ &nums[i_1] < nums[i_2] < \dots < nums[i_k] \end{align} $$ For example: Input: {0,1,0,3,2,3} Output: 4 //{0,1,2,3} Solution Brute Force This method is the simplest solution can approach: We can enumerate all subsets of the original array and then test them for the increasing property then find the longest....

Problem Source: Codewars From Wikipedia The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences. It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. Write a function lcs that accepts two strings and returns their longest common subsequence as a string. Performance matters. For example...

Problem Source: Codewars How many ways can you make the sum of a number? From wikipedia: https://en.wikipedia.org/wiki/Partition_(number_theory)# In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. Example: Input: 4 Output: 5 //4, 3+1, 2+2, 2+1+1, 1+1+1+1 Solution It would be very slow if you enumerate all the partitions when $n$ is large so i’ll use dynamic programing instead (Oω<)☆....

Problem Source: Codeforces Find the $n^th$ Fibonacci number modulo $10^9+7$. So, you need to find $F_n$ in the sequence defined as $$ \begin{aligned} F_0 & = 0\\ F_1 & = 1\\ F_i & = F_{i-1} + F_{i-2} (i >= 2) \end{aligned} $$ Example: Input: 50 Output: 586268941 Solution Approach 1: Dynamic Programing Using fibonacci’s difference equation as a recurrence relation, i can write to a program like this: int f0 = 0, f1 = 1, fn; for(int i = 2; i <= n; i++){ fn = f0 + f1; f0 = f1; f1 = fn; } return fn; This code’s complexity is $O(n)$ which is fine with $n <= 5....

Problem Source: Leetcode , Codewars You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin. For example: Input: amount = 5, coins = {1,2,5} Output: 4 //{5, 2+2+1, 2+1+1+1, 1+1+1+1+1} Solution We’ll go through at each stage to considera certain coin and see how it changes the total amount of ways that can make change....

Problem Source: Leetcode You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin. Examples: Input: coins = {1,2,5}, amount = 11 Output: 3 //2 đồng 5 và 1 đồng 1 Input: coins = {2}, amount = 3 Output: -1 Solution Approach 1: Brute force By above example, amount = 11....

Summary Name Operator Description AND & Both bits are 1, return 1. Otherwise, return 0. OR \ One of both bit is 1, return 1. Otherwise, return 0. XOR ^ Two bits are different return 1. Otherwise, return 0. NOT ~ Flip bit, 0 becomes 1, 1 becomes 0 Shift left << Shifts all the bits to the left Right left >> Shifts all the bits to the right Application Integer Change bit //Set nth bit x |= (1 << n); //Set the right-most 0 bit to 1 x |= (x+1); //Unset nth bit x &= ~(1 << n); //Set the right-most 1 bit to 0 x &= (x-1); //Toggle nth bit x ^= (1 << n); //Get the mth bit of n (x >> n) & 1; //Swap Adjacent bits ((x & 10101010) >> 1) | ((x & 01010101) << 1); Multiplication / Division x by $2^n$ x << n //multiplication x >> n //division Round up to the next power of two x--; x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x++; Round down to the next power of two x--; x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x++; x = x >> 1; //the same with the code above but added this line Floor x x >> 0; 6....

Problem Source: Codewars The aim of the kata is to decompose $n!$(factorial n) into its prime factors. For example: Input: n = 12 Output: 2^10 * 3^5 * 5^2 * 7 * 11 Note that $n$ can reach 4000 and, of course, 4000! would be very big with more than 12000 digits ∑(O_O;) Solution Idea By definition, the factorial of a positive integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$: $$12!...

Problem Codewars Given a positive number n > 1 find the prime factor decomposition of n. The result will be a string with the following form: ($p_1$**$n_1$)($p_2$**$n_2$)…($p_k$**$n_k$) where a**b means $a^b$ $p_i$ in increasing order $n_i$ empty if n(i) is 1. Example: Input: n = 86240 Output: (2**5)(5)(7**2)(11) Solution Generally, in order to calculate all of the prime factors of a number, you have to go about dividing the original number by its smallest prime factor....

Promblem Source: Codeforces We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we’ll call a positive integer $t$ Т-prime, if $t$ has exactly three distinct positive divisors. You are given an array of $n$ positive integers. For each of them determine whether it is Т-prime or not. Examples Input: 3 4 5 6 Output: YES NO NO Solution First, we need to find all prime numbers from 2 to $\sqrt{x}$....