Archive

Posts Tagged ‘algorithm’

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…

Advertisements
Categories: Umum 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…