07/11/19

HackerRank ‘Halloween Sale’ Solution

Short Problem Definition:

You wish to buy video games from the famous online video game store Mist.

Usually, all games are sold at the same price, p dollars. However, they are planning to have the seasonal Halloween Sale next month in which you can buy games at a cheaper price. Specifically, the first game you buy during the sale will be sold at dollars, but every subsequent game you buy will be sold at exactly d dollars less than the cost of the previous one you bought. This will continue until the cost becomes less than or equal to m dollars, after which every game you buy will cost m dollars each.

Link

Halloween Sale

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

The solution is based on the Arithmetic Progression. It makes it a bit more complex due to the floor m.

Another option is either a while loop or a recursion.

Solution:
// Complete the howManyGames function below.
int howManyGames(int p, int d, int m, int s) {
    int n=floor( (p-m)/d +1);
    if( (n*(2*p-(n-1)*d))/2 <= s)
    {
        return n + (s-(n*(2*p-(n-1)*d)/2))/m;
    }
    else
    {
        return floor(((-d-2*p)+sqrt((-2*p-d)*(-2*p-d)-(8*d*s)))/(-2*d));
    }
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
07/10/19

HackerRank ‘The Time In Words’ Solution

Short Problem Definition:

Given the time in numerals we may convert it into words.

Link

The Time In Words

Complexity:

time complexity is O(?)

space complexity is O(?)

Execution:

I might have hinted at my opinion in the past: Why do “challenges” like this even exist? It requires 0 brain power, but you will spend an hour figuring out the fine details of English and fixing bugs.

Solution:
#!/bin/python

import math
import os
import random
import re
import sys

# Complete the timeInWords function below.
def timeInWords(h, m):
    raise RuntimeError("Nope!")

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    h = int(raw_input())

    m = int(raw_input())

    result = timeInWords(h, m)

    fptr.write(result + '\n')

    fptr.close()


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

Facebooktwittergoogle_plusredditpinterestlinkedin
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(&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() {
    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
07/8/19

HackerRank ‘Strange Counter’ Solution

Short Problem Definition:

Bob has a strange counter. At the first second, it displays the number 3. Each second, the number displayed by the counter decrements by 1 until it reaches 1.

The counter counts down in cycles. In next second, the timer resets to 2x the initial number for the prior cycle and continues counting down.

Link

Strange Counter

Complexity:

time complexity is O(log(N))

space complexity is O(1)

Execution:

This is a ‘simple’ mathematical problem that requires no while loops. First, find out what cycle the value T belongs to. Secondly, determine the value at the end of the cycle. Go back T steps to figure out the exact value at T.

Be careful, this can easily int overflow in C++, if the input is large enough.

Solution:
#include <bits/stdc++.h>

using namespace std;

// Complete the strangeCounter function below.
long strangeCounter(long t) {
    return 6 * pow(2, floor(log2((t+2)/3))) - 2 - t;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    long t;
    cin >> t;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    long result = strangeCounter(t);

    fout << result << "\n";

    fout.close();

    return 0;
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin