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

HACKER RANK: The Grid Search

Problem Link: https://www.hackerrank.com/challenges/the-grid-search

Summary:
Given a 2D array of digits, try to find the occurrence of a given 2D pattern of digits.

1234567890  
0987654321  
1111111111  
1111111111  
2222222222  

Assume we need to look for the following 2D pattern:

876543  
111111  
111111

If we scan through the original array, we observe that the 2D pattern begins at the second row and the third column of the larger grid (the 8 in the second row and third column of the larger grid is the top-left corner of the pattern we are searching for).

So, a 2D pattern of P digits is said to be present in a larger grid G, if the latter contains a contiguous, rectangular 2D grid of digits matching with the pattern P, similar to the example shown above.

Logic:

Match element by element for small array in large array.

To View My Solution:

https://github.com/shivam04/hackerrank/blob/master/the-grid-search.cpp

SPOJ PROBLEM 21079. THE RESISTANCE

Problem Link: http://www.spoj.com/problems/RESSTNCE/

SUMMARY:
In this problem, we are constructing a long network of resistors composed of N blocks. Every block has two 1 ohm resistors, shown below by the upper-left figure. We would like for you to measure the net resistance across the two leftmost terminals in a circuit with N blocks. If the circuit has one block (N=1), then the net resistance across the leftmost terminals is 1 ohm, because the horizontal resistor is not in a path connecting the leftmost terminals. Similarly, for a circuit with two blocks (N=2), the net resistance is 2/3 ohms. The figures below illustrate this.

Logic:
ans = (fibo(2n-1)%m)/(fibo(2n)%m)

To View My Solution:

https://github.com/shivam04/spoj/blob/master/RESSTNCE.cpp

SPOJ PROBLEM 8001. FIBONACCI SUM

Problem Link: http://www.spoj.com/SPOJ/problems/FIBOSUM/

SUMMARY:

The fibonacci sequence is defined by the following relation:

F(0) = 0

F(1) = 1

F(N) = F(N - 1) + F(N - 2), N >= 2

Your task is very simple. Given two non-negative integers N and M, you have to calculate the sum (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.

Logic:

What I have done is that I used matrix powers a nice way to find F[n] (nth term of Fibonacci Series) 

you can calculate this using fast matrix exponentiation i.e nth power of the matrix above at L.H.S gives you the value of (n+1)th Fibonacci number as the element at row and column (1,1) in the resultant matrix. 

at first try to write the first few Fibonacci numbers:
0  1  1  2  3  5  8  13  21  34  55

now write the sum of Fibonacci numbers from 0 to i:
0  1  2  4  7  12  20  33  54

looking the pattern given above we found that

Sum(N) = F(N+2) ---------> (1)

where sum(N) is sum up to Nth term of Fibonacci series

and the simple way to calculate the sum of all the numbers b/w "N" and "M" is: sum(M)-sum(N-1)

so (F(N) + F(N + 1) + ... + F(M)) mod 1000000007 = (sum(M)-sum(N-1)) mod 1000000007

from (1)

sum(M) = F(M+2) and

sum(N-1) = F(N+1)

now the final results become:

(F(N) + F(N + 1) + ... + F(M)) mod 1000000007 = (F(M+2)-F(N+1))mod 1000000007

To View My Solution:

https://github.com/shivam04/spoj/blob/master/FIBOSUM

SPOJ PROBLEM 21332. PIGEONHOLE TOWER

Problem Link: http://www.spoj.com/problems/PHT/

SUMMARY:

Pigeon SSNA want to build a tower with some wood walls. Let's describe the tower they want to make:

1. A Tower can consist of different number of level.
2. If a tower contain L levels then 1^st level must contain L  holes , 2^nd level L-1 , 3^rd level L-2 ….. L level contain 1 hole .
3. Each room contain 3 wood walls.

See the picture below:

                                                     

                                           3 Level Tower                                      4 Level tower

Now pigeon SSNA has n wood walls. What is maximum number of level he can made. 

Logic:

It's a simple mathematics based on n*(n+2) gives you the required solution so we have to find only the value of n.  

To View My Solution:

https://github.com/shivam04/spoj/blob/master/PHT.cpp