Archive

Posts Tagged ‘hackerrank’

Handshake

February 22, 2015 Leave a comment

Problem Statement

At the annual meeting of Board of Directors of Acme Inc, every one starts shaking hands with everyone else in the room. Given the fact that any two persons shake hand exactly once, Can you tell the total count of handshakes?

Input Format
The first line contains the number of test cases T, T lines follow.
Each line then contains an integer N, the total number of Board of Directors of Acme.

Output Format

Print the number of handshakes for each test-case in a new line.

Constraints

1 <= T <= 1000
0 < N < 106

This problem is about combinations. The formula is

For factorial calculation I’m using recursive with memoization to optimization process. Read more…

The Love-Letter Mystery

February 22, 2015 Leave a comment

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.

To do this, he follows 2 rules:

  1. He can reduce the value of a letter, e.g. he can change ‘d’ to ‘c’, but he cannot change ‘c’ to ‘d’.
  2. In order to form a palindrome, if he has to repeatedly reduce the value of a letter, he can do it until the letter becomes ‘a’. Once a letter has been changed to ‘a’, it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations required to convert a given string into a palindrome.

Read more…

Categories: Umum Tags: , ,

Pangrams

Problem:

Roy wanted to increase his typing speed for programming contests. So, his friend advised him to type the sentence “The quick brown fox jumps over the lazy dog” repeatedly because it is a pangram. ( pangrams are sentences constructed by using every letter of the alphabet at least once. ) After typing the sentence several times, Roy became bored with it. So he started to look for other pangrams. Given a sentence s, tell Roy if it is a pangram or not.

From Wikipedia, A pangram or holoalphabetic sentence for a given alphabet is a sentence using every letter of the alphabet at least once. Check both uppercase and lowercase(+32).

Using Java String function indexOf() to check if the character appear in the sentence.

Java code:


import java.util.Scanner;

public class Pangram {

public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 String input = in.nextLine();
 if(testPangram(input)) {
 System.out.println("pangram");
 } else {
 System.out.println("not pangram");
 }
 in.close();
 }

 static boolean testPangram(String input) {
 for(char a = 'A' ; a <= 'Z' ; a++) {
 if(input.indexOf(a) < 0 && input.indexOf((char) a+32) < 0) {
 return false;
 }
 }
 return true;
 }
}

Result for input “We promptly judged antique ivory buckles for the prize “:

pangrams2

Result for input “ABCDEFGHIJKLMNOPQSTUVWXYZ”:

pangrams1

Source:

  1. https://www.hackerrank.com/challenges/pangrams
  2. http://en.wikipedia.org/wiki/Pangram
Categories: JAVA Tags: , ,

Maximizing XOR

Problem:

Given two integers: L and R, find the maximal values of A xor B given, L ≤ A ≤ B ≤ R

Java code:


import java.util.Scanner;

public class MaximizingXOR {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int l = in.nextInt();
int r = in.nextInt();
int max = 0;
for(int b=l; b<= r; b++) {
for(int a=b ; a <=r; a++) {
max = max > (a ^ b) ? max : (a ^ b);
}
}
System.out.println(max);
in.close();
}
}

Result for input 1 and 10:

maximizingXOR1

Result for input 10 and 15:

maximizingXOR2

Source:

https://www.hackerrank.com/challenges/maximizing-xor

Categories: Umum Tags: , ,

Is Fibo

Problem:

You are given an integer, N. Write a program to determine if N is an element of the Fibonacci Sequence.

Solution I choose is using this formula:

fibocheck or fibocheck2

 

Then check if the result is a perfect square.

Java code:


public class IsFibo {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
long[] arrays = new long[a];
for(int i=0; i < a; i++) {
arrays[i] = in.nextLong();
}
for(int i=0; i < arrays.length; i++) {
System.out.println(isFibo(arrays[i]));
}
}

private static String isFibo(long suspectFibo) {
if((Math.sqrt(5 * Math.pow(suspectFibo, 2) + 4)%1 == 0)
|| (Math.sqrt(5 * Math.pow(suspectFibo, 2) - 4)%1 == 0)) {
return "IsFibo";
}
return "IsNotFibo";
}
}

Result for 3 input (5, 7, 8):

isFibo

Source:

  1. https://www.hackerrank.com/challenges/is-fibo
  2. http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers
  3. http://en.wikipedia.org/wiki/Square_number

Lonely Integer

Problem:

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.

The solution I choose is using XOR operator. XOR operator have following characteristic:

  1. x (+) 0 = x
    XORing with 0 gives you back the same number.
    Thus, 0 is the identity for XOR.
  2. x (+) 1 = \x
    XORing with 1 gives you back the negation of the bit. Again, this comes from the truth table. For bitwise XOR, the property is slightly different: x ^ ~0 = ~x .
    That is, if you XOR with all 1’s, the result will be the bitwise negation of x.
  3. x (+) x = 0
    XORing x with itself gives you 0.
    That’s because x is either 0 or 1, and 0 (+) 0 = 0 and 1 (+) 1 = 0.
  4. XOR is associative.
    That is: (x (+) y) (+) z = x (+) (y (+) z).
    You can verify this by using truth tables.
  5. XOR is commutative.
    That is: x (+) y = y (+) x.
    You can verify this by using truth tables.

note: (+) is symbol for XOR operator.

Java code: Read more…