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

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