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?

Link

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.

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

Link

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.

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

Link

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.

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

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;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t,n,c,m;
    cin>>t;
    while(t--){
        cin>>n>>c>>m;
        int answer=0;
        answer = eatenChocolades(n,c,m);
        cout<<answer<<endl;
    }
    return 0;
}

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

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

Link

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

    answer = 0

    for _ in xrange(m):
        a, b, k = map(int, raw_input().split())
        answer += (abs(a-b)+1)*k
    print answer//n

 #include<iostream>
 #include<vector>
 #include<math.h>
 #include<array>
 using namespace std;
 int main()
 {
    long n,m;
    long answer=0,t;
    cin>>n>>m;
    t = m;
    while(t--){
        long a,b,k;
        cin>>a>>b>>k;
        answer = answer + (abs(a-b)+1)*k;
    }
    answer = floor(answer/n);
    cout<<answer<<endl;
    return 0;
 }

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

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

Link

ACM ICPC Team

Complexity:

time complexity is O(N^3);

space complexity is O(N)

Execution:

I generate all teams by brute force.

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



int acmIcpc(string &str1, string &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;
        }
    }
    return topicsKnown;
}
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.

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

Link

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

    if not found:
        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.

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

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin