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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
03/13/15

Codility ‘Max Nonoverlapping Segments’ Solution

Short Problem Definition:

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

Link

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[0]
    
    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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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…

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin