06/30/15

Codility ‘TrekAndSwim’ 2015 Argon Solution

Short Problem Definition:

Find a longest slice of a binary array that can be split into two parts: in the left part, 0 should be the leader; in the right part, 1 should be the leader.

Link

Trek and Swim

Complexity:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)

Execution:

The PHP solution is by Rastislav Chynoransky. The Python code and an execution explanation will follow shortly.

Solution:
/**
 * @author Rastislav Chynoransky
 */
function solution($A) {
    $sum = 0;
    for ($i = 0; $i < count($A); $i++) {
        $sum += !$A[$i];
        $zeros[] = $sum;
    }

    $sum = 0;
    for ($i = count($A); $i--;) {
        $sum += $A[$i];
        $ones[$i] = $sum;
    }

    for ($i = count($A) - 1; $i--;) {
        $res[$i] = ($zeros[$i] + $ones[$i]) * ($A[$i + 1] - $A[$i]);
    }

    $max = max($res);

    if ($max <= 0) {
        return 0;
    }

    $index = array_search($max, $res);

    $right = 0;
    $sum = 0;
    for ($i = $index + 1; $i < count($A); $i++) {
        $sum += $A[$i];
        if (2 * $sum / ($i - $index) > 1) {
            $right = $i - $index;
        }
    }

    $left = 0;
    $sum = 0;
    for ($i = $index; $i >= 0; $i--) {
        $sum += !$A[$i];
        if (2 * $sum / ($index - $i + 1) > 1) {
            $left = $index - $i + 1;
        }
    }

    return $left + $right;
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/24/15

HackerRank ‘Song of Pi’ Solution

Short Problem Definition:

That’s the value of pi! (Ignoring the floating point) A song is a pi song if the length of its words represent the value of pi.

Link

Song of Pi

Complexity:

time complexity is O(N*T)

space complexity is O(N)

Execution:

 

This problem is straight forward.

Solution:
#!/usr/bin/py

PI = map(int, list("31415926535897932384626433833"))

def isPiSong(s):
    for idx, word in enumerate(s):
        if len(word) != PI[idx]:
            return False    
    return True
    
if __name__ == '__main__':
    t = input()
    for _ in range(t):
    	s = raw_input().split()
        if isPiSong(s):
            print "It's a pi song."
        else:
            print "It's not a pi song."

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/23/15

HackerRank ‘Identify Smith Numbers’ Solution

Short Problem Definition:

A Smith number is a composite number, the sum of whose digits is the sum of the digits of its prime factors obtained as a result of prime factorization (excluding 1). The first few such numbers are 4, 22, 27, 58, 85, 94, and 121.

Link

Identify Smith Numbers

Complexity:

time complexity is O(sqrt(N))

space complexity is O(sqrt(N))

Execution:

There are many ways how to compute the prime composition of a number. I selected one with two optimization steps, there are many more. If there were many numbers to check I would use the Sieve of Eratosthenes to pre-compute the primes. The rest of the solution is straight forward. Do not forget that prime factors can also contain multiple digits.

Solution:
#!/usr/bin/py
def factors(n):
    f, fs = 3, []
    while n % 2 == 0:
        fs.append(2)
        n /= 2
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += 2
    if n > 1: fs.append(n)
    return fs

def getIntLetterCount(n):
    return sum([int(l) for l in list(str(n))])

def isSmithNumber(n):
    return sum([getIntLetterCount(f) for f in factors(n)]) == getIntLetterCount(n)

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

    if isSmithNumber(n):
        print 1
    else:
        print 0

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/22/15

HackerRank ‘Caesar Cipher’ Solution

Short Problem Definition:

Julius Caesar protected his confidential information from his enemies by encrypting it. Caesar rotated every alphabet in the string by a fixed number K. This made the string unreadable by the enemy. You are given a string S and the number K. Encrypt the string and print the encrypted string.

Link

Caesar Cipher

Complexity:

time complexity is O(?)

space complexity is O(?)

Execution:

This task has a few non-obvious pitfalls.

  • upper case does not rotate into lower case (as one would expect from ascii)
  • k can be bigger than the alphabet size (and must be corrected or a modulo operation on the whole sum must be performed)

Basically you need separate logic for upper case and lower case letters.

Solution:
#!/usr/bin/py
def encryptCaesar(s, k):
    output = list(s)
    k %= (ord('z') - ord('a') + 1)
    
    for idx, l in enumerate(output):
        if l.isalpha():
            if l.isupper():
                new_char = ord(l)+k
                if new_char > ord('Z'):
                    new_char = new_char - ord('Z') + ord('A') - 1
                output[idx] = chr(new_char)
            else:
                new_char = ord(l)+k
                if new_char > ord('z'):
                    new_char = new_char - ord('z') + ord('a') - 1
                output[idx] = chr(new_char)
    return ''.join(output)
    
    
if __name__ == '__main__':
    n = input()
    s = raw_input()
    k = input()
    print encryptCaesar(s, k)
    

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/19/15

HackerRank ‘Library Fine’ Solution

Short Problem Definition:

The Head Librarian at a library wants you to make a program that calculates the fine for returning the book after the return date. You are given the actual and the expected return dates

Link

Library Fine

Complexity:

time complexity is O(?)

space complexity is O(?)

Execution:

HackerRank does not support the dateutil library. This should have been computed in terms of date differences and not using if/else branches. Here I use the date library for convenience and readability.

Solution:
#!/usr/bin/py
from datetime import date

def calculateHackos(actual, expected):
    actual_date = date(actual[2], actual[1], actual[0])
    expected_date = date(expected[2], expected[1], expected[0])
    
    if actual_date.year > expected_date.year: return 10000
    if actual_date.year < expected_date.year: return 0 
    if actual_date.month > expected_date.month: return (actual_date.month - expected_date.month) * 500
    if actual_date.month < expected_date.month: return 0
    if actual_date.day > expected_date.day: return (actual_date.day - expected_date.day) * 15
    return 0    

if __name__ == '__main__':
    actual = map(int, raw_input().split())
    expected = map(int, raw_input().split())
    print calculateHackos(actual, expected)
    

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/18/15

HackerRank ‘Time Conversion’ Solution

Short Problem Definition:

You are given time in AM/PM format. Convert this into a 24 hour format.

Link

Time  Conversion

Complexity:

time complexity is O(?)

space complexity is O(?)

Execution:

Transforming date formats without use of the proper libraries is suicide. Use your language!

Solution:
#!/usr/bin/py
from datetime import datetime

def convertToEuTime(us_time):
    return datetime.strptime(us_time, '%I:%M:%S%p').strftime('%H:%M:%S')


if __name__ == '__main__':
    us_time = raw_input()
    print convertToEuTime(us_time)

use std::io;

fn main() {
    let mut line = String::new();
    io::stdin().read_line(&mut line).ok().expect("Failed to read line");
    
    let a: String = line.chars().skip(0).take(2).collect();
    let b: String  = line.chars().skip(3).take(2).collect();
    let c: String  = line.chars().skip(6).take(2).collect();
    let d: String  = line.chars().skip(8).take(2).collect();
    
    let a = a.trim().parse::<u32>().unwrap();
    let b = b.trim().parse::<u32>().unwrap();
    let c = c.trim().parse::<u32>().unwrap();
    
    let a = (a % 12) + match d.as_ref()  {
        "AM"    => 0,
        "PM"    => 12,
        _       => panic!("Unknown date type"),
    };
    
    println!("{:02}:{:02}:{:02}", a, b, c);
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/17/15

HackerRank ‘Staircase’ Solution

Short Problem Definition:

Your teacher has given you the task to draw the structure of a staircase. Being an expert programmer, you decided to make a program for the same. You are given the height of the staircase.

Link

Staircase

Complexity:

time complexity is O(N^2)

space complexity is O(1)

Execution:

Either fill each level with N-i empty spaces or adjust to the right.

Solution:
#!/usr/bin/py
def printStaircase(levels):
    for i in xrange(1,levels+1):
        print ("#" * i).rjust(levels)


if __name__ == '__main__':
    t = input()
    printStaircase(t)

use std::io;

fn get_number() -> u32 {
    let mut line = String::new();
    io::stdin().read_line(&mut line).ok().expect("Failed to read line");
    line.trim().parse::<u32>().unwrap()
}

fn main(){
    let n = get_number() as usize;
    
    for i in 0..n {
        let s = std::iter::repeat("#").take(i+1).collect::<String>();
        println!("{:>width$}", s, width=n);
    }
    
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/16/15

HackerRank ‘Plus Minus’ Solution

Short Problem Definition:

You’re given an array containing integer values. You need to print the fraction of count of positive numbers, negative numbers and zeroes to the total numbers. Print the value of the fractions correct to 3 decimal places.

Link

Plus Minus

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Count the values. Do not forget to force floats instead of integers.

Solution:
#!/usr/bin/py

def getPartitionPythonesque(values):
    c1 = len(filter(lambda x:x>0,values))
    c2 = len(filter(lambda x:x<0,values))
    c3 = len(filter(lambda x:x==0,values))
    v_len = float(len(values))
    
    return (c1/v_len, c2/v_len, c3/v_len)

def getPartition(values):
    pos, neg, zero = [0.0,0.0,0.0]
    v_len = len(values)
    
    for value in values:
        if value == 0:  zero += 1
        elif value > 0: pos += 1
        else:           neg += 1
            
    return (pos/v_len, neg/v_len, zero/v_len)    
    

if __name__ == '__main__':
    t = input()
    values = map(int, raw_input().split())
    partition = getPartition(values)
    for percentage in partition:
        print round(percentage,4)

use std::io;
use std::cmp::Ordering;


fn get_number() -> u32 {
    let mut line = String::new();
    io::stdin().read_line(&mut line).ok().expect("Failed to read line");
    line.trim().parse::<u32>().unwrap()
}

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

fn main() {
    let siz = get_number() as f32;
    
    let (mut pos, mut neg, mut zer) = (0, 0, 0);
    
    let zero = 0;
    
    for i in get_numbers() {
        match i.cmp(&zero) {
            Ordering::Less => neg+=1,
            Ordering::Greater => pos+=1,
            Ordering::Equal => zer+=1,
        }
    }
       
    println!("{:.6}\n{:.6}\n{:.6}", pos as f32 /siz, neg as f32 /siz, zer as f32 /siz);
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
06/15/15

HackerRank ‘Diagonal Difference’ Solution

Short Problem Definition:

You are given a square matrix of size N×N. Calculate the absolute difference of the sums across the two main diagonals.

Given two strings (they can be of same or different length) help her in finding out the minimum number of character deletions required to make two strings anagrams. Any characters can be deleted from any of the strings.

Link

Diagonal Difference

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Access the correct indexes and compute the difference.

Solution:
#!/usr/bin/py

def getDiagonalDifference(v):
    diff = 0
    v_len = len(v)
    for idx in xrange(v_len):
        diff += v[idx][idx]
        diff -= v[idx][v_len-idx-1]

    return abs(diff)    
        
if __name__ == '__main__':
    t = input()
    v = []
    for _ in xrange(t):
        e = map(int, raw_input().split())
        v.append(e)
        
    print getDiagonalDifference(v)

use std::io;

fn get_number() -> u32 {
    let mut line = String::new();
    io::stdin().read_line(&mut line).ok().expect("Failed to read line");
    line.trim().parse::<u32>().unwrap()
}

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

fn main() {
    let siz = get_number() as usize;
    
    let mut left = 0;
    let mut right = 0; 
    
    for i in 0..siz {
        let item = get_numbers();
        left += item[i];
        right += item[siz-i-1];
    } 
    
    println!("{}", (left-right).abs());
   
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin