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.

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.

07/10/19

# HackerRank ‘The Time In Words’ Solution

##### Short Problem Definition:

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

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.

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.

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();
line.trim().parse::<u32>().unwrap()
}

fn get_numbers() -> Vec<u32> {
let mut line = String::new();
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.

06/14/19

##### Short Problem Definition:

Happy Ladybugs is a board game having the following properties:

• A ladybug is happy only when it’s left or right adjacent cell (i.e., ) b[i+/-1] is occupied by another ladybug having the same color.

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

This challenge definition does not require a full sort. It only wants to know whether the array is sortable. Therefore we will assume that if there is at least one free slot, the array is sortable by color.

Further we will assume that each ladybug wants to have at least one neighbor with the same color. If there are two of the same color, the ladybug is happy.

If there is no empty space, the input array needs to be sorted correctly.

##### Solution:
```#!/bin/python

import math
import os
import random
import re
import sys
from collections import Counter

# Complete the happyLadybugs function below.
counter = Counter(b)
for key, value in counter.items():
if key != "_" and value == 1:
return "NO"

if "_" in b:
return "YES"

for idx in xrange(1, len(b)):
if b[idx] == b[idx-1] or b[idx] == b[idx+1]:
continue
else:
return "NO"

return "YES"

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

g = int(raw_input())

for g_itr in xrange(g):
n = int(raw_input())

b = raw_input()

fptr.write(result + '\n')

fptr.close()
```

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

06/13/19

# HackerRank ‘Absolute Permutation’ Solution

##### Short Problem Definition:

We define P to be a permutation of the first n natural numbers in the range
[1,n]. Let pos[i] denote the value at position i in permutation P using 1-based indexing.

P is considered to be an absolute permutation if |pos[i]-i| = K holds true for every i.

Absolute Permutation

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

The time complexity of this solution is a question as is always true with hash maps. It is either O(N), O(NlogN) or O(N^2) depending on your particular implementation and hash algorithm.

After I solved this, I looked at the editorial and was amazed by the complex algorithm that they proposed. This is much simpler. Yet I agree that the editorial is more time/space effective.

Iterate over the list of all values [1,N]. Use the lowest available value from the [1,N] pool. Either i-K or i+k, if i-K is not available.

##### Solution:
```#!/bin/python

import math
import os
import random
import re
import sys

# Complete the absolutePermutation function below.
def absolutePermutation(n, k):
solution = []
s = set(range(1,n+1))

for pos in xrange(1, n+1):
if pos-k in s:
solution.append(pos-k)
s.remove(pos-k)
elif pos+k in s:
solution.append(pos+k)
s.remove(pos+k)
else:
return [-1]

return solution

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

t = int(raw_input())

for t_itr in xrange(t):
nk = raw_input().split()

n = int(nk[0])

k = int(nk[1])

result = absolutePermutation(n, k)

fptr.write(' '.join(map(str, result)))
fptr.write('\n')

fptr.close()
```

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

06/12/19

# HackerRank ‘Repeated String’ Solution

##### Short Problem Definition:

Lilah has a string, s, of lowercase English letters that she repeated infinitely many times. Given an integer, n, find and print the number of letters `a` in the first n letters of Lilah’s infinite string.

For example, if the string s = ‘abcac’ and n = 10, the substring we consider is abcacabcac, the first 10 characters of her infinite string. There are 4 occurrences of `a` in the substring.

Repeated String

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

As with most simple problems, there are many ways to write the code that can achieve the correct result. I picked the one that seems the simplest and most Pythonesque.

##### Solution:
```#!/bin/python

import math
import os
import random
import re
import sys

# Complete the repeatedString function below.
def repeatedString(s, n):
n_per_string = s.count('a')
n_per_substring = s[0:n%len(s)].count('a')
return n_per_string * (n/len(s)) + n_per_substring

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
s = raw_input()
n = int(raw_input())
result = repeatedString(s, n)
fptr.write(str(result) + '\n')
fptr.close()
```

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

06/11/19

# HackerRank ‘Climbing The Leatherboard’ Solution

##### Short Problem Definition:

Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:

• The player with the highest score is ranked number 1 on the leaderboard.
• Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number

##### Complexity:

time complexity is O(N*log(N))

space complexity is O(1)

##### Execution:

I am not a fan of the Dense Rank. Standard Competition ranking makes much more sense.

1) In the Dense Rank, duplicates have no impact on the ranking, so they can be safely removed.

2) The array should be sorted. Since the value range is fairly small (10^5), counting sort would improve the theoretical O-notation to O(N).

3) Take advantage of built-in Python functionality. Bisect right finds an insertion point after potential duplicates, giving us the correct Dense Rank.

##### Solution:
```#!/bin/python

import math
import os
import random
import re
import sys
import bisect

# Complete the climbingLeaderboard function below.
res = []
s = sorted(list(set(scores)))
l = len(s)
for v in alice:
res.append(l - bisect.bisect_right(s, v) +1)

return res

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
scores_count = int(raw_input())
scores = map(int, raw_input().rstrip().split())
alice_count = int(raw_input())
alice = map(int, raw_input().rstrip().split())
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
fptr.close()

```

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

06/6/19

# HackerRank ‘Almost Sorted’ Solution

##### Short Problem Definition:

Given an array of integers, determine whether the array can be sorted in ascending order using only one of the following operations one time.

1. Swap two elements.
2. Reverse one sub-segment.

Determine whether one, both or neither of the operations will complete the task. If both work, choose swap. For instance, given an array [2, 3, 5, 4] either swap the 4 and 5; or reverse them to sort the array. Choose swap.

Almost Sorted

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

I wrote this code 4 years ago and I already have no clue what it does. It is linear time and it works even today.

Today, I would have broken this logic down into smaller functions with clear purpose.

##### Solution:
```#!/usr/bin/py
def getReverseAction(arr):
is_sorted = True

low_idx = 0
high_idx = len(arr)-1

while (low_idx < high_idx and arr[low_idx] < arr[low_idx+1]):
low_idx += 1

if low_idx == high_idx:
print "yes"
return

while (high_idx > 0 and arr[high_idx] > arr[high_idx-1]):
high_idx -= 1

#print "low", low_idx, arr[low_idx]
#print "high", high_idx, arr[high_idx]

if low_idx == 0 or arr[high_idx] > arr[low_idx -1]:
#print "high index swapable"
if arr[high_idx] < arr[low_idx +1] or low_idx+1 == high_idx:
#print "high index swapable"
if high_idx == len(arr)-1 or arr[low_idx] < arr[high_idx+1]:
#print "low index swapable"
if arr[low_idx] > arr[high_idx -1] or low_idx == high_idx-1:
#print "low index swapable"
low_idx_runner = low_idx+1
while (low_idx_runner < high_idx and arr[low_idx_runner] < arr[low_idx_runner+1]):
low_idx_runner += 1
if low_idx_runner == high_idx-1 or low_idx == high_idx-1:
print "yes"
print "swap", low_idx+1, high_idx+1
return

low_idx_runner = low_idx+1
while (low_idx_runner < high_idx and arr[low_idx_runner] > arr[low_idx_runner+1]):
low_idx_runner += 1

if low_idx_runner == high_idx:
if low_idx == 0 or arr[high_idx] > arr[low_idx -1]:
if high_idx == len(arr)-1 or arr[low_idx] < arr[high_idx+1]:
print "yes"
print "reverse", low_idx+1, high_idx+1
return

print "no"

if __name__ == '__main__':
n = input()
arr = map(int, raw_input().split())
getReverseAction(arr)
```

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

06/5/19

# HackerRank ‘Picking Numbers’ Solution

##### Short Problem Definition:

Given an array of integers, find and print the maximum number of integers you can select from the array such that the absolute difference between any two of the chosen integers is less than or equal to 1. For example, if your array is a = [1, 1, 2, 2, 4, 4, 5, 5, 5], you can create two subarrays meeting the criterion:  [1 ,1 ,2 ,2] and [4, 4, 5, 5, 5]. The maximum length subarray has 5 elements.

Picking Numbers

##### Complexity:

time complexity is O(N*log(N))

space complexity is O(N)

##### Execution:

There is a simple solution. Sort the array and iterate over it, counting pairs. But I don’t like it.

The solution proposed here never sorts the array. Depending on the O-complexity of a map implementation, it could be O(N) or O(NlogN).

The idea is to check the +/-1 neighbors of each value as you iterate over them.

##### Solution:
```from collections import defaultdict

def pickingNumbers(a):
d = defaultdict(int)
r_val = 0
for val in a:
d[val] += 1
r_val = max(r_val, d[val]+d[val+1], d[val]+d[val-1])

return r_val
```

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

06/4/19

# HackerRank ‘Cats And A Mouse’ Solution

##### Short Problem Definition:

Two cats and a mouse are at various positions on a line. You will be given their starting positions. Your task is to determine which cat will reach the mouse first, assuming the mouse doesn’t move and the cats travel at equal speed. If the cats arrive at the same time, the mouse will be allowed to move and it will escape while they fight.

Cats And A Mouse

##### Complexity:

time complexity is O(1)

space complexity is O(1)

##### Execution:

This feels like a very simplistic version of Codility Fish. Just implement the specification.

##### Solution:
```#!/bin/python

import sys

q = int(raw_input().strip())
for a0 in xrange(q):
x,y,z = raw_input().strip().split(' ')
x,y,z = [int(x),int(y),int(z)]
catA = abs(x-z)
catB = abs(y-z)
if (catA < catB):
print "Cat A"
elif (catB < catA):
print "Cat B"
else:
print "Mouse C"
```

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