Monthly Archive for December, 2009

Page 2 of 2

Project Euler : Largest Product Of Five Consequtive Digits

Published on December 12, 2009 in Problems. 0 Comments

The problem was that given a 1000 digit number, we had to find the largest product of 5 consecutive digits.

This was a no brainer actually. It was simple to the point question. I realized that if a 0 appeared, then the product would be minimum. So I split the given number at 0′s and stored them in an array, Each number of the array was the largest block without any 0. Now if the length of a block is less than 5, we can just avoid that block.

The whole thing now boils down to finding the largest product in blocks of length greater than 5. A simple loop completed the solution. Here is the solution as coded by me:

public class Problem_8 {
    public int getMaxProductOfFiveConsequtiveDigits(String[] nums) {
        int maxProduct = 0;

        Stopwatch stopwatch = new Stopwatch();
        stopwatch.start();

        for (String num : nums) {
            int length = num.length();
            if (length < 5)
                continue;
            int[] n = new int[5];
            for (int i = 0; i < 5; i++)
                n[i] = num.charAt(i) - '0';
            int cycle = 5;
            while (cycle < length) {
                int prod = n[0] * n[1] * n[2] * n[3] * n[4];
                if (prod > maxProduct)
                    maxProduct = prod;
                n[cycle % 5] = num.charAt(cycle) - '0';
                cycle++;
            }
        }
        stopwatch.stop();
        System.out.println("The reading for operation is: " + stopwatch);

        return maxProduct;
    }

    public static void main(String[] args) {
        String[] nums = ("73167176531330624919225119674426574742355349194934"
                + "96983520312774506326239578318016984801869478851843"
                + "85861560789112949495459501737958331952853208805511"
                + "12540698747158523863050715693290963295227443043557"
                + "66896648950445244523161731856403098711121722383113"
                + "62229893423380308135336276614282806444486645238749"
                + "30358907296290491560440772390713810515859307960866"
                + "70172427121883998797908792274921901699720888093776"
                + "65727333001053367881220235421809751254540594752243"
                + "52584907711670556013604839586446706324415722155397"
                + "53697817977846174064955149290862569321978468622482"
                + "83972241375657056057490261407972968652414535100474"
                + "82166370484403199890008895243450658541227588666881"
                + "16427171479924442928230863465674813919123162824586"
                + "17866458359124566529476545682848912883142607690042"
                + "24219022671055626321111109370544217506941658960408"
                + "07198403850962455444362981230987879927244284909188"
                + "84580156166097919133875499200524063689912560717606"
                + "05886116467109405077541002256983155200055935729725"
                + "71636269561882670428252483600823257530420752963450").split("0");
        System.out.println((new Problem_8()).getMaxProductOfFiveConsequtiveDigits(nums));
    }
}

Popularity: 6% [?]

Project Euler : Find the nth Prime

Published on December 11, 2009 in Problems. 0 Comments

The seventh problem in Project Euler is stated thus:

Find the 10001st prime number.

Well, there are two ways that I knew of to find the prime numbers. One is by checking if it has any factors below sqrt(n) and the second method is the Sieve of Eratosthenes. I checked online to search for a better method, but could not find any. So I decided to go ahead implementing the factor thing.

I created an array to hold all the discovered primes. Now given a number, I check if it already is in the list or not. If yes, it is a prime. If not, I check if any of the primes in the list, less than square root of the number, is a factor of this number or not. My code was able to all these computations and throw the answer in 94ms.

The solution proposed by the Project Euler authors improvised on this. They used an additional fact that any prime greater than 3 is of the form 6k+/-1.

Also, another thing that I read was that if you know the upper bound of the prime number, then the Sieve of Eratosthenes gives the answer much quickly. To estimate the upper bound Wikipedia has a topic called Prime Number Theorem, which could be looked up.

I am pasting below the piece of code I wrote to generate the 10001st prime number:

public class Problem_7 {
    public Long getPrimeByIndex(int index) {
        if (index == 1)
            return 2L;

        // An array of all the discovered primes
        List<Long> primes = new ArrayList<Long>();
        primes.add(2L);

        Long num = 3L;

        // Start the stopwatch
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.start();

        // Search for primes by dividing num with all the known prime numbers
        while (primes.size() != index) {
            boolean isComposite = false;
            double sqrt = Math.sqrt(num);
            for (Long p : primes) {
                if (p > sqrt)
                    break;
                if (num % p == 0) {
                    isComposite = true;
                    break;
                }
            }
            if (!isComposite)
                primes.add(num);
            num++;
        }

        stopwatch.stop();
        System.out.println("The reading for operation is: " + stopwatch);

        return primes.get(index - 1);
    }

    public static void main(String[] args) {
        System.out.println((new Problem_7()).getPrimeByIndex(10001));
    }
}

Popularity: 14% [?]

Project Euler : Palindrome Made From Product Of Three Digit Numbers

Published on December 10, 2009 in Problems. 0 Comments

The problem was to find the largest palindrome made from the product of two 3-digit numbers.

I did not want to do a brute force thing. So I searched the net for some property of palindrome which might help me in the solution. But I found none. However I stumbled across a piece of information which helped reduce the number of computations in the brute force. The piece of information was this:

836 * 836 = 698896

So all I did was to count up from 836 to 999. Below is the code that I wrote in Java:

public class Problem_4 {
    private static int knownPalin = 698896;

    private boolean checkPalindrome(String word) {
        StringBuffer reverse = new StringBuffer(word);
        reverse.reverse();
        return word.equals(reverse.toString());
    }

    public void findGreatestMultiplePalindrome() {
        int palin = Problem_4.knownPalin;
        int a = 836;
        int b = 836;

        Stopwatch stopwatch = new Stopwatch();

        stopwatch.start();
        for (int i = 836; i < 1000; i++) {
            int j = palin / i;
            for (; j < 1000; j++) {
                int prod = i * j;
                if (checkPalindrome(String.valueOf(prod))) {
                    palin = prod;
                    a = i;
                    b = j;
                }
            }
        }
        stopwatch.stop();
        System.out.println("The reading for operation is: " + stopwatch);

        System.out.println("A: " + a + ", B: " + b + ", Product: " + palin);
    }

    public void findGreatestMultiplePalindromeAlternate() {
        int palin = Integer.MIN_VALUE;
        int a = 0;
        int b = 0;

        Stopwatch stopwatch = new Stopwatch();

        stopwatch.start();
        for (int i = 999; i > 99; i--)
            for (int j = 990; j > 99; j -= 11) {
                int prod = i * j;
                if (prod > palin &amp;amp;&amp;amp; checkPalindrome(String.valueOf(prod))) {
                    palin = prod;
                    a = i;
                    b = j;
                }
            }
        stopwatch.stop();
        System.out.println("The reading for operation is: " + stopwatch);

        System.out.println("A: " + a + ", B: " + b + ", Product: " + palin);
    }

    public static void main(String[] args) {
        Problem_4 p = new Problem_4();
        p.findGreatestMultiplePalindrome();
    }
}

It took 15ms to output the answer.

Then I looked at the solutions proposed by the others. Most of the people had used brute force. However, there was one smart simplification done.

Any palindrome is of the form abccba.

abccba = 100000a + 10000b + 1000c + 100c + 10b + a = 100001a + 10010b + 110c

Thus our palindrome is of the form

11(9091a + 910b + 100c ) = mn

And since 11 is a prime number, one of our m or n has to be a multiple of 11. Thus instead of looping through all the numbers, having one loop only through the multiples of 11 reduces the number of products to be checked.

The alternate method is the one with the multiple of 11 idea.

Popularity: 28% [?]

Why Telangana

Published on December 10, 2009 in Miscel. 0 Comments

Until yesterday, I had never taken the threats of forming a new state of Telangana seriously. I always thought it was just another political issue which would be used to garner votes before the elections. But when I was told that the centre government had approved the formation of a new state, I was shocked. It prompted me to read up the history behind the whole thing. Just like any political issue, even this topic had its pros and cons on either side. You could be a devil’s advocate and argue from either side, but I do not think this is a proper resolution.

Now I am not too aware of all the reasons behind this stir, but a few searches over the net convinced me that the Indian government does not have the balls to stamp its authority, leave aside dialogues. By agreeing to the demands of a new state, it has opened the Pandora’s box, inviting further trouble.

The history as I understand is that after the abolition of the Nizam state, the Hyderabad state was created with Hyderabad as the capital. Later on, this Hyderabad state was merged into the Madrasas state, which today is the Rayalseema and the Coastal Andhra, to form the state as we know today – Andhra Pradesh. Even then there were opposition from the Telangana people. Their primary concern was that the madrasas being more literate and well educated could snatch jobs from the Telangana people. Inferiority complex basically! Also, throughout the years, those people felt that financial revenues generated from Hyderabad was being diverted to improve the coastal andhra, leaving the Telangana region poor and under-developed.

And the struggle for a new state is also not new. The agitation is as old as ‘69. But the then Indian Prime Minister, Ms. Indira Gandhi, who has the reputation of being the only man in her cabinet, played a masterstroke and made the Chief Minister of Andhra Pradesh a Telangana minister. So the agitation of ‘69 died after personal gain. Later on, P V Narsimha Rao became the Chief Minister. He too hails from Telangana.

In the elections before this one, TRS and Congress joined hands. Congress declared that it would definitely form the new state if it came to power. Once again, after the elections, YSR got cold feet and did nothing to resolve the issue. So in this election, TRS contested without the Congress support. But they were badly defeated. They lost more ground, and won fewer seats than they had earlier.

Our defeated hero, K Chandrasekhar Rao, had no where to go. His pride hurt. And once YSR was dead, KCR got active and started the agitation once again. He took up a fast unto death pledge and in his 11th day the government gave up. They feared a revolt and huge loss of lives on a planned Chalo Assembly motion.

And now buoyed by the victory of TRS, other factions have been revived in their demands of new states for themselves. And what will the government do if a lost cause political leader will go into fast in every state. Shall we double the number of states now. Shall we bow to the whims of these fools. And if the government refuse to create Gorkhaland, but go ahead with Telangana, how do they justify themselves? Where’s the rationale behind all these.

When I was young, I liked the phrase Unity in Diversity. I thought of India being comprised of several different customs, religions and philosophies, and yet united as a single country. But the more I think of it now, the more I see my country bleeding to death. The opportunist bastards have exploited our country and the poor, illiterates have been a tool of exploitation. I hate my fellow countrymen.

I hate the poverty in India. These dumb, senseless, un-educated people who get swayed by sweet words of a manipulating bastard are the undoing of India. They are the ones who let politicians divide us on casts, race and what not.

But what pains me is that even the educated people fall for these tricks. I hate my friends who support religious or caste leaders. I curse all the damned students who played any part in this agitation.

I think I am now beginning to understand politics. This is a game. You play with people to derive some gain out of it. In the process, you are also rewarded lots of fame if you succeed. I hate politicians, but like politics. No where in the world would it have been possible to get your wish by not eating for a couple of days.

Had I been the prime minister, I would have said this:

I dare you, I double dare you m*****f*****, say that one more Goddamn time!

Popularity: 3% [?]