03/17/15

# HackerRank ‘Cut the sticks’ Solution

##### Short Problem Definition:

You are given N sticks, where each stick has the length of a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.

Cut the sticks

##### Complexity:

time complexity is O(n*log(n))

space complexity is O(n)

##### Execution:

Cutting every stick will result in O(N^2) which is not required. Sorting the array requires nlogn time. Python pop() requires O(1) time and importantly it does not rearrange or reallocate the array.

With each step, remove all elements from the list (actually a stack/queue) that have the same value and print the size of the remaining list.

##### Solution:
#!/usr/bin/py
def computeSticks(arr):
arr.sort(reverse=True)
while len(arr) > 0:
print len(arr)
block_cut = arr.pop()
while len(arr) > 0 and arr[-1] <= block_cut:
arr.pop()

if __name__ == '__main__':
n = int(raw_input())
arr = map(int, raw_input().split())
computeSticks(arr)


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/16/15

# HackerRank ‘Cavity Map’ Solution

##### Short Problem Definition:

You are given a square map of size n×n. Each cell of the map has a value denoting its depth. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has strictly smaller depth. Two cells are adjacent if they have a common side.

Cavity Map

##### Complexity:

time complexity is O(N^2)

space complexity is O(1)

##### Execution:

*pun* You only get your cavities checked on an airport */pun*

I check all 4 surrounding elements if they are strictly smaller. If so, I mark the position with an ‘X’.  Better runtime than n^2 is not possible as every element has to be visited!

##### Solution:
#!/usr/bin/py

def transformCavity(arr, n):
for idx_tb in xrange(1, n-1):
for idx_lr in xrange(1, n-1):
if arr[idx_tb-1][idx_lr] != 'X' and int(arr[idx_tb-1][idx_lr]) < int(arr[idx_tb][idx_lr]) and \
arr[idx_tb+1][idx_lr] != 'X' and int(arr[idx_tb+1][idx_lr]) < int(arr[idx_tb][idx_lr]) and \
arr[idx_tb][idx_lr-1] != 'X' and int(arr[idx_tb][idx_lr-1]) < int(arr[idx_tb][idx_lr]) and \
arr[idx_tb][idx_lr+1] != 'X' and int(arr[idx_tb][idx_lr+1]) < int(arr[idx_tb][idx_lr]):
arr[idx_tb][idx_lr] = 'X'

if __name__ == '__main__':
n = input()

arr = []

for _ in xrange(n):
line = list(raw_input())
arr.append(line)

transformCavity(arr, n)

for line in arr:
print ''.join(line)


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/15/15

# HackerRank ‘Taum and B’day’ Solution

##### Short Problem Definition:

Taum is planning to celebrate the birthday of his friend Diksha. There are two types of gifts that Diksha wants from Taum: one is black and the other is white. To make her happy, Taum has to buy B number of black gifts and W number of white gifts.

Taum and B’day

##### Complexity:

time complexity is O(1)

space complexity is O(1)

##### Execution:

The cost for each present is either the cost of its category, or the cost of the other category + the conversion cost. Just select the minimum.

##### Solution:
#!/usr/bin/py
if __name__ == '__main__':
t = input()
for _ in xrange(t):
b, w = map(int, raw_input().split())
x, y, z = map(int, raw_input().split())

print min(b*x, b*(y+z)) + min(w*(x+z), w*y)


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/14/15

# HackerRank ‘Is Fibo’ Solution

##### Short Problem Definition:

You are given an integer, N. Write a program to determine if N is an element of the Fibonacci sequence.

Is Fibo

##### Complexity:

time complexity is O(15√(ϕn−(−ϕ)−n))

space complexity is O(15√(ϕn−(−ϕ)−n))

##### Execution:

There are two methods:

A) generate all fibonacci numbers up to N and check if the candidates are in this set.

B) There is a mathematical function that can prove whether a number is in the Fibonacci sequence in sqrt(N) time. I am not going to explain this here. Read the discussion on SO if you are interested.

##### Solution:
#!/usr/bin/py
def getFibo(N):
v = [1,2]
while v[-1] < N:
v.append(v[-1]+v[-2])

return set(v)

def isFibo(fiboSet, value):
if value in fiboSet:
return "IsFibo"
return "IsNotFibo"

if __name__ == '__main__':
t = input()
values = []
for _ in xrange(t):
values.append(input())

fiboSet = getFibo(max(values))

for value in values:
print isFibo(fiboSet, value)


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/13/15

# Codility ‘Max Nonoverlapping Segments’ Solution

##### Short Problem Definition:

Find a maximal set of non((-))overlapping segments.

MaxNonoverlappingSegments

##### Complexity:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)

##### Execution:

This can be solved by using greedy search. The beginning of the next segment must come strictly after its predecessor.

##### Solution:
def solution(A, B):
if len(A) < 1:
return 0

cnt = 1
prev_end = B

for idx in xrange(1, len(A)):
if A[idx] > prev_end:
cnt += 1
prev_end = B[idx]

return cnt


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/12/15

# HackerRank ‘Two Strings’ Solution

##### Short Problem Definition:

You are given two strings, A and B. Find if there is a substring that appears in both A and B.

Two Strings

##### Complexity:

time complexity is O(N+M);

space complexity is O(1)

##### Execution:

At first sight this seems like a longest common substring problem. It is actually much easier. You just need to find out if there are two equal letters in both strings A and B.

##### Solution:
#!/usr/bin/py
def twoStrings(s1, s2):
m1 = set(s1)
m2 = set(s2)
if set.intersection(m1,m2):
return "YES"
return "NO"

if __name__ == '__main__':
t = input()
for _ in xrange(t):
first = raw_input()
second = raw_input()
print twoStrings(first, second)



If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/11/15

# HackerRank ‘AngryProfessor’ Solution

##### Short Problem Definition:

The professor is conducting a course on Discrete Mathematics to a class of N students. He is angry at the lack of their discipline, and he decides to cancel the class if there are less than K students present after the class starts.

Given the arrival time of each student, your task is to find out if the class gets cancelled or not.

Angry Professor

##### Complexity:

time complexity is O(N);

space complexity is O(1)

##### Execution:

Just count all students with arrival time <= 0.

##### Solution:
#!/usr/bin/py
if __name__ == '__main__':
t = input()
for _ in xrange(t):
n, m = map(int, raw_input().split())
A = map(int, raw_input().split())
for x in A:
if x <= 0:
m -= 1
if m <= 0:
print "NO"
else:
print "YES"


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/10/15

# HackerRank ‘Find Digits’ Solution

##### Short Problem Definition:

You are given an integer N. Find the digits in this number that exactly divide N (division that leaves 0 as remainder) and display their count. For N=24, there are 2 digits (2 & 4). Both of these digits exactly divide 24. So our answer is 2.

Find Digits

##### Complexity:

time complexity is O(N);

space complexity is O(1)

##### Execution:

Just follow the problem description. The problem can be optimized by creating a map of digits and their counts.

##### Solution:
#!/usr/bin/py
if __name__ == '__main__':
t = input()
for _ in xrange(t):
a = input()
count = 0
for i in list(str(a)):
if int(i) != 0 and a % int(i) == 0:
count += 1
print count


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/8/15

# HackerRank ‘Sherlock and GCD’ Solution

##### Short Problem Definition:

Sherlock is stuck while solving a problem: Given an array A={a1,a2,..aN}, he wants to know if there exists a subset, B={ai1,ai2,…aik} where 1≤i1<i2<…<ik≤N…

Sherlock and GCD

##### Complexity:

time complexity is O(N);

space complexity is O(1)

##### Execution:

A subset has no common divisor if the GCD equals 1. There is an interesting fact that leads to my solution: If any subset has GCD 1, any bigger set containing this set will also have GCD 1. Therefore GCD(a,b,c,d) = GCD(GCD(GCD(a,b),c),d). This is easily generated by python reduce.

Beware: The problem statement allows n==1.

##### Solution:
#!/usr/bin/py
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)

def multiple_gcd(numbers):
return reduce(lambda x,y: gcd(x,y), numbers)

if __name__ == '__main__':
t = input()
for _ in xrange(t):
n = input()
values = map(int, raw_input().split())
if len(values) < 2:
print "NO"
continue
if (multiple_gcd(values) == 1):
print "YES"
else:
print "NO"


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/7/15

# HackerRank ‘Manasa and Stones’ Solution

##### Short Problem Definition:

Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either aor b. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 0, find all the possible values for the number on the last stone.

Manasa and Stones

##### Complexity:

time complexity is O(N);

space complexity is O(N)

##### Execution:

There are two distinct values. It is basically a combination with repetition. The order of the stones does not matter.

##### Solution:
#!/usr/bin/py

def manasa(n, a, b):
solutions = set()
for i in xrange(n):
solutions.add(a * i + b * (n-i-1))

return solutions

if __name__ == '__main__':
t = input()
for _ in xrange(t):
n = input()
a = input()
b = input()
l = sorted(list(manasa(n, a, b)))
print ' '.join(map(str, l))


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.