General

Question 1

An array has every distinct number three times except one. Find this number

Answer 1

Count how many times each bit is on. This will be of the form 3n or 3n+1. The bit which is of the form 3*n+1 is on in answer.

Question 2

Reverse Linked List

Answer 2

last = NULL;
while head is not NULL:
next = head->next
head->next=last
last=head
head=next
return last;

Question 3

Find maximum product subarray with negative, positive and zeroes.

Answer 3

https://leetcode.com/problems/maximum-product-subarray/discuss/48230/Possibly-simplest-solution-with-O(n)-time-complexity

Question 4

builtin_clz(x)
builtin_ctz(x)
builtin_popcount(x)

Answer 4

count leading zeroes
count trailing zeroes
count set bits

Question 5

Given a string A and integer B, what is maximal lexicographical string that can be made from A if you do atmost B swaps.

Answer 5

Keep a global max string.
Recursive function is f(string,k). We run a n^2 loop and try all swaps and call recursive function f(string,k-1) and check if string is better than max string.
Each recursive call has a time complexity of O(n^2+n)
Total k recursive calls
Time Complexity O((n^2)^k)
Improvement is rather than trying all swaps we maintain a current index as well and try swaps with the max number only after it.
Each recursive function calls itself n times until k is 0
O(n^k). if k doesn’t change, current index changes with only one recursive call therefore no effect on time

Pure greedy wrong at 5499

https://www.geeksforgeeks.org/find-maximum-number-possible-by-doing-at-most-k-swaps/

Question 6

Number of partitions of N

Answer 6

dp(n,taken) number of ways to partition n such that least number is taken
dp(n,taken) = dp(n-taken,taken)+dp(n,taken+1)
either taken is present or it isn’t
O(n^2)

Question 7

Knapsack
Given N items with (value, weight), total weight W of knapsack, find maximum value you can get

Answer 7

dp(i,w) = maximum value we can create with choices being from the first i elements.
dp(i,w) = max( v[i] + dp(i-1, w-w[i] ), dp[i-1][w] )
O(NW)

Question 8

Knapsack
Given N items with (value, weight), total weight W of knapsack, find maximum value you can get
infinite items available

Answer 8

dp(i,w) = max( dp(i-1,w), v[i] + dp(i-1,w-w[i]), 2v[i] + dp(i-1,w-2w[i]) …
O(nww)
check what dp(i,w-w[i]) is
we can use that value to reduce time complexity
dp(i,w) = max(dp(i-1,w), v[i] + dp(i,w-w[i]) )

Question 9

Longest Increasing Subsequence

Answer 9

dp[i] = LIS ending at index i
dp[i] = max( 1 + dp[j] ) for all j < i such that a[j] < a[i]
O(n^2)

dp[i] = among all increasing subsequences of length i, dp[i] will be the minimum ending number.
for some number x, it can be added to any subsequence with dp[j] < x. j = lowerbound(x) on dp,
dp[j]=min(dp[j],x)
O(nlogn)

Question 10

Longest common subsequence of two arrays. Distinct integers in array.

Answer 10

LCS -> O(n^2)

a = [4, 3, 5, 7, 9]
b = [4, 3, 2, 9, 3]
map all elements of a to their index.

ai = [1,2,3,4,5]
bi = [1,2,6,5,2]
LIS is answer
O(nlogn)

Question 11

Longest common subsequence

Answer 11

dp[i][j] = LCS of s1[0,i] and s2[0,j]
dp[i][j] = max( dp[i-1][j], dp[i][j-1] )
if s1[i] == s2[j]
dp[i][j] = 1 + dp[i-1][j-1]
O(n*m)

Question 12

Players p1 and p2. Given array p1 takes one element from front or back. Then p2. Maximize sum of p1-sum of p2.

Answer 12

dp[l][r] = maximum s1-s2
dp[l][r] = max( a[l] - dp[l+1][r], a[r]-dp[l][r-1] )
O(n^2)

Question 13

Given an array. Operation: merge i and i+1 to create (a[i]+a[i+1])%100 which gives profit a[i]*a[i+1]. Find maximum profit after all operations.

Answer 13

dp{l}[r] = max profit for array [l,r]
dp[l][r] = max (dp[l][mid]+dp[mid+1][r] + (pre[r]-pre[mid])%100*(pre[mid]-pre[l-1])%100) over all mid from l to r-1
O(n^3)

Question 14

Given array of N elements, for each window of K elements, find the maximum element.
Expected O(n)

Answer 14

Useful element is element which is greater than all elements on it’s left for that window.

We maintain a deque of useful elements which will store the elements in reverse sorted order.

When iterating, keep removing the last element until it is greater than x. So the max element will always be at the front.

Question 15

Given an array. Operation: merge i and i+1 to create ( a[i]X + a[i+1]Y + Z )%50 which gives profit a[i]*a[i+1]. Find maximum profit after all operations. n<=50

Answer 15

dp[l][r][k] = maximum profit from range(l,r) such that value becomes k.
dp[l][r][(pX + qY + Z)%50] = max ( dp[l][mid][p] + dp[mid+1][r][q] + p*q) over all p,q,mid
O(n^5)

Question 16

Given an array we can delete consecutive same elements to get a profit of (number of elements)^2. Find max profit we can get by deleting the entire array.

Answer 16

See LR dp states ending problem

Question 17

Given a parenthesis sequence with ‘?’, find the number of ways to replace ‘?’ with ‘(‘ or ‘)’ such that final string is balanced.

Answer 17

dp[i][j] = number of ways such that the prefix (1..i) has value j. Ans is dp[n][0].

Question 18

Given a string, find the number of distinct subsequences.

Answer 18

dp[i] = number of distinct subsequences of string
j = last occurence of s[i]
(1..i). dp[i]=2*dp[i-1]-dp[j-1]

Question 19

No of ways to fill N blanks with 0 or 1, such that no K consecutive characters are same.

Answer 19

dp[i][j][k] = number of ways to fill first i blanks such that last character is j, with k consecutive characters at the end.
n2k

Question 20

Keys: A, ctrl-A, ctrl-C, ctrl-V
Maximum A’s we can create with N key presses.

Answer 20

dp[n] = max of dp[n-1]+1, for i >= 3 dp[n-i]*(i-1)
O(n^2)

Question 21

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. (https://leetcode.com/problems/trapping-rain-water/)

Answer 21

We can calculate how much water will be above the ith elevation.
wat[i] = max(0,min(l[i],r[i])-height[i])
l[i] and r[i] is the maximum elevation on the left and right of ith elevation.

Question 22

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

Answer 22

dp[i][j] = maximum length of common subarray starting at i in nums1 and starting at j in nums2

Question 23

Expected Value definition

Answer 23

E(X) = summation of [P(a) x a] over all a

Question 24

Linearity of Expectation

Answer 24

E[X+Y] = E[X] + E[Y]

Question 25

Randomly shuffled permutation of size n find the expected number of inversions

Answer 25

Let Xij be variable where i < j
Xij = 0 if i is before j
Xij = 1 if i is after j
# inv = Sum(i < j) Xij
Apply Expectation on both sides
E[ # inv ] = E[ Sum(i < j) Xij ]
E[ # inv ] = Sum(i < j) E[ Xij ]
E[Xij] = 1/2(0+1)
E[ # inv ] = (nC2)/2

Question 26

P(H) = 1/2 P(T) = 1/2
Create three events where probability of each event is 1/3

Also find the expected number of experiments to get one of the three events.

Answer 26

Rejection Sampling
Events are [HH, HT, TH]
and when we get TT we just repeat the experiment.

Let x be expected experiments
x = (1/4)(1 + x) + (3/4)(1)

Question 27

Create equally probable rand10 function from rand7

Answer 27

Again rejection sampling.
We run the function twice.
Two values [0..6][0..6]
Total types of outputs are 49. So for 40 of them we assign to [0..9] and for 9 we do rejection and conduct experiment again.

Question 28

N sided dice. Throw as long as you don’t get all sides at least once. Find expected number of total moves.

Answer 28

Let Xi = # of moves to get another distinct number after getting i-1 distinct numbers.
Total moves = Sum(i=[1..n])Xi
Apply expectation on both sides.
Expected # of moves = Sum(i=[1..n])E[Xi]
E[Xi] = (n-(i-1))/n + ((i-1)/n)(1+E[Xi])
E[Xi] = n/(n-i+1)

Question 29

For rejection sampling, expected number of moves formula

Answer 29

E[X] = 1/(probability of success)

Question 30

Given number N, randomly select a divisor d and divide N by d. Find expected number of moves to reach 1. Time complexity tricky.

Answer 30

E[Xn] = (1/# of divisors)Sum( d divides n ) E[Xn/d]+1
Here we write recursive solution. For calculating for n, we have to visit sqrt(n) divisors. But when calculating for those divisors the same smaller divisors will be visited.
Time = O(sqrt(N))

Question 31

Grundy Numbers
https://www.codechef.com/submit/PILESPARITY

Answer 31

Grundy numbers is a way to solve nim style problems. One move must be restricted to one pile only. If the piles are [a1,a2,a3..an]
it can be replaced to [G(a1),G(a2),G(a3)…G(an)] which will be the simple nim game where if xor of all grundy is 0 2nd player wins else 1st.

If from a state X of some pile we can move to states {X1,X2,X3..Xn}
G(X) = mex{ G(X1), G(X2), G(X3) … G(Xn) }

Question 32

Array
Operation: Choose any subsequence and add X to all the elements.
Minimum operations to make all distinct.
https://www.codechef.com/submit/SUBSEQDIST

Answer 32

max of (cnt-1) is wrong. Each operation changes the frequency of each distinct element. We can choose half of cnt for each distinct number and add X to it. So the new cnts will be half of before. Here max will be ceil(cnt(max)/2). Hence number of steps is for the max cnt to reach 1.

Question 33

Given a tree start at any node v, end at any node u and we have to traverse all nodes travelling minimum edges.

Answer 33

ans = 2(N-1) - len(diameter)
All edges will be visited twice except edges on the path v -> u
Therefore maximum length path should be chosen.

Question 34

Two ways to find diameter of tree

Answer 34

1. Find farthest node from any node. Find farthest node from the new node.
2. Tree DP
   Store the distance of deepest node in a subtree with dp
   deep[v] = 1 + max over all u(deep[u])
   diameter = max over all v (1+ sum of deepest and second deepest node among all children of v)

Question 35

Given a rooted tree.
Operation select an edge (v->u), break it and attach u to root. Max K operations, what minimum height can be achieved for the tree.
https://codeforces.com/contest/1739/problem/D

Answer 35

Binary search on answer. if mid is maximum height, we have to make (mid-1) length partitions from children of root. We do this recursively by maintaining maximum depth in a subtree. as soon as max depth is (current depth+mid-1), we delete the edge between current and his parent.
Such cutting is best done from the bottom up never start from root.

Question 36

Find minimum xor pair in array

Answer 36

Claim: Minimum xor pair will be consecutive in sorted array.
A < B < C
Let i be the maximum bit where A and C differ.
A[i] = 0, C[i] = 1
Now
if B[i] = 0
A^B = 0 B^C = 1 A^C = 1 Hence, A^B < A^C
if B[i] = 1
A^B = 1 B^C = 0 A^C = 1 Hence, B^C < A^C

Question 37

Check whether a big number ( string ) is divisible by m

Answer 37

Do it like the division we do on paper. loop over each character c
cur *= 10;
cur += c -‘0’
cur %= m

Question 38

Maximum xor subset

Answer 38

Let us first understand a simple case when all elements have Most Significant Bits (MSBs) at different positions. The task in this particular case is simple, we need to do XOR of all elements.
If the input contains multiple numbers with the same MSB, then it’s not obvious which of them we should choose to include in the XOR. What we do is reduce the input list into an equivalent form that doesn’t contain more than one number of the same length. By taking the maximum element, we know that the MSB of this is going to be there in output. Let this MSB be at position i. If there are more elements with i’th set (or same MSB), we XOR them with the maximum number so that the i’th bit becomes 0 in them and the problem reduces to i-1 bits.

Question 39

Taking input till end of file

Answer 39

int n;
while(cin»n){

}

Question 40

Given binary string of length 2n. Select a subsequence b and right shift it such that there should be two distinct equal subsequences of length n.

Answer 40

Create two subsequences of characters at even index and odd index. Now if at any index i characters don’t match, we put the original string index which has 0 in b. Similarly for next non equal, we put the index which has 1 in b and so on.

Question 41

Given a string and k, right shift the string by k. No extra variables can be used.

Answer 41

reverse is an inplace operation. Call reverse on s[1,n-k], s[n-k+1,n] and then on s[1,n]

Question 42

stoi()
stoll()
to_string()

Answer 42

string -> int
string -> ll
int -> string

Question 43

N ranks M students, student i gets happy[i][j] if assigned rank j. One rank can be assigned to one student only. Find maximum total happiness.
N < = 15, M < = 50

Answer 43

Bitmask state dp[i][mask] = ans if initially mask is assigned to 0 to i-1 and we get to choose how to assign rest of the mask, assigning to i on the current level of recursion.
Upward dp
dp[i][mask] = Maximum happiness by choosing from the first i students (0..i-1) with mask ranks chosen.
dp[i][mask] -> max on
dp[i+1][mask]
dp[i+1][ mask | (1 < < j ) ] + happy[j][i] if jth bit is off in mask
O((2^n)nm)

Question 44

Hamiltonian path -> visits each vertex exactly once in a graph
Number of hamiltonian paths starting from 1 and ending at N

Answer 44

dp[i][mask] = number of hamiltonian paths starting from i ending at N having already visited mask. (ith bit on means i+1 node is visited)
Top down dp

f(node, mask):
if node == N and mask == (1 < < N)-1
return 1
ans=0
for v in adj[node]:
if not mask&(1< <(v-1))
ans += f(v,mask|(1< <(v-1))
return ans

O((N + M)*2^N)

Question 45

Find the shortest hamiltonian path in N nodes weighted graph

Answer 45

dp[i][mask] = shortest path ending at i having visited mask
dp[i][(1 < < i)] = 0
for v in adj[node]
if mask hasn’t visited v
dp[v][mask | (1 < < v)] = max (self, 1 + dp[node][mask])

Question 46

Number of hamitonian paths

Answer 46

dp[node][mask] -> number of hamiltonian paths starting from i ending at N having already visited mask
Only difference is base case -> if mask = (1 < < N)-1 node need not be N
return 1

Question 47

Number of hamiltonian cycles

Answer 47

start from any node x, calculate number of hamiltonian paths to y
if y has edge to x, add it to the answer

Question 48

Number of simple paths in a graph (Visit nodes at most once)

Answer 48

dp[i][mask] = Simple paths starting at i having visited mask
Base is if mask contains only 1 bit, 0 paths else 1 path. Answer will be complete dp[i][mask] summation.

Question 49

Given array,
operation => decrease a[i], increase a[i-1]
Find minimum possible value of maximum of array

Answer 49

Leetcode 2439
Here movement is from right to left direction only. Therefore, answer will always be greater than ceil(sum of prefix/length of prefix). Do this on every prefix and maximum of all is the answet

Question 50

Next greater element

Answer 50

Forward loop, push element if smaller than top. Else current element is next greater for top element, now pop top element and repeat

Question 51

Find numbers in [L,R] whose sum of digits is divisible by D.
https://atcoder.jp/contests/dp/tasks/dp_s

Answer 51

dp[idx][lo][hi][rem] = count of ways to create the number such that (sum of digits)%D is 0 and (sum of digits)%D till idx-1 is rem. lo and hi and binary
lo = 0 means not tight. Which means from current idx we can have digits with no lower bound and it will always be greater than L.
lo = 1 means tight. Which means idx is still bounded by L’s digit.

Question 52

Binary matrix, rearrange columns to get the maximum area having all ones

Answer 52

For each column store maximum number of consecutive ones ending at each row. Now for each row, sort these values.