03/6/15

# HackerRank ‘Halloween Party’ Solution

##### Short Problem Definition:

Alex is attending a Halloween party with his girlfriend Silvia. At the party, Silvia spots the corner of an infinite chocolate bar.
If the chocolate can be served as only 1 x 1 sized pieces and Alex can cut the chocolate bar exactly K times, what is the maximum number of chocolate pieces Alex can cut and give Silvia?

Halloween Party

##### Complexity:

time complexity is O(1);

space complexity is O(1)

##### Execution:

The product a*b (where a+b = k) is maximal, when a is close to b as possible. We can only use integral values, so a and b are rounded halves of k.

##### Solution:
#!/usr/bin/py
def oneOneBars(K):
half = K//2
return half * (K-half)

if __name__ == '__main__':
t = input()
for _ in xrange(t):
k = input()
print oneOneBars(k)


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

03/5/15

# HackerRank ‘Sherlock and Squares’ Solution

##### Short Problem Definition:

Watson gives two integers A & B to Sherlock and asks if he can count the number of square integers between A and B (both inclusive).

A square integer is an integer which is the square of any integer. For example, 1, 4, 9, 16 are some of the square integers as they are squares of 1, 2, 3, 4 respectively.

Sherlock and Squares

##### Complexity:

time complexity is O(sqrt(N));

space complexity is O(1)

##### Execution:

Just compute the difference between the square of the low end and the high end.

##### Solution:
#!/usr/bin/py
from math import *

if __name__ == '__main__':
t = input()
for _ in range(t):
a, b = map(int, raw_input().split())
a = ceil(sqrt(a))
b = floor(sqrt(b))
print int(b - a) + 1


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

03/4/15

# HackerRank ‘Chocolate Feast’ Solution

##### Short Problem Definition:

Little Bob loves chocolates, and goes to a store with $N in his pocket. The price of each chocolate is$C. The store offers a discount: for every M wrappers he gives to the store, he gets one chocolate for free. How many chocolates does Bob get to eat?

Chocolate Feast

##### Complexity:

time complexity is O(N);

space complexity is O(1)

##### Execution:

Evaluate the number of wraps after each step. Do this until you have enough wraps to buy new chocolates.

If someone knows how to solve this in O(1) with a mathematical formula, let me know!

##### Solution:
int eatenChocolades(int availableCash, int price, int wrapperDiscount){
int eaten = 0;
int wraps = 0;

wraps = eaten = availableCash/price;

while (wraps >= wrapperDiscount){
int newlyEaten = wraps/wrapperDiscount;
eaten += newlyEaten;
wraps %= wrapperDiscount;
wraps += newlyEaten;
}

return eaten;
}

def chocolateFeast(availableCash, price, wrapperDiscount):
eaten = availableCash // price
wraps = eaten

while wraps >= wrapperDiscount:
newlyEaten = wraps // wrapperDiscount
eaten += newlyEaten
wraps = wraps % wrapperDiscount + newlyEaten

return eaten


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

03/3/15

# HackerRank ‘Filling Jars’ Solution

##### Short Problem Definition:

Animesh has N empty candy jars, numbered from 1 to N, with infinite capacity. He performs M operations. Each operation is described by 3 integers a, b and k. Here, a and b are indices of the jars, and k is the number of candies to be added inside each jar whose index lies betweena and b (both inclusive). Can you tell the average number of candies after M operations?

Filling Jars

##### Complexity:

time complexity is O(N);

space complexity is O(1)

##### Execution:

Keep a sum variable. Compute the average at the end.

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

for _ in xrange(m):
a, b, k = map(int, raw_input().split())


 #include<iostream>
#include<vector>
#include<math.h>
#include<array>
using namespace std;
int main()
{
long n,m;
cin>>n>>m;
t = m;
while(t--){
long a,b,k;
cin>>a>>b>>k;
}
return 0;
}


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

03/3/15

# HackerRank ‘ACM ICPC Team’ Solution

##### Short Problem Definition:

You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.

ACM ICPC Team

##### Complexity:

time complexity is O(N^3);

space complexity is O(N)

##### Execution:

I generate all teams by brute force.

##### Solution:
def acmTeam(n, m, topic):
maxKnown = 0
teamsCnt = 0
for i in xrange(n-1):
for j in xrange(i+1, n):
knownForThisCombo = 0
for t in xrange(m):
if topic[i][t] == '1' or topic[j][t] == '1':
knownForThisCombo += 1
if knownForThisCombo > maxKnown:
maxKnown = knownForThisCombo;
teamsCnt = 1;
elif knownForThisCombo == maxKnown:
teamsCnt += 1;

return maxKnown, teamsCnt

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int acmIcpc(string &amp;str1, string &amp;str2, int length){
int topicsKnown = 0;
for (int i=0; i<length; i++){
if (str1.at(i) == '1' or str2.at(i) == '1'){
topicsKnown+= 1;
}
}
}
int main() {
string str[500] = {};
int N, M;
cin>>N>>M;
for (int i=0;i<N;i++) {
cin>>str[i];
}

int maxKnown = 0, teamsCnt = 0;

for (int i=0;i<N-1;i++) {
for (int j=i+1;j<N;j++) {
int knownForThisCombo = acmIcpc(str[i], str[j], M);
if (knownForThisCombo > maxKnown){
maxKnown = knownForThisCombo;
teamsCnt = 1;
} else if (knownForThisCombo == maxKnown){
teamsCnt += 1;
}
}
}

cout << maxKnown << endl;
cout << teamsCnt << endl;
return 0;
}



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

03/2/15

# HackerRank ‘Game of Thrones – I’ Solution

##### Short Problem Definition:

Dothraki are planning an attack to usurp King Robert from his kingdom. King Robert learns of this conspiracy from Raven and plans to lock the single door through which an enemy can enter his kingdom. But, to lock the door he needs a key that is an anagram of a certain palindrome string.

Game of Thrones – I

##### Complexity:

time complexity is O(N);

space complexity is O(1)

##### Execution:

A palindrome must by definition have an even number of letters. The only exception is a string of an odd length (‘aba’) that has exactly one odd letter count.

##### Solution:
#!/usr/bin/py
if __name__ == '__main__':
string = raw_input()
found = True
# Write the code to find the required palindrome and then assign the variable 'found' a value of True or False
oddCnt = 0
letterCnt = [0] * 26

for letter in string:
letterCnt[ord(letter)-ord('a')] += 1

for cnt in letterCnt:
oddCnt += cnt % 2

if oddCnt > 1:
found = False

print("NO")
else:
print("YES")


#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {

string s;
cin>>s;

int flag = 1;

int oddCnt = 0;
int letterCnt[26] = {};

for (int i=0; i<s.length(); i++){
letterCnt[int(s[i]) - int('a')]++;
}

for (int i=0; i<26; i++){
oddCnt += letterCnt[i] % 2;
}
if (oddCnt > 1){
flag = 0;
}

// Assign Flag a value of 0 or 1 depending on whether or not you find what you are looking for, in the given string
if(flag==0)
cout<<"NO";
else
cout<<"YES";
return 0;
}


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

03/1/15

# HackerRank ‘Max Min’ / ‘Angry Children’ Solution

##### Short Problem Definition:

Given a list of N integers, your task is to select K integers from the list such that its unfairness is minimized.

Max Min

##### Complexity:

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

space complexity is O(N)

##### Execution:

The unfairness is the distance between K elements in a sorted array.

##### Solution:
#!/usr/bin/py
if __name__ == '__main__':
n = input()
k = input()
candies = [input() for _ in range(0,n)]
candies.sort()
min_diff = 1000000000
## Write code here to compute the answer using (n, k, candies)

for i in xrange(n - k + 1):
min_diff = min(min_diff, candies[i+k-1] - candies[i])

print min_diff


#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;

int main() {
/* The code required to enter n,k, candies is provided*/

int N, K, unfairness = std::numeric_limits<int>::max();
cin >> N >> K;
int candies[N];
for (int i=0; i<N; i++)
cin >> candies[i];

sort(candies, candies + N);

for (int i=0; i < N - K + 1; i++){
unfairness = min(unfairness, candies[i+K-1] - candies[i]);
}

cout << unfairness << "\n";
return 0;
}


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