thefourtheye's weblog

opinions are my own; try code/suggestions at your own risk

Next Palindrome After a 1000000 Digit Number - SPOJ - PALIN

| Comments

I always have afraid of the problems which require string processing, to be solved. This is one such problem. The problem description as stated in SPOJ (http://www.spoj.pl/problems/PALIN/) and my solution to this problem is http://ideone.com/osqLhp (I am sure, I can improve this code)

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.


Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output

For each K, output the smallest palindrome larger than K.

Example

Input:
2
808
2133

Output:
818
2222


We know that, there is no integral data type which is as sophisticated as to accommodate a 1000000 digits number (a million digits in a number). So only option is to use string. And we also know what palindrome is. A number or a string of characters, is the same when expressed from left to right and right to left. For example, AMMA, MADAM, MALAYALAM, 11, 505, 797979797, ...

Lets assume the input number as N. If we read through the problem, we are asked to find the next (greater than the number provided) palindrome which exists after the number N. As we see in the examples, 818 is the next big palindrome after 808 and 2222 is the next big palindrome after 2133. If the numbers are small, we can try brute-force approach.

Brute force approach:


  1. Read the number N
  2. Increment by 1
  3. Check whether it is a palindrome or not
  4. If Yes, Print the number and exit
  5. If No, goto step 2

This approach is quite simple and easy to implement. But, this may not work always when we have time constraints. If the number N becomes as big as a 1000000 digit number, program with this approach would produce output after a very long time. We all want our programs to produce outputs so quickly, don't we? Let us look at the approach which I followed to solve this problem.

My approach:

  1. Read the number as a string and store it in STR and the number of digits as N
  2. Split STR into two halves STR1 and STR3, if the number of digits in STR is odd, the middle digit will be in STR2 otherwise it is empty
  3. If the Reverse of STR1 is greater than STR3, Print STR1 + STR2 + Reverse (STR1) and exit
  4. make all digits of STR3 as '0'
  5. If N is even, 
    1. increment STR1
    2. Goto step 1 with input (Incremented STR1 + STR3)
  6. If N is odd, 
    1. increment STR2
      1. If Incremented STR2 is 10, 
        1. set STR2 as "0"
        2. increment STR1
        3. Goto step 1 with input (Incremented STR1 + STR2 + STR3)
      2. If Incremented STR2 is lesser than 10
        1. Goto step 1 with input (STR1 + STR2 + STR3)
The observation which I made after analyzing few examples is, if the second half of the number is smaller than the reverse of the first half of the number, just replacing the second half with the reverse of the first half produces the required output. If it is not smaller than the reverse of the first half, increment the first half and then replace the second half with the incremented first half. This is the basic idea but the above algorithm includes all the corner cases.

My solution:

Infix Expression to Postfix (RPN) Expression Conversion - SPOJ - ONP

| Comments

This was one of our lab exercises in my Engineering first year. That was Data Structures lab. Guess what, this program was agreed as the toughest program of all the programs, by the whole class (our class strength was 63), which we were supposed to finish in that semester and the teacher had the whole program written on the blackboard and later we typed, compiled and executed on the computers. I remember the days, in which I used to memorize the program which solved the same problem for the lab exams. Nostalgic!!! Now, this took me lesser than 15 minutes to get "accepted" in SPOJ :)

Here is the problem statement, as stated in SPOJ (http://www.spoj.pl/problems/ONP/). My solution to the same http://ideone.com/wCfryC

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]
Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

Store and Read Static Files in Android

| Comments

Recently I was writing an Android application, in which I had to read data from a static text file. I did not know where to keep the file and how to refer that file in the program (in windows/*nix OS we used to provide path to the file in file system). After surfing the internet enough, found a solution to this problem.

Note: This post helps you to read from a static application specific internal files.

1) The IDE which I used to develop Android applications is Eclipse and I assume that you already have an Android project opened and the static file to be read.

2) The name of the static file which I am going to use in this example is dictionary.txt

3) In the directory structure of an Android project, there will be a directory called "res". Create a directory called "raw" inside the "res" directory and import the file to be read in that directory. All the files added to the raw folder will be read-only. (And I don't think we can refer them as files anymore. So that data can be read as shown in step 6). The directory structure might look like this

4) After adding the file, just Build the Project and make sure that build is successful.

5) Now, in the "gen" directory, inside your package, Open the R.java file. You might get to see something similar to this

    public static final class raw {
        public static final int dictionary=0x......;
    }


6) Now, this static file will be included in the ".apk" file. As to read from the file, the following piece of code would do that job. You may have to add the appropriate try-catch blocks.

BufferedReader filereader = new BufferedReader(
   new InputStreamReader (ctx.getResources().openRawResource 
   (R.raw.dictionary)));

String lineread = "";
while ((lineread = filereader.readLine()) != null)
{
   System.err.println ("Read " + lineread);
}
filereader.close();

7) In order to view the files in development environment or emulator itself, there is a perspective called DDMS in Eclipse, just switch to that and have your Android Virtual Device started.


8) The application specific files can be found in data/data/<your package name>/files

Making Lync 2010 to Work in Android

| Comments

Lately I downloaded Lync 2010 from Android Market. But I was not able to make it to connect to my corporate network. I was sure that there is some setting which has to be done properly but not sure what that is. After surfing internet for a while, landed on this page. http://support.microsoft.com/kb/2636313

This is how I made it to work.

1) Downloaded and installed Lync 2010 from Google Play Store in my Android Gingerbread.
2) Opened Lync 2010
3) Typed my username and password properly. The username should be typed completely, for example, someone@example.com
4) Now press the menu button to be able to select the "Options" option.
5) It will open up a page like this
6) Most of the cases, Lync detects the server details automatically. So lets not worry about the server settings now. Press the downward arrow which corresponds to the User name box, which will pull up a simple page like this.
7) This is the part which was driving me crazy and took three days to figure out. You have to provide the username along with the complete domain name. The most important thing is, you need to use a backward slash (\) to separate the domain name and username. My gingerbread did not show (\) character on this page. So I had to copy it from the browser where I was able to type that character. For example, domain\someone

I helped many of my friends using Lync this way, on Android and it works on iTouch also.

Prime Numbers and Basic Primality Tests - SPOJ - Prime1

| Comments

Prime numbers are the numbers which get divided properly (leaving remainder as 0) only by 1 and the same number.

The same way, numbers which get divided by 1, the same number and other numbers are called composite numbers.

Current state of the art security infrastructures rely on security schemes such as RSA and DSA. They both, in turn, rely heavily on Prime numbers. So prime numbers are so important in the digital world's security. Lets see few of the algorithms to determine whether the given number is a Prime number or not.

Basic Tests for Primality

Lets say, we want to find whether the numbers 101 and 100 are prime numbers are not.

Approach 1


This is the very basic approach and very easy to implement.

  • Read the number n
  • Loop with i from 2 till n/2 (if it doesn't divide properly, round off is needed)
  • if i divides n with out leaving any remainder (remainder is 0) then return false
  • End Loop
  • return true

The idea here is to check whether each and every number from 2 till half of that number [2, n/2] divides the number or not. If any of them divides the number without leaving any remainder, we can declare that the number is NOT a prime number. If no number in that range divides properly, the number is called a Prime number. We check only till n/2, because 2 * n/2 would be n, there would be no number greater than n/2 would divide n properly. In the worst case, It needs n/2 iterations to confirm whether the number is prime or not. In our case, for 101, it is 50.

Approach 2


The simplicity of this algorithm would tempt us to use this always. Lets see, if we can improve this. If we observe closely, if the number n is odd, we don't even have to try any of the even numbers. This would reduce the number of iterations needed by half.

  • Read the number n
  • if n is even return false
  • Loop with i from 3 till n/2, increment i by 2
  • if i divides n with out leaving any remainder (remainder is 0) then return false
  • End Loop
  • return true

As we can clearly see, if n is even it can not be a prime number, since if a number is even it is divisible by 2. So we check only the odd numbers starting from 3 till n/2 and we are skipping all the even number  by incrementing the loop's index variable by 2 every time. So the loop would be run for the values 3,5,7,9, 11... Now if we look at the performance of this approach, we just need n/4 iterations to find whether the number is a prime number or not. In our case, for 101, it is 25.

Approach 3


Lets see, if we can reduce it further from n/4. Lets write down the combinations which would yield 100. {2, 50}, {4, 25}, {5, 20} and {10, 10}. Lets try 256. {2, 128}, {4, 64}, {8, 32}, {16, 16}. In both the cases, atleast one of the numbers is always lesser than equal to the square root of the actual number. (I, honestly, don't know how to prove this, but this observation works always). So, instead of looping till n/2 we are going to limit the loop at square root of the number. Combining the observation we made in approach 2, presenting approach 3.

  • Read the number n
  • if n is even return false
  • Loop with i from 3 till sqrt (n), increment i by 2
  • if i divides n with out leaving any remainder (remainder is 0) then return false
  • End Loop
  • return true

In our case, we see a tremendous hike in performance, for the value 101, in the worst case we might have to do only 4 checks.

Approach 4


We have already had good performance with approach 3. Lets see if we still can improve it. Lets list the four values with which we may need to divide 101 to determine whether it is prime or not. The values are {2, 3, 5, 7, 9}. We have 2 as well here, since we check whether the input is even or not and 11 is not included because sqrt (101) would be rounded off to 10. The odd item in the list is 9, since we are checking against all the odd number between 2 and sqrt(n). We all know that, any given composite (non-prime) number can be expressed in terms of its prime factors. So we can try and divide the number only with the prime numbers within the range [2, sqrt(n)]. Note: This approach works only when we have a predetermined list of prime numbers. If we don't have that its better to stick to approach 3 or have a look at approach 5 below.

Approach 5


Lets observe the list the prime numbers a bit.

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101...}

Lets rewrite them like this

{2, 3, 6*1-1, 6*1+1, 6*2-1  6*2+1  6*3-1  6*3+1  6*4-1  6*5-1  6*5+1  6*6+1  6*7-1  6*7+1,  6*8-1  6*9-1, 6*10-1, 6*10+1, 6*11+1, 6*12-1, 6*12+1, 6*13-1, 6*14-1, 6*15-1, 6*16+1, 6*17-1...}

Basically, the prime numbers are of the form (6*x)±1 (though few of them may not be prime numbers). This reduces the possible values to be looked at, to a greater extent. 

  • Read the number n
  • if n is even return false
  • if 3 divides n properly return false
  • Loop with i from 1 till (6 * i) -1 > sqrt (n), increment i by 1 every time
  • if (6 * i) -1 or (6 * i) + 1 divides n with out leaving any remainder (remainder is 0) then return false
  • End Loop
  • return true

This method would be the fastest of all the methods discussed, I believe.

Based on the ideas discussed above, I managed to solved the SPOJ's PRIME1 problem. The problem description can be found here http://www.spoj.pl/problems/PRIME1/

Spoiler alert: This http://ideone.com/4n9kB has my solution to the above mentioned PRIME1 problem.