07/9/19

HackerRank ‘Fair Rations’ Solution

Short Problem Definition:

You are the benevolent ruler of Rankhacker Castle, and today you’re distributing bread. Your subjects are in a line, and some of them already have some loaves. Times are hard and your castle’s food stocks are dwindling, so you must distribute as few loaves as possible according to the following rules:

  1. Every time you give a loaf of bread to some person i, you must also give a loaf of bread to the person immediately in front of or behind them in the line (i.e., persons i+1 or i-1).
  2. After all the bread is distributed, each person must have an even number of loaves.
Link

Fair Rations

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

The solution can be approached from either the beginning or the end of the array.

Let’s examine the following observation: The first and last person in the array can only receive a loaf if the person next to them also got one.

If there is only one person in the array, it can never receive a loaf of bread. If there are two people in the array, both need to receive a loaf. If there are three people in the array either 0, 2 or 3 people receive a loaf. If there are any loaves awarded, the middle person has to receive at least 1.

Iterate the array from the beginning and always give the loaf to any person that does not meet criteria #2. Since the last person can never receive a loaf alone, check that for the final YES/NO decision.

Solution:
#!/bin/python

import sys


N = int(raw_input().strip())
B = map(int,raw_input().strip().split(' '))

loafs = 0

for idx in xrange(N-1):
    if B[idx] % 2 == 0:
        continue
    B[idx] += 1
    B[idx+1] += 1
    loafs += 2

    
if B[-1] % 2 == 1:
    print "NO"
else:
    print loafs
# Rust
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<u32> {
    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::<u32>().unwrap()).collect()
}

fn main() {
    let n = get_number() as usize;
    let mut b = get_numbers();
    let mut loafs = 0;
    
    for idx in 0..(n-1) {
        if b[idx] % 2 == 0 {
            continue;
        }
        
        b[idx] += 1;
        b[idx+1] += 1;
        loafs += 2;
    }
    
    if b[n-1] % 2 == 1 {
        println!("{}", "NO");
    } else {
        println!("{}", loafs);
    }
    
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
05/7/19

HackerRank ‘A Very Big Sum’ Solution

Short Problem Definition:

Calculate and print the sum of the elements in an array, keeping in mind that some of those integers may be quite large.

Link

A Very Big Sum

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Just add all of this together. No magic.

Solution:
#!/usr/bin/py
if __name__ == '__main__':
    t = input()
    n = map(int, raw_input().split())
    print sum(n)

# RUST

use std::io;

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

fn get_numbers() -> Vec<u32> {
    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::<u32>().unwrap()).collect()
}

fn main() {
    get_number();  
    let sum = get_numbers().iter().fold(0u64, |a, &amp;b| a + b as u64);
    println!("{}", sum)
}

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

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

[rust]
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) );
}
[/rust]
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin

08/4/16

HackerRank ‘Flatland Space Station’ Solution

Short Problem Definition:

For each city, determine its distance to the nearest space station and print the maximum of these distances.

Link

Flatland Space Station

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

This is a two pass algorithm. First, measure the distance to the last station on the left. And on the second pass measure the distance to the nearest station on the right. Pick the minimum of both values. Remember that the first and last position are not necessarily stations.

Solution:

[rust]
use std::io;
use std::cmp;

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 find_distance(c: Vec<u32>, n: usize) -> u32 {
let mut solution = 0;
let mut distances = vec![n as u32; n];

// first pass
let mut last_seen = 0;
let mut seen_one = false;
for i in 0..n {
if c[i] == 1 {
seen_one = true;
last_seen = 0;
} else {
last_seen += 1;
}
if seen_one {
distances[i] = last_seen;
}
}

// second pass
let mut last_seen = 0;
let mut seen_one = false;
for i in (0..n).rev() {
if c[i] == 1 {
seen_one = true;
last_seen = 0;
} else {
last_seen += 1;
}
solution = cmp::max(solution,
match seen_one {
true => cmp::min(last_seen, distances[i]),
false => distances[i],
}
);
}

solution
}

fn main() {
let line = get_numbers();
let n = line[0] as usize;
let c = get_numbers();
let mut v = vec![0; n];
for station in c {
v[station as usize] = 1;
}
println!("{}", find_distance(v, n));
}
[/rust]

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

Facebooktwittergoogle_plusredditpinterestlinkedin

08/3/16

HackerRank ‘Kangaroo’ Solution

Short Problem Definition:

There are two kangaroos on an x-axis ready to jump in the positive direction (i.e, toward positive infinity). The first kangaroo starts at location x1 and moves at a rate of v1 meters per jump. The second kangaroo starts at location x2 and moves at a rate of v2 meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they’ll ever land at the same location at the same time?

Link

Kangaroo

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

There is no need to simulate the movement. We can reason that the two kangaroos either meat at the smallest common multiply or never.

Solution:

[rust]
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 main() {
let numbers = get_numbers();
let x1 = numbers[0];
let v1 = numbers[1];
let x2 = numbers[2];
let v2 = numbers[3];

if x1 == x2 && v1 == v2 {
println!("YES");
}
else if x1 == x2 && v1 > v2 {
println!("NO");
}
else if x1 <= x2 && v1 <= v2 {
println!("NO");
}
else {
if (x2 – x1) % (v1 – v2) == 0 {
println!("YES");
}
else {
println!("NO");
}
}
}
[/rust]

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

Facebooktwittergoogle_plusredditpinterestlinkedin

08/2/16

HackerRank ‘Save the Prisoner!’ Solution

Short Problem Definition:

A jail has N prisoners, and each prisoner has a unique id number,S , ranging from 1 to N. There are M sweets that must be distributed to the prisoners. But wait—there’s a catch—the very last sweet S is poisoned! Can you find and print the ID number of the last prisoner to receive a sweet so he can be warned?

Link

Save the Prisoner!

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

This challenge is painlessly trivial.

Solution:

[rust]
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<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 solve_prisoner(n: u32, m: u32, s: u32) -> u32 {
((s – 1 + m – 1 ) % n) +1
}

fn main() {
let t = get_number();
for _ in 0..t {
let line = get_numbers();
println!("{}", solve_prisoner(line[0], line[1], line[2]));
}
}
[/rust]

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

Facebooktwittergoogle_plusredditpinterestlinkedin

08/2/16

HackerRank ‘Jumping on the Clouds’ Solution

Short Problem Definition:

Emma is playing a new mobile game involving clouds numbered from 1 to n. There are two types of clouds, ordinary clouds and thunderclouds. The game ends if Emma jumps onto a thundercloud, but if she reaches the last cloud, she wins the game!

Link

Jumping on the Clouds

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Theoretically your solution can depend on the fact that the win condition is guaranteed, but I don’t like such solutions. Here I present a semi-DP approach that keeps track of the optimal number of jumps it takes to reach each cloud.

Solution:

[rust]
use std::io;
use std::cmp;

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<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_jumping(a: Vec<u32>, n: usize) -> u32{
let mut v = vec![100; n];
v[0] = 0;

for i in 1..n {
//println!("{} {} {:?}", i, a[i], v);
if a[i] == 1 {
continue;
}

if i == 1 {
v[i] = v[i-1] + 1;
} else {
v[i] = cmp::min(v[i-1], v[i-2]) + 1;
}
}

v[n-1]
}

fn main() {
let n = get_number() as usize;
let a = get_numbers();

println!("{}", calculate_jumping(a, n) );
}
[/rust]

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)

[rust]
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) );
}
[/rust]

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

Facebooktwittergoogle_plusredditpinterestlinkedin

07/29/16

HackerRank ‘Circular Array Rotation’ Solution

Short Problem Definition:

John Watson performs an operation called a right circular rotation on an array of integers.

Link

Circular Array Rotation

Complexity:

time complexity is O(Q)

space complexity is O(1)

Execution:

Calculate the offset for every query. Watch out for index overflows and negative modulo.

Solution:

[rust]
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<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 main() {
let line = get_numbers();
let (n,k,q) = (line[0], line[1], line[2]);
let a = get_numbers();
for _ in 0..q {
let m = get_number();
let idx = ((m-(k%n)+n)%n) as usize;
println!("{}", a[idx]);
}
}
[/rust]

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

Facebooktwittergoogle_plusredditpinterestlinkedin

07/29/16

HackerRank ‘Compare Triplets’ Solution

Short Problem Definition:

Alice and Bob each created one problem for HackerRank. A reviewer rates the two challenges, awarding points on a scale from 1 to 100  for three categories: problem clarity, originality, and difficulty.

Link

Compare Triplets

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

This is a warmup. Follow specification.

Solution:

[rust]
use std::io;
use std::cmp::Ordering;

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 main() {
let a = get_numbers();
let b = get_numbers();

let mut alice = 0;
let mut bob = 0;

for idx in 0..3 {
match a[idx].cmp(&b[idx]) {
Ordering::Less => bob += 1,
Ordering::Greater => alice += 1,
Ordering::Equal => {},
}
}

println!("{} {}", alice, bob);
}
[/rust]

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

Facebooktwittergoogle_plusredditpinterestlinkedin