02/28/15

HackerRank ‘The Love-Letter Mystery’ Solution

Short Problem Definition:

James found a love letter his friend Harry has written for his girlfriend. James is a prankster, so he decides to meddle with the letter. He changes all the words in the letter into palindromes.

Link

The Love-Letter Mystery

Complexity:

time complexity is O(N*T);

space complexity is O(1)

Execution:

You process the string from the beginning towards mid and always decrement the higher side.

Solution:
#!/usr/bin/py
if __name__ == '__main__':
    t = input()
    for _ in range(t):
        s = map(int, raw_input().split())
        reductions = 0
    	for i in range(0,len(s)//2):
            reductions += abs(ord(s[i]) - ord(s[-1-i]))
    	print reductions 

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


int letterMystery(string &str){
    int changes = 0;
    
    int mid = str.length()/2;
    int len = str.length();
    
    for (int i=0; i < mid; i++){
        int diff = abs(int(str.at(i)) - int(str.at(len-i-1)));
        changes += diff;
    }
    
    return changes;
}
int main() {
    string str;
    int t;
    cin>>t;
    for (int i=0;i<t;i++) {
        cin>>str;
        cout << letterMystery(str) << endl;
  }
  return 0;
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/27/15

HackerRank ‘Alternating Characters’ Solution

Short Problem Definition:

Shashank likes strings in which consecutive characters are different. For example, he likes ABABA, while he doesn’t like ABAA. Given a string containing characters A and B only, he wants to change it into a string he likes. To do this, he is allowed to delete the characters in the string.

Your task is to find the minimum number of required deletions.

Link

AlternatingChars

Complexity:

time complexity is O(N*T);

space complexity is O(1)

Execution:

If two following characters are the same, you have to delete one of them. A sequence of x equal characters will require (x-1) deletions.

Solution:
#!/usr/bin/py
if __name__ == '__main__':
    t = input()
    for _ in range(t):
    	s = raw_input()
    	delete_cnt = 0
    	for i in range(1,len(s)):
            if s[i] == s[i-1]:
            	delete_cnt +=1
        print delete_cnt

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/26/15

HackerRank ‘Maximizing XOR’ Solution

Short Problem Definition:

Given two integers, L and R, find the maximal values of A xor B, where A and B satisfies the following condition:

  • LABR
Link

Maximizing XOR

Complexity:

time complexity is O(N^2);

space complexity is O(1)

Execution:

Based on the constraints, you can search by using brute force.

Solution:
#!/usr/bin/py
def  maxXor( l,  r):
  max_xor = 0
  for low in xrange(l ,r+1):
    for high in xrange(low, r+1):
        max_xor = max(max_xor, low ^ high)
  return max_xor  

if __name__ == '__main__':
    l = int(raw_input());
    r = int(raw_input());

    res = maxXor(l, r);
    print(res)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/25/15

HackerRank ‘Utopian Tree’ Solution

Short Problem Definition:

The Utopian Tree goes through 2 cycles of growth every year. The first growth cycle occurs during the spring, when it doubles in height. The second growth cycle occurs during the summer, when its height increases by 1 meter.  Now, a new Utopian Tree sapling is planted at the onset of spring. Its height is 1 meter. Can you find the height of the tree after N growth cycles?

Link

Utopian Tree

Complexity:

time complexity is O(N + max(N));

space complexity is O(max(N))

Execution:

Just follow the problem description. I compute the height for all test cases at the same time. Printing them at the end.

Solution:
#!/usr/bin/py
def printUtopianTree(cycles):
    heights = [1]

    for cycle_nr in xrange(1,max(cycles)+1):
    	if cycle_nr % 2 == 1:
            heights.append(heights[-1]*2)
    	else:
            heights.append(heights[-1]+1)

    for cycle in cycles:
    	print heights[cycle]

if __name__ == '__main__':
    n = int(raw_input())

    cycles = []

    for i in range(0,n):
    	cycles.append(int(raw_input()))

    printUtopianTree(cycles)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/24/15

HackerRank ‘Flipping Bits’ Solution

Short Problem Definition:

You will be given a list of 32 bits unsigned integers. You are required to output the list of the unsigned integers you get by flipping bits in its binary representation (i.e. unset bits must be set, and set bits must be unset).

Link

Flipping Bits

Complexity:

time complexity is O(N);

space complexity is O(1)

Execution:

It can be done by either using the negation ~ operator, or by XORing the value with 2^32 -1 (all 1).

Solution:
#!/usr/bin/py
def flipBits(a):
   return a ^ 4294967295 # 2^32 - 1

if __name__ == '__main__':
    n = int(raw_input())
    for i in range(0,n):
    	a = int(raw_input())
    	res = flipBits(a)
    	print res

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/23/15

HackerRank ‘Lonely Integer’ Solution

Short Problem Definition:

There are N integers in an array A. All but one integer occur in pairs. Your task is to find out the number that occurs only once.

Link

Lonely Integer

Complexity:

time complexity is O(N);

space complexity is O(1)

Execution:

XORing two equal numbers cancels them out. XOR all numbers together.

Solution:
#!/usr/bin/py
def lonelyinteger(a):
    answer = 0
    for candidate in a:
        answer ^= candidate
    return answer
if __name__ == '__main__':
    a = input()
    b = map(int, raw_input().strip().split(" "))
    print lonelyinteger(b)

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

Facebooktwittergoogle_plusredditpinterestlinkedin