Palindrome and Prime

the initial drafted title was “Old concepts with new understanding”. You’ll know why.

Palindrome :

A string which is same when read from left to right or right to left.

Algorithm as a naive programmer : Run a loop till middle of string, and compare the first letter with last letter, then 2nd with second last and so on. If you do not get any mismatch, it is a palindrome, else it is not.

Better algorithm : It is neither better in terms of space nor time complexity, I still found it better because it was neat !. Insert the string into a stack and a queue. Then start popping out the letters and compare them. Since stack is LIFO and queue is FIFO, first and last letters will be compared.

 

Prime number :

A number greater than 1 which is divisible only by 1 and itself.

Algorithm as a naive programmer : Iterate starting 2 to that number, if you find any number which completely divides our number, it is not prime , else it is prime. The complexity is O(n)

Better algorithm : iterate staring 2 to n only,  but check on square of the number. This way only √n will be the order.

So instead of (for int i=2;i<=n; i++) { } do (for int i=2;i*i<=n;i++) { }

I found a good answer for this thing on stack overflow :

If a number n is not a prime, it can be factored into two factors a and b:

n = a*b

If both a and b were greater than the square root of n, a*b would be greater than n. So at least one of those factors must be less than or equal to the square root of n, and to check if n is prime, we only need to test for factors less than or equal to the square root.

 

 

Keep reading !

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s