LeetCode 1003. Check If Word Is Valid After Substitutions

  Link:- https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/

Summary:

Given a string s, determine if it is valid.

A string s is valid if, starting with an empty string t = "", you can transform t into s after performing the following operation any number of times:

Insert string "abc" into any position in t. More formally, t becomes tleft + "abc" + tright, where t == tleft + tright. Note that tleft and tright may be empty.

Return true if s is a valid string, otherwise, return false. 

For Example:

Input:

s = "aabcbc"

Output:

true

Logic:

This can be solved with the stack. Traverse string and if s[i]!= 'c' then insert into stack.

Else, check if stack element at the top and next to the top is 'b' and 'a' respectively or not.

if no: return false, else remove the top two elements of the stack.

Repeat the above steps.

At last, check if the stack is empty or not.

Time Complexity:

O(n)

To view my solution:

https://github.com/shivam04/codes/blob/master/leetcode/check-if-word-is-valid-after-substitutions.cpp

LeetCode 1530. Number of Good Leaf Nodes Pairs

 Link:- https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/

Summary:

Given a root of the binary tree and an integer distance. Find the number of pairs of leaves such that the shortest path between them is less than or equal to distance.  

For Example:

Input:

root = [1,2,3,null,4], distance = 3

Output:

1

Logic:

Convert the binary tree into a graph using DFS and find all the leaves in that DFS traversal.

Run other DFS from each leaf and check if the shortest distance between current leave and other leaf is less than or equal to distance or not. 

If yes:

ans++

Finally, return ans/2.

Why ans/2?

As we run DFS from each leaf, we end up computing the same pair of leaves twice.

Time Complexity:

O(n^2)

To view my solution:

https://github.com/shivam04/codes/blob/master/leetcode/number-of-good-leaf-nodes-pairs.cpp

Seedr

 Seedr.cc is the best torrent Stream site free service I had ever seen. I used a lot of sites before, also paid sites, but I had never seen like this site and it’s amazing services before. Seedr allows to you to download torrents very quickly, sometimes you don’t have to wait, because when I add torrent link, I found it’s already there :) and ready for downloading it in very high speed. It also makes you streaming the torrent videos without the need of downloading. And it’s surprised me when I didn’t have to pay for it, because it’s gives you a lot of offers to get more free space. The site gives you 2 GB limit after registration. By inviting 8 friends you got 500 MB for each one, and there a lot of others methods to increase you space, and it’s totally free. I highly recommended this amazing site, you’ll never find site like this in the whole internet. Click to my invite link, and you’ll get 500 Mb more space to be 2.5 GB as total starting space: https://www.seedr.cc/?r=151880

LeetCode 931. Minimum Falling Path Sum

Link:- https://leetcode.com/problems/minimum-falling-path-sum/

Summary:

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row and chooses one element from each row.  The next row's choice must be in a column that is different from the previous row's column by at most one.

For Example:
Input:

[[1,2,3],[4,5,6],[7,8,9]]

Output:
12

Logic:

Given array A with row ->n and column ->n

now create matrix say ans[n][m]

copy first row of A into ans

i.e ans[0] = A[0]

Why?

since we can start from any column in first row

now for rest of the row and column say i and j (1<=i<n, 0<=j<m)

ans[i][j] = A[i][j] + min(ans[i][j-1], ans[i-1][j-1], ans[i-1][j+1]

return min(ans[n-1])

i.e minimum of all values in last row

Why?

because we can end at any column of last row.

To View My Solution:

https://github.com/shivam04/codes/blob/master/leetcode/minimum-falling-path-sum.cpp

LeetCode 1140. Stone Game II

Link:- https://leetcode.com/problems/stone-game-ii/

Summary:

Alex and Lee continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones. 

Alex and Lee take turns, with Alex starting first.  Initially, M = 1.

On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

For Example:
Input:

[2,7,9,4,4]

Output:
10

Logic:

You can easily solve this question recursion.

So Alex will try to get the maximum point as he is playing optimally

if player == 1 (or Alex)

 alexPoint = max(alexPoint, sum[s to s+x-1]  stoneGameIIUtil(piles, s+x, max(x,m), n ,1-p));

also, Lee is playing optimally and try to reduce Alex points

if player == 0 (or Lee)

 alexPoint = min(alexPoint, stoneGameIIUtil(piles, s+x, max(x,m), n ,1-p));

1<=x<2*M

Will this solution gives TLE?

Yes

as 1<=N<=100 (total number of piles)

We can't use recursion here.

How can we optimize it?

One solution that I think of is using memorization. We can create a matrix say dp

and store current state dp[s][m][p]

s -> starting index

m -> for picking stones from piles i.e (1<=x<=2*m)

p -> 0/1 (Lee/Alex)

Now if we reach this state again we don't need to compute again and return dp[s][m][p]

(Yahi battein to bad me yaad  ayengi 😛)

Can we further optimize it?

Yes.

For calulationg sum[s to s+x-1]

we can use prefixSum array 

so sum[s to s+x-1] will be prefixSum[s+x-1] - prefixSum[s-1]

To View My Solution:

https://github.com/shivam04/codes/blob/master/leetcode/stone-game-ii.cpp

Seedr

Seedr.cc is the best torrent Stream site free service I had ever seen. I used a lot of sites before, also paid sites, but I had never seen like this site and it’s amazing services before. Seedr allows to you to download torrents very quickly, sometimes you don’t have to wait, because when I add torrent link, I found it’s already there :) and ready for downloading it in very high speed. It also makes you streaming the torrent videos without the need of downloading. And it’s surprised me when I didn’t have to pay for it, because it’s gives you a lot of offers to get more free space. The site gives you 2 GB limit after registration. By inviting 8 friends you got 500 MB for each one, and there a lot of others methods to increase you space, and it’s totally free. I highly recommended this amazing site, you’ll never find site like this in the whole internet. Click to my invite link, and you’ll get 500 Mb more space to be 2.5 GB as total starting space: https://www.seedr.cc/?r=151880

HACKEREARTH: Permutation Swaps

Link:- https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/permutation-swaps/

Summary:
Given P and Q be two permutation of numbers 1 to N. Given some pair of indexes (ai , bi).
Your task is to find Q from P by swapping (Pai , Pbi).
Print YES if it possible else print NO.

For Example:
Input:
2
4 1
1 3 2 4
1 4 2 3
3 4
4 1
1 3 2 4
1 4 2 3
2 4

Output:
NO
YES

Logic:
Use Breadth First Search(BFS) to find connected components of indexes.
Then check for indexes in each connected component if P and Q are same or not.

To View My Solution:
https://github.com/shivam04/codes/blob/master/hackerearth/algo/graph/medium/permutation-swaps.cpp

HACKEREARTH: Connected Horses

Link:- https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/connected-horses-10/description/

Summary:
Given N ,M number of rows and columns in a chess board
Given Q queries each query contain co-ordinates of horses in a chess board.
Find the number of ways horses swap their position

For Example:
Sample Input:
2 
4 4 4
1 1
1 2
3 1
3 2
4 4 4
1 1
1 2
3 1
4 4

Sample Output:
4
2

Topic:
Breadth First Search(BFS) , Dynamic Programming(DP)

Logic:
Use Breadth First Search(BFS) to find the total number of horses in each connected groups, then find the factorial of this number. Apply same in each group and multiplication of all gives the result. Use DP for calculation of factorials.

To View my solution:
https://github.com/shivam04/codes/blob/master/hackerearth/algo/graph/medium/connected-horses.cpp

HACKERRANK: Power Of Large Numbers

Link:- https://www.hackerrank.com/challenges/power-of-large-numbers

Summary:
Given A and B.
Find (A^B)%(10^9+7)

Constraints:
1 <= T <= 10 
1 <= A,B <= 10100000 
A % (109 + 7) != 0

For Example:
Sample Input:
4
3 2
4 5
7 4
34534985349875439875439875349875  93475349759384754395743975349573495

Sample Output:
9
1024
2401
735851262

Logic:
(A^B)%MOD = (A%MOD)^B
Since A is very very large number can't be stored in int or long so using modulo technique bring A in the range of int or long as:
Let 'a' be an array contains digit of A so to construct A%MOD. Let A = 0
for i 0 to len(a):
    A = (A*10 + a[i])%MOD
This gives A%MOD

Now B is also very very large but we can't apply same technique as we done in A as
(A%MOD)^B%MOD != (A%MOD)^(B%MOD)%MOD
So we use Fermet's Little Theorem which says:

where p is prime number.
divide by a both side


Since MOD = 10^9+7 is a prime number

we need to find A^B%MOD
so if  B is divisible by (p-1) or (MOD-1) then B = (MOD-1)*x
so (A^((MOD-1)*x))%MOD = (A^(MOD-1)%MOD)^x%MOD = 1^x%MOD = 1

and if B is not divisible by (MOD-1) then B = (MOD-1)*x + y
so
(A^((MOD-1)*x+y))%MOD = ((A^(MOD-1)%MOD)^x)%MOD*(a^y)%MOD =  1^x*(a^y)%MOD
and y = B%(MOD-1)
so y can be computed as:
y = 0
b is an array contains digit of number B.
for i 0 to len(b)
    y = (y*10 + b[i])%(MOD-1)
if y==0
answer = 1
else
answer = A^y%MOD

To View My Solution:
https://github.com/shivam04/codes/blob/master/hackerrank/math/number%20theory/medium/power-of-large-number.py

CODEFORCES: Sereja and Suffixes(368B)

Problem Link: http://codeforces.com/problemset/problem/368/B

Summary:
Given 'n' number of elements in array.

Given 'm' i.e 'm' different queries each query contains an integer 'l'.

Find the number of distinct elements from 'l' to 'n'  in array.

For Example:

input

10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10

output

6
6
6
6
6
5
4
3
2
1

Topic:
Dynamic Programming
Logic:

Let dp[i] be the answer i.e number of distinct elements from i to n.

and dp[i] = dp[i+1] +1 when element at a[i] has not been visited yet or visit[a[i]] = 0 otherwise dp[i] = dp[i+1] i.e visit[a[i]] = 1

For any 'l' print dp[l]  is the answer.

To View my solution:

https://github.com/shivam04/codes/blob/master/codeforces/seerja_and_suffixes.py

HACKER RANK: Journey to the Moon

Problem Link: https://www.hackerrank.com/challenges/journey-to-the-moon

Summary:

There are  trained astronauts numbered from  to . But those in charge of the mission did not receive information about the citizenship of each astronaut. The only information they have is that some particular pairs of astronauts belong to the same country.

Your task is to compute in how many ways they can pick a pair of astronauts belonging to different countries. Assume that you are provided enough pairs to let you identify the groups of astronauts even though you might not know their country directly. For instance, if  are astronauts from the same country; it is sufficient to mention that  and  are pairs of astronauts from the same country without providing information about a third pair .

Print An integer that denotes the number of permissible ways to choose a pair of astronauts.

For Example:

Sample Input:

4 2
0 1
2 3

Sample Output:

4

Topic:

Graph Theory, BFS(Breadth First Search)

Logic:

I have create an adjacency list.

Then Using BFS I have count total number of sub graphs in a graph such that there is no edges between sub graphs and also count total number of nodes in each sub graph.

Then compute number of ways 2 astronauts from different country can be sent to Moon.

For example:

Like From America There are 3 trained astronauts.

From India There are 4 trained astronauts.

From Japan There are 2 trained astronauts.

From China, Australia and Russia There are Only One astronaut.

So number_of_ways = 3*(4+2+1+1+1) + 4*(2+1+1+1) + 2*(1+1+1) + 2 + 1 = 56

To View My Solution:

https://github.com/shivam04/codes/blob/master/hackerrank/algo/graph/medium/journey-to-the-moon.py

HACKER RANK: Play Game

Problem Link: https://www.hackerrank.com/challenges/play-game

Summary:
Given N number of elements in stack.

first line will contain a number N i.e. number of elements in the stack and next line will contain N numbers i.e. numbers etched on bricks from top to bottom.

You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.

Print a single line containing your maximum score.

For Example:

Sample Input:

2

5

999 1 1 1 0

5

0 1 1 1 999

Sample Output:

1001

999

Topic:
Dynamic Programming Approach: https://en.wikipedia.org/wiki/Dynamic_programming

Logic:

I took dp[2][n]

dp[0]->My Score

dp[1]->Minimum Score other player leaves for me as he also play optimally

When n = 1,2,3 then you took all elements in stack

dp[0][n-1]=a[n-1]

dp[0][n-2]=a[n-1]+a[n-2]

dp[0][n-3]=a[n-1]+a[n-2]+a[n-3]

so for i n-4 to 0:

    dp[1][i] = min(dp[0][i+1],min(dp[0][i+2],dp[0][i+3]))

    dp[0][i] = max(a[i]+dp[1][i+1],max(a[i]+a[i+1]+dp[1][i+2],a[i]+a[i+1]+a[i+2]+dp[1][i+3]))

ans = dp[0][0]

print ans

In this code dp[1][i] is minimum left by other player for you when he plays optimally i.e chooses maximum sum of elements for itself.

and dp[0][i] is maximum of taking one element, two element or three element plus minimum left by other player when he chooses maximum sum of elements for itself.

Time Complexity: O(n)

To View My Solution:

https://github.com/shivam04/hackerrank/blob/master/play-game.cpp

HACKER RANK: Red John is Back

Problem Link: https://www.hackerrank.com/challenges/red-john-is-back

Summary:
Given N find number of ways to to arrange 4X1 and 1X4 bricks in 4XN block. Say there are M ways so print P number of prime up to M(i.e. <=M).

For Example:

Sample Input:
4
1
3

Sample Output:
0
3

For N=1
There is only one way so P = 0 as there is no prime number less than M=1

For N=7
there is M=5 ways so answer P=3 as 2,3,5 is less than than and equal to 5.

Topic:
Dynamic Programming Approach: https://en.wikipedia.org/wiki/Dynamic_programming

Logic:
What I have done is take number N as a block of weight N kg and try to adjust weight 1kg and 4kg weight in different ways.
So number of ways can be recursively computed as:
F(n) = F(n-1) + F(n-4)
if we place weight of 1kg then F(n-1) need to be computed.
if we place weight of 4kg then F(n-4) need to be computed.

Then taken sum of all computes M = F(n)

Now using Sieve Of Eratosthenes(http://www.geeksforgeeks.org/sieve-of-eratosthenes/) we compute P number of prime numbers up to M.

To View My Solution:
https://github.com/shivam04/hackerrank/blob/master/red-john-is-back.cpp

HACKER RANK: Common Child

Problem Link: https://www.hackerrank.com/challenges/common-child

Summary:
Given 2 strings of equal length what's the longest string that can be constructed such that it is a child of both.

For example:

Sample Input 1:
HARRY
SALLY

Sample Output 1:
2

Longest possible string is "AY"

Sample Input 2:
ABCDEF
FBDAMN

Sample Output 2:
2

Longest possible string is "BD"

Topic:
Dynamic Programming Approach: https://en.wikipedia.org/wiki/Dynamic_programming
Longest String Subsequence: https://en.wikipedia.org/wiki/Longest_common_substring_problem
                                                http://www.geeksforgeeks.org/longest-common-substring/

My Logic:

Let string str1 = HARRY and str2 = SALLY
So this is how i solved this question using DP(Dynamic Programming).

To view My Solution:
https://github.com/shivam04/hackerrank/blob/master/common-child.java

HACKER RANK: Sherlock and Anagrams

Problem Link: https://www.hackerrank.com/challenges/sherlock-and-anagrams

Given a string S, find the number of "unordered anagrammatic pairs" of substrings.

Input Format

First line contains T, the number of testcases. Each testcase consists of string S in one line.

Constraints 
1≤T≤10 
2≤length(S)≤100 
String S contains only the lowercase letters of the English alphabet.

Output Format

For each testcase, print the required answer in one line.

Logic:

Let's say S[i,j] denotes the substring Si,Si+1,⋯,Sj.

Match Subset Si  With Si+1, ....... Sj For anagram.

To View My Solution:

https://github.com/shivam04/hackerrank/blob/master/sherlock-and-anagrams.java