08/5/16

HackerRank ‘Non-Divisible Subset’ Solution

Short Problem Definition:

Given a set S of n distinct integers, print the size of a maximal subset S’ of S where the sum of any 2 numbers in S’ are not evenly divisible by k.

Link

Non-Divisible Subset

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

This is by all means not an easy task and is also reflected by the high failure ratio of the participants. For a sum of two numbers to be evenly divisible by k the following condition has to hold. If the remainder of N1%k == r then N2%k = k-r for N1+N2 % k == 0. Let us calculate the set of all numbers with a remainder of r and k-r and pick the larger set. If the remainder is half of k such as 2 % 4 = 2 or exactly k such as 4 % 4 = 0, just one number from each of these sets can be contained in S’.

Solution:
def solveSubset(S, k, n):
    r = [0] * k
    
    for value in S:
        r[value%k] += 1
    
    result = 0
    for a in xrange(1, (k+1)//2):
        result += max(r[a], r[k-a])
    if k % 2 == 0 and r[k//2]:
        result += 1
    if r[0]:
        result += 1
    return result
    
n, k = map(int, raw_input().split())
S = map(int, raw_input().split())
print solveSubset(S, k, n)

use std::io;

fn get_numbers() -> Vec<u32> {
    let mut line = String::new();
    io::stdin().read_line(&mut line).ok().expect("Failed to read line");
    line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn calculate_nondivisible(a: Vec<u32>, n: usize, k: usize) -> u32 {
    let mut result = 0;
    
    let mut r = vec![0; k];
    for val in a {
        r[(val as usize)%k] += 1;
    }
    
    for idx in 1..(k+1)/2 {
        result += std::cmp::max(r[idx as usize], r[(k-idx) as usize]);
    }
    
    if k % 2 == 0 && r[k/2] != 0 {
        result += 1;
    }
    if r[0] != 0 {
        result += 1;
    }
    
    result
}

fn main() {
    let line = get_numbers();
    let a = get_numbers();
 
    println!("{}", calculate_nondivisible(a, line[0] as usize, line[1] as usize) );
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/1/16

HackerRank ‘Jumping on the Clouds: Revisited’ Solution

Short Problem Definition:

Aerith is playing a cloud game! In this game, there are clouds numbered sequentially from 1 to n. Each cloud is either an ordinary cloud or a thundercloud. Given the values of n and k the configuration of the clouds, can you determine the final value of e after the game ends?

Link

Jumping on the Clouds: Revisited

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Simulate the game in a loop.

Solution:
#!/bin/python

def solveCloudRevisited(c, n, k):
    pos = 0
    cnt = 0

    while cnt == 0 or pos != 0:
        pos += k
        pos %= n
        if c[pos] == 0:
            cnt += 1
        else:
            cnt += 3
    
    return 100 - cnt

if __name__ == '__main__':
    n,k = map(int,raw_input().strip().split(' '))
    c = map(int,raw_input().strip().split(' '))
    print solveCloudRevisited(c, n, k)

use std::io;

fn get_numbers() -&gt; Vec&lt;u32&gt; {
    let mut line = String::new();
    io::stdin().read_line(&amp;mut line).ok().expect("Failed to read line");
    line.split_whitespace().map(|s| s.parse::&lt;u32&gt;().unwrap()).collect()
}

fn calculate_jumping(a: Vec&lt;u32&gt;, n: usize, k: usize) -&gt; u32 {
    let mut e = 0;
    let mut pos = 0;
    
    while e == 0 || pos != 0 {
        e += match a[pos] {
            0 =&gt; 1,
            1 =&gt; 3,
            _ =&gt; panic!("invalid input"),
        };
        
        pos += k;
        pos %= n;
    }
    
    100 - e
}

fn main() {
    let line = get_numbers();
    let (n, k) = (line[0], line[1]);
    let a = get_numbers();
    println!("{}", calculate_jumping(a, n as usize, k as usize) );
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
07/3/16

HackerRank ‘Divisible Sum Pairs’ Solution

Short Problem Definition:

You are given an array of n integers and a positive integer, k. Find and print the number of (i,j) pairs where i < j and ai + aj is evenly divisible by k.

Link

Divisible Sum Pairs

Complexity:

time complexity is O(N^2)

space complexity is O(1)

Execution:

Brute force search.

Solution:
n,k = raw_input().strip().split(' ')
n,k = [int(n),int(k)]
a = map(int,raw_input().strip().split(' '))
count=0
for i in xrange(len(a)):
    for j in xrange(i+1,len(a)):
        if (a[i]+a[j]) % k == 0:
            count+=1
        
print count

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/22/16

HackerRank ‘Lisas Workbook’ Solution

Short Problem Definition:

Lisa just got a new math workbook. A workbook contains exercise problems, grouped into chapters.

  • …..

Lisa believes a problem to be special if its index (within a chapter) is the same as the page number where it’s located. Given the details for Lisa’s workbook, can you count its number of special problems?

Link

Lisa’s Workbook

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

This brute force solution iterates over all pages in the final book keeping track of the page(offset) and chapter it is on. There can only be one special problem per page and therefore I check if there is any problem that would match the criteria.

Solution:
def findPages(N, K, P):
    cnt = 0
    offset = 1
    for chapter in P:
        pages = (chapter + K -1)/K
        for idx in xrange(pages):
            if offset >= (idx * K)+1 and offset <= min((idx+1)*K, chapter):
                cnt += 1
            offset += 1

    return cnt

if __name__ == '__main__':
    N, K = map(int, raw_input().split())
    P = map(int, raw_input().split())
    print findPages(N, K, P)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/21/16

HackerRank ‘Sherlock and The Beast’ Solution

Short Problem Definition:

Sherlock Holmes suspects his archenemy, Professor Moriarty, is once again plotting something diabolical. Sherlock’s companion, Dr. Watson, suggests Moriarty may be responsible for MI6’s recent issues with their supercomputer, The Beast.

Shortly after resolving to investigate, Sherlock receives a note from Moriarty boasting about infecting The Beastwith a virus; however, he also gives him a clue—a number, . Sherlock determines the key to removing the virus is to find the largest Decent Number having digits.

Link

Sherlock and The Beast

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

I am presenting two solutions. The naive brute force solution executes in O(N) and passes all the tests. Yet further optimisations and a runtime complexity of O(1) are possible.

When observing the possible output space we realise that there can only be 0, 5 or 10 threes in the output. If there would be 15 threes, it is better to use fives instead. The number of trailing threes can therefore be defined by K = 5*((2*N)%3). Let us plug some numbers into the equation:

  • 1 -> 5*(2%3) = 10 -> INVALID
  • 2 -> 5*(4%3) = 5 -> INVALID
  • 3 -> 5*(3%3) = 0 -> 555
  • 4 -> 5*(8%3) = 10 -> INVALID
  • 5 -> 5*(10%3) = 5 -> 33-33-3
  • 8 -> 5*(16%3) = 5 -> 555-33-33-3
  • 10 -> 5*(20%3) = 10 -> 33-33-33-33-33
  • 15 -> 5*(30%3) = 0 -> 555-555-555-555-555
Solution:
def sherlockBeast(N):
    K = 5*((2*N)%3)
    if K > N:
        return -1
    else:
        return '5' * (N-K) + '3'*K

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        n = input()
        print sherlockBeast(n)
def sherlockBeastNaive(N):
    if (N < 3): return "-1" three_cnt = N//3 five_cnt = 0 while three_cnt >=0:
        rem = N - three_cnt*3
        if rem % 5 == 0:
            five_cnt = rem/5
            break
        three_cnt -= 1
        
    if three_cnt <= 0 and five_cnt == 0:
        return "-1"
    
    return "555"*three_cnt + "33333"*five_cnt

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        n = input()
        print sherlockBeastNaive(n)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
05/13/16

HackerRank ‘Bigger is Greater’ Solution

Short Problem Definition:

Given a word w, rearrange the letters of w to construct another word in such a way that is lexicographically greater than w. In case of multiple possible answers, find the lexicographically smallest one among them.

Link

Bigger is Greater

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

This task challenges us to find the next permutation of any given array. There are many implementations available online and it is worthwhile comparing them . I would recommend reading the article by Nayuki or re-implementing the std::next_permutation.

Solution:
def next_permutation(arr):
    # Find non-increasing suffix
    i = len(arr) - 1
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        return False
    
    # Find successor to pivot
    j = len(arr) - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]
    
    # Reverse suffix
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    return True 
        
def main():
    t = input()
    for _ in xrange(t):
        s = list(raw_input())
        if next_permutation(s):
            print "".join(s)
        else:
            print "no answer"
    
if __name__ == '__main__':
    main()

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/4/16

HackerRank ‘Castle on the Grid’ Solution

Short Problem Definition:

You are given a grid with both sides equal to N/N. Rows and columns are numbered from 0/0 to N−1/N−1. There is a castle on the intersection of the aath row and the bbth column.

Your task is to calculate the minimum number of steps it would take to move the castle from its initial position to the goal position (c/d).

It is guaranteed that it is possible to reach the goal position from the initial position.

Link

Castle on the Grid

Complexity:

time complexity is O(N^2) or O(N^3)

space complexity is O(N^2)

Execution:

This solution works with the task as a 2D array. There are options available where you treat the task as a graph problem. In both cases each node it visited exactly once using BFS. On each node, I generate all nodes that are connected to this node in a straight line that is not broken by a ‘X’. I keep the distance data (integer) in the array itself. I store the nodes that have to be visited in a FIFO queue. Once the top element in the queue is the end, I terminate the algorithm. The data stored in the array are these:

  • X        – blocked
  • .          – not visited yet
  • (int)   – already visited. Value is the number of steps from the beginning.
Solution:
from collections import deque

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __str__(self):
        return "X=%d,Y=%d" % (self.x, self.y)

def getPointsFromPoint(N, arr, point):
    x = point.x
    y = point.y
    points = []
    
    while x > 0:
        x -= 1
        if arr[x][y] == 'X':
            break
        points.append(Point(x,y))
    
    x = point.x
    while x < N-1: 
        x += 1 
        if arr[x][y] == 'X': 
            break 
        points.append(Point(x,y)) 
    
    x = point.x 
    while y > 0:
        y -= 1
        if arr[x][y] == 'X':
            break
        points.append(Point(x,y))
    
    y = point.y
    while y < N-1:
        y += 1
        if arr[x][y] == 'X':
            break
        points.append(Point(x,y))
        
    return points
    
def solveCastleGrid(N, arr, start, end):
    q = deque([start])
    arr[start.x][start.y] = 0
    
    while q:
        current_point = q.pop()
        current_distance = arr[current_point.x][current_point.y]
        
        points = getPointsFromPoint(N, arr, current_point)
        for p in points:
            if arr[p.x][p.y] == '.':
                arr[p.x][p.y] = current_distance + 1
                q.appendleft(p)
                if p.x == end.x and p.y == end.y:
                    return current_distance + 1
    return -1
    
if __name__ == '__main__':
    N = input()
    arr = [0] * N
    
    for i in xrange(N):
        arr[i] = list(raw_input())
        
    start_x, start_y, end_x, end_y = map(int, raw_input().split())
    
    print solveCastleGrid(N, arr, Point(start_x, start_y), Point(end_x, end_y))

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/23/16

HackerRank ‘Sherlock and Valid String’ Solution

Short Problem Definition:

A “valid” string is a string S such that for all distinct characters in S each such character occurs the same number of times in S.

Link

Sherlock and Valid String

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

I optimised this solution to the minimal case that passes all tests on HackerRank. It seems that each character occurs 1 or 2 times. I did not pay the Hackos to verify the input :). The logic of the solution is as follows: count the character counts for each character.

  • if they are all equal – it means that all characters occur exactly N times and there is no removal needed
  • if 2 or more have less or more characters – there is no way to fix the string in just 1 removal
  • if exactly 1 char has a different count than all other characters – remove this char completely and S is fixed.
Solution:
from collections import Counter


def isValid(S):
    char_map = Counter(S)
    char_occurence_map = Counter(char_map.values())

    if len(char_occurence_map) == 1:
        return True

    if len(char_occurence_map) == 2:
        for v in char_occurence_map.values():
            if v == 1:
                return True

    return False


S = raw_input()
if isValid(S):
    print "YES"
else:
    print "NO"

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/11/16

HackerRank ‘Poisonous Plants’ Solution

Short Problem Definition:

There are NN plants in a garden. Each of these plants has been added with some amount of pesticide. After each day, if any plant has more pesticide than the plant at its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each plant. Print the number of days after which no plant dies, i.e. the time after which there are no plants with more pesticide content than the plant to their left.

Link

Poisonous Plants

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

 

This challenge was really hard. I could not figure it out for a long time. The part with the stack is pretty obvious, but I missed the fact that older plants can have higher daysAlive values.

Solution:
class Plant:
    def __init__(self, pesticide, days):
        self.pesticide = pesticide
        self.days = days

def solvePlants(a):
    stack = []
    maxDaysAlive = 0
    
    for pesticide in a:
        daysAlive = 0
        while stack and pesticide <= stack[-1].pesticide:
            daysAlive = max(daysAlive, stack.pop().days)
            
        if not stack:
            daysAlive = 0
        else:
            daysAlive += 1
            
        maxDaysAlive = max(maxDaysAlive, daysAlive)
        
        stack.append(Plant(pesticide, daysAlive))
    
    print maxDaysAlive

def main():
    N = input()
     
    numbers = map(int, raw_input().split())
     
    solvePlants(numbers)
     
 
if __name__ == '__main__':
    main()

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/10/16

HackerRank ‘Waiter’ Solution

Short Problem Definition:

You are a waiter at a party. There are NN stacked plates. Each plate has a number written on it. You start picking up the plates from the top one by one and check whether the number written on the plate is divisible by a prime….

Link

Waiter

Complexity:

time complexity is O(N*Q)

space complexity is O(N)

Execution:

First of all, generate primes using Sieve, or copy-paste a list of pre-generated primes. After each iteration the order of the remaining plates is reversed (you put the last on top and once finished you start from the top). That means that the solution has to have a stack, not a queue.

It is not possible to solve this in one pass. I would love to find such a solution.

Solution:
generated_primes = [...]

def solveWaiter(N, Q, numbers):
    stack = []
    
    for value in numbers:
        if value % generated_primes[0] != 0:
            stack.append(value)
        else:
            print value
    
    
    for prime_idx in xrange(1, Q):
        leftover = []
        
        while stack:
            value = stack.pop()
            if value % generated_primes[prime_idx] != 0:
                leftover.append(value)
            else:
                print value
        stack = leftover
    
    for value in stack:
        print value

def main():
    N, Q = map(int, raw_input().split())
    
    numbers = map(int, raw_input().split())
    
    solveWaiter(N, Q, numbers)
    

if __name__ == '__main__':
    main()


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

Facebooktwittergoogle_plusredditpinterestlinkedin