Journey to the Moon : HackerRank

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

Logic : Here constrain is we have to make a pair of two scientists which belongs to two different countries. So, we can relate this problem as graph theory and finding all different connected components(scientist who belong to same country) among whole graph. Then, using combinations, we find total pairs.                                                                                                   Here, I used adjecency list instead of matrix, because I have faced error of Memory Exceed in python3.

Language :  Python3

 

   import queue

#outputq=queue.Queue()

# bfs search function
def bfssearch(snode):
	q=queue.Queue()
	totalcv=0 #total vertex in one connected graph
	q.put(snode)
	visitednode[snode]=1
	totalcv+=1
	#outputq.put(snode)
	while not q.empty():
		source = q.get()
		for j in node:
			if visitednode[j]!=1:
				q.put(j)
				visitednode[j]=1
				totalcv+=1
				#outputq.put(v)
	return totalcv

# finding total number of connected component
def connectednumber():
	return outputq.qsize()

# unvisited node
def unvisitednode():
	i=0
	check=-1                    #all node are visited or not
	while check==-1 and i<totalnode:
		if visitednode[i]==0:
			check=i
		i+=1
	return check		

#main function start

totalnode,edge= list(map(int, input().split(" ")))
aa=[] # list to store total vertex in various connected graph
# adjecency matrix
node = [[]for y  in range(totalnode)]

#mark visited
# 1 if node is visited 0 if not visited . initially set all zero

visitednode = [0 for x in range(totalnode)]
# adding edge in matrix.
for  i in range(0,edge):
	xx,yy = list(map(int, input().split(" ")))
	node[xx].append(yy)
	node[yy].append(xx)

#starting bfs search with 0.
for h in range(0,totalnode):
	if visitednode[h]==0:
		aa.append(bfssearch(h))

#combination calculation
total = (sum(aa)*(sum(aa)-1))//2
for j in aa:
	total-=(j*(j-1))//2
print(total)

Quick Sort

Quick sort is favourite algorithm of most of computer science lovers. Quick sort implemented four ways:

1. Pivot element is first element of array
2. Pivot element is last element of array
3. Random pivot element from array
4. median element of array as pivot

Here, I implemented  this sorting algorihtms by first two ways.

Complexity : 

Average time complexity is O(nlogn). But it depends on how you choose pivot element. So, most efficient is third approach (random element taken as pivot). Looking quite wrong but in real world average of choosing random is always near to target element and it’s the fact!!!!

Pivot element is first element of array :

 #quick sort
#pivot element is first.

# function for partition of an array
def partition(a,start,end):
	pivot=a[start]  # first element as pivot
	i=start;
	for j in range(start+1,end+1):
		if a[j]<pivot:
			a[j],a[i+1]=a[i+1],a[j]   # swapping element with left most greater element than pivot
			i+=1
	# after traversing through array. In last putting pivot element between two list.
	a[start],a[i]=a[i],a[start]
	return i



# quick sort function
def quicksort(a,start,end):
	if start<end:
		mid=partition(a,start,end)
		quicksort(a,start,mid-1)  #left portion
		quicksort(a,mid+1,end)  #right portion


array=[55,14,25,1,10,21,12,17,48,95,58,65,48,47,41,25,36,39,540,124,-4,-7,-5,984,210]
quicksort(array,0,len(array)-1)
print(array)

Pivot element is first element of array :

#Quick sort
#pivot element is last

#function of partition of array
def partition(a,start,end):
	pivot=a[end]     # taking pivot as last element of array
	i=start-1       # taking index to differentiate two list less than pivot and greater than pivot
	for j in range(start,end):
		if a[j]<pivot:
			a[j],a[i+1]=a[i+1],a[j]
			i+=1
	a[end],a[i+1]=a[i+1],a[end]     # swapping pivot element between less and greater than list 
	return i+1



#function for quick sort
def quicksort(a,start,end):
	if start<end:
		mid=partition(a,start,end)  # partitioning array
		quicksort(a,start,mid-1)  # left portion
		quicksort(a,mid+1,end)	  #right portion


array=[55,14,25,1,10,21,12,17,48,95,58,65,48,47,41,25,36,39,540,124,-4,-7,-5,984,210]
quicksort(array,0,len(array)-1)
print(array)

Special Case(Height is 1 ) : There is no divisor of 1 that <1. So always 2nd player win.Because 1st player have no move.

Problem :

My Logic : 

Total Towers are Even :- Assume that the towers are separated into two groups having an equal number of towers in each group. Both players are playing optimally, 2nd player just copied 1st players’s move.                             Hence, when total towers are even then 2nd players always follow 1st players move. At the end 1st player have no move to play. So, 2nd player always win in this case.

Total Towers are Odd :-  Same explaination as above but when total towers are odd then at the end after move of 1st player, 2nd player have no chance to move. Hence 1st player would win the game.

Language : Python3

 

 #Tower Breaker : HackerRank : Game Theory
t=int(input())
for i in range(t):
    n,m=list(map(int,input().split(" ")))
    print("2" if (n%2==0)or(m==1) else "1" )

Game of Stones : HackerRank

Problem :  https://www.hackerrank.com/challenges/game-of-stones-1

My Logic : In problem, it’s given that Player 1 would move always optimally so, he could win.So, the possibilities of his win is possible when at his turn stones are remaining 2 or 3 or 4 or 5 or 6. Because in this situation he will win by removing accordingly 2,3 or 5 stones. So, here O(1) solution is if stones%7>1 then First player will win otherwise Second player. 

Language : Python3

 

  #Game of Stones : Game Theory : HackerRank
stone=int(input())
for i in range(0,stone):
    print("First" if int(input())%7>1 else "Second")

Beautiful Pairs : Hacker Rank

Problem : https://www.hackerrank.com/challenges/beautiful-pairs

Logic : Straight forward logic it is. Finding similar pairs which index occur exactaly once.So, I am using dictionary in python 3, use map in c++ or in java and counting the occurance of numbers and then minimum occurance from both array are desire number of pairs.

Language : Python3

 

import math
n=int(input())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
da={}
db={}
ask=[]
cost=0
for i in a:
    if i in da:
        da[i]+=1
    else:
        da[i]=1
        ask.append(i)
for j in b:
	if j in db:
		db[j]+=1
	else:
		db[j]=1
for k in da:
    if k in db:
        cost+=min(da[k],db[k])
    #cost+=min(da[k],db[k])
if cost==n:
	cost-=1
else:
	cost+=1
print(cost)
		

Cutting Board : Hacker Rank

Problem : https://www.hackerrank.com/challenges/board-cutting

Logic :  We want to minimum cost. First we sort both horizontal and vertical cost array and start with largest element form both array, because cost is derived from total cutting edges multiply with horizontal or vertical cost. So, minimum cost has been derived by minimum cost multiply with cutting edge.

Language : Python3

 

## Cutting Boards  Greedy ###
## Cutting Boards  Greedy ###
t=int(input())
for i in range(t):
    row,column = list(map(int,input().split()))
    xa= list(map(int,input().split()))
    ya= list(map(int,input().split()))
    xa.sort()
    ya.sort()
    xarr=xa[::-1]
    yarr=ya[::-1]
    pivot_x=0
    pivot_y=0
    cost=0
    cutedge_x=1
    cutedge_y=1
    while pivot_x<row-1 and pivot_y<column-1:
        if xarr[pivot_x]>yarr[pivot_y]:   #horizontal cost is greater than vertical cost
            cost+=cutedge_y*xarr[pivot_x]
            cutedge_x+=1
            pivot_x+=1
        else:
            cost+=cutedge_x*yarr[pivot_y]      #vertical cost is greater than horizontal cost
            cutedge_y+=1
            pivot_y+=1
    while pivot_x>=row-1 and pivot_y<column-1:   # adding remaining vertical cost
        cost+=cutedge_x*yarr[pivot_y]
        cutedge_y+=1
        pivot_y+=1
    while pivot_x<row-1 and pivot_y>=column-1:   # adding remaining horizontal cost
        cost+=cutedge_y*xarr[pivot_x]
        cutedge_x+=1
        pivot_x+=1
    print(cost%1000000007)

Stock Maximize – HackerRank

Problem : HackerRank – Algorithms – Dynamic Programming – Stock Maximize.

My Logic :  Start with 1st price and find the maximum price after starting price. Now till buy shares till maximum price index – 1 and add total cost. Then subtract from maximum price*total share purchased. Recursively perform this operation till last price.

Language : Python3

profit=0
def stockp(a,current,last):
    arr=a
    c=current
    l=last
    cnt=0
    cost=0
    maxn=-1
    global profit
    for k in range(c,l+1):  # finding maximum price
        if arr[k]>maxn:
            maxn=arr[k]
    while(c!=l and a[c]<maxn):
        cost+=a[c]
        c+=1
        cnt+=1
    profit+=(cnt)*a[c] - cost #total profit added here
    if(c!=l):
        stockp(a,c+1,l) #recursively continue above process
t=int(input())
for i in range(t):
    price=list(map(int,input().split()))
    stockp(price,0,len(price)-1) 
    print(profit)

Google Code Jam 2016-Practise – Spelling Bee

Got full points on both small and large input submissions.

t=int(input())
for i in range(0,t):
	s=input()
	a=list(s)
	ans=1
	if len(a)!=1:
		for j in range(1,len(a)-1):
			if a[j-1] ==a[j+1] and a[j]!=a[j-1]:
				ans=ans*2
			else:
				if a[j]==a[j-1] and a[j]!=a[j+1] :
					ans=ans*2
				else:
					ans=ans*1

				if a[j]==a[j+1]  and a[j]!=a[j-1]:
					ans=ans*2
				else:
					ans=ans*1

				if a[j]!=a[j-1] and a[j]!=a[j+1]:
					ans=ans*3
		if a[0]!=a[1]:
			ans=ans*2
		if a[len(a)-1]!=a[len(a)-2]:
			ans=ans*2
	else:
		ans=1
	print('Case #'+str(i+1)+':',ans)		

Google Code Jam – All Your Credit

Successfully accepted both smaller and larger inputs.

t = int(input())
printindex=1
for i in range(0,t):

    cash=int(input())
    n = int(input())
    toy = list(map(int, input().split()))
    a=toy[:]
    a.sort()
    last = len(a)
    start = last/2
    s= False
    n1=0
    n2=0

    for x in range(0,last):

        for y in range(x+1,last):

            if (a[x]+a[y])>cash:
                last=y
                break
            elif(a[x]+a[y])==cash:
                s=True

                n1=a[x]
                n2=a[y]
                break
        if s==True:
            break
    i1=toy.index(n1)+1
    i2=toy.index(n2)+1
    if i1==i2:
        i2=i2+1
    print('Case #'+str(printindex)+':',min(i1,i2),max(i1,i2))
    printindex=printindex+1

HackerRank – Sherlock and The Beast

My Logic : We have to make a number which contain only 3 and 5, where total number of 3 divisible by 5 and total number of 5 divisible by 3.

•  So, i took first total number  of 5 as given number because we want to print largest number so literraly num. of 5 should be > num. of 3. Set num.of 5 which divisible by 3.Then num. of 3 = input – num. of 5.
• For largest number first print all 5’s then 3’s.

Language : java

//Author : Ashutosh Kakadiya
//HackerRank - Sherlock and the Beast
import java.io.*;
import java.util.*;

public class Solution {

 public static void main(String[] args) {
     Scanner s = new Scanner(System.in);
     int number = s.nextInt();
     for(int i=0;i<number;i++){
        int digit = s.nextInt();
        int temp=digit;
        while(temp%3!=0){
          temp-=5;
        }
       if(temp< 0){ System.out.println("-1");}
       else{
       for(int j=0;j<temp;j++){ System.out.print("5");}
       for(int j=0;j<digit-temp;j++){ System.out.print("3");}
       System.out.println();
     }
   }
 }
}