Tag Archive for 'algorithm'

Sum Of Divisors

Published on 2 years ago in Problems. 0 Comments

Let n be an integer factorized as following:

n = {p_1}^{e_1} \times {p_2}^{e_2} \times \ldots \times {p_k}^{e_k}

The sum of divisors of n is:

\sigma(n) = a_1 \times a_2 \times \ldots \times a_k

where,

a_k = \frac{{p_k}^{e_k + 1} - 1}{p_k - 1} = {p_k}^{e_k} \times \ldots \times {p_k}^{2} \times {p_k}^{1}

In the simpler case of n = p^e, the sum is

\sigma(n) = p^e \times \ldots \times p^2 \times p

This I learned from the article written by Hisanori Mishima found here. The idea translates into a nice little loop to find the sum of divisors. The Java implementation of it has been done by me and is thus:

package pba.common.number;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class PrimeNumber {
	private List<Integer> m_primeNumbers;

	/**
	 * @param sizeOfSieve The upper bound to the determination of prime numbers.
	 */
	public PrimeNumber(int sizeOfSieve) {
		m_primeNumbers = new ArrayList<Integer>();
		sieveOfEratosthenes(sizeOfSieve);
	}

	/**
	 * @param number The number whose sum of divisors is required
	 * @return The sum of divisors of the given number
	 */
	public int getSumOfDivisors(int number) {
		int sum = 1;
		while (number > 1) {
			int temp = 1;
			int primeFactor = getSmallestPrimeFactor(number);
			while (number % primeFactor == 0) {
				temp = temp * primeFactor + 1;
				number /= primeFactor;
			}
			sum *= temp;
		}

		return sum;
	}

	/**
	 * @param number The number whose smallest prime factor is required
	 * @return The smallest rpime factor for the given number
	 */
	public int getSmallestPrimeFactor(int number) {
		for (int prime : m_primeNumbers)
			if (number % prime == 0)
				return prime;

		return Integer.MIN_VALUE;
	}
}

Note that the list of prime numbers can be quickly found by using the Sieve of Eratosthenes.

Popularity: 11% [?]

Project Euler : Maximum Sum Traversing Top To Bottom In A Triangle

Published on 2 years, 1 month ago in Problems. 17 Comments

The 18th and the 67th problems in Project Euler are one and the same. The only difference is in the input test case. The problem 18 has a smaller input and 67 has a large input. For the explanation purpose, I’ll consider problem 18. The code without any modification can be extended to 67th problem.

Given a triangle of numbers, the objective is to determine the maximum sum along paths descending from the apex of the triangle to the base. Consider the example:

3

7     4

2     4     6

8     5     9     3

The maximum sum occurs along the path 3-7-4-9.

The problem required us to determine the maximum sum for any given triangle. Also an interesting thing is mentioned about the problem, in case you were considering a brute force method of checking every path:

It is not possible to try every route to solve this problem (where the base of the triangle has 100 numbers), as there are 2^(99) altogether! If you could check one trillion (10^(12)) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Being forewarned, I never once gave a thought to the brute force solution.

This problem was not as tricky as they tried to sound it. The solution is quite easy to see. I’ll run you through the idea as it formed in my mind. I used the top-to-bottom approach for forming the idea and coming up with the solution, and then implemented the solution in bottom-to-top sweep. I hope you have realized that a greedy solution will not work here.

Consider the triangle given above. I’ll work out the maximum path for it from top to bottom.  We start with 3. We may choose either 7 or 4. To help make this choice, consider the two triangles with apex 7 and the other with 4. So we have two smaller triangles of height 3 each. Say the maximum length for the triangle with apex 7 is x and with apex 4 is y. If x > y, we choose 7 as the next on the path, else 4.

Thus, at every step we form two triangle of height 1 smaller, and choose the apex which has the larger sum. Implemented as it is will give us the recursive solution. To get an iterative solution to this problem, one could traverse from bottom-to-top. The bottom-to-top approach is also simple. It is greedy in approach.

Consider the penultimate row, specifically the triangle with 2 as apex and 8, 5 as the base. The maximum sum in this triangle is 2+8 =  10. Replace 2 with 10. Do the same for all the triangles formed with the penultimate layer as the apex. Thus our triangle reduces to

3

7     4

10     13     15

You know what to do next. Keep applying the same till the apex of the original triangle has the maximum sum.

I have implemented the bottom-to-top method so as to avoid recursion. Here is my code:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Problem_18 {
	private static int heightOfTree = 100;
	private final String fileName = "problem_67.in";
	private int[][] tree;

	public int maxValue() throws IOException {
		readTree();

		for (int i = Problem_18.heightOfTree - 2; i >= 0; i--)
			for (int j = 0; j <= i; j++)
				tree[i][j] += tree[i + 1][j] > tree[i + 1][j + 1] ? tree[i + 1][j] : tree[i + 1][j + 1];

		return tree[0][0];
	}

	private void readTree() throws IOException {
		tree = new int[Problem_18.heightOfTree][];

		BufferedReader bufferedReader = new BufferedReader(new FileReader(fileName));
		for (int i = 0; i < Problem_18.heightOfTree; i++) {
			tree[i] = new int[i + 1];
			String[] values = bufferedReader.readLine().split(" ");
			for (int j = 0; j <= i; j++)
				tree[i][j] = Integer.parseInt(values[j]);
		}
	}

	public static void main(String[] args) throws IOException {
		System.out.println(new Problem_18().maxValue());
	}
}

Popularity: 100% [?]

Project Euler : Longest Sequence Using A Number Under Million

Published on 2 years, 1 month ago in Problems. 1 Comment

Problem number 14 of Project Euler gave a sequence.

n = n/2 if (n is even)

n = 3*n+1 (if n is odd)

It has been observed that all the numbers in this sequence do end up at 1, though this is yet to be proved! For example, if we consider the number 13, then the sequence pans out as

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

The length of the sequence in this case is 9. The challenge was to find the largest starting number below 1 million which produces the maximum length sequence. Do note that intermediate numbers might cross the 1 million mark.

The first thing that struck me was the repetitive nature of the problem. Say we are checking the lengths for every number and we start from 1 upwards. So, by the time we get to 13, we would have already calculated the value of 10. If we remember this value, then the value for 13 effectively becomes 3 + value for 10. Thus memoization can be used to speed up the computation.

But if we remember all the values, we will require a very large array as the number greater than 1 million are bound to occur. An another interesting thing struck me. Consider the number 16. It has only 2 predecessors in the sequence, namely 5 and 32. No other number can land on 16 in one step. So, if I know the values for 5 and 32, I need not know the value for 16 anymore. Also note that we shall not miss the largest sequence value by removing keys like this because its predecessors will have a larger sequence length.

Using these two ideas I implemented a recursive solution to give me the answer. Well, I did get the answer but the time taken was large. It took 3845ms to get the answer.

The first modification was to replace the recursive function with an iterative one. This reduced the time taken to just 1907ms. However, the one drawback of moving from a recursive solution to an iterative one was that while in recursive I was able to store the path lengths for intermediate numbers too, in the iterative one I am able to store the results for the starting number only. I suppose if I have a stack of the numbers visited, then I might be able to add their values and consolidate the map so as to remove the unnecessary entries.

At this point, another thing came to my mind. I had used a hash map to remember the already computed values. I remembered Prasun telling me that the jvm allocates a default space to the map, which is as low as 11, if the initial size of the map is not specified. When the number of values being put into the map increases, the map size is readjusted. And since I had not specified any initial size, my map was undergoing all these extra operations. So I went ahead and specified a map of size 1 million. Voila! The time reduced to under 1500ms.

Another couple of observations I made was regarding the size of the map. If I do not optimize the map to contain only the essential entries, then the map is as large as 97000 entries. But with the optimization function that I have used, the size required reduces to 62000. A further modification of calculating the lengths for only odd numbers reduces the map size to just 48500, which is half of the original usage. And since the time invested in periodic optimization of the map contributes to only some 100ms, I think it is a good enough trade off to optimize the entries stored in the map.

All said and done, it is a brute force solution with memoization. I look to better the solution sometime. Below is the code that I have written.

import java.util.HashMap;
import java.util.Map;

import stopwatch.Stopwatch;

public class Problem_14 {
	private static long MAX_NUMBER = 1000000;
	private Map<Long, Integer> m_pathLengths = new HashMap<Long, Integer>((int) (2 * Problem_14.MAX_NUMBER));

	public long getLongestChainStartingNumber() {
		int maxLength = 0;
		long maxLengthStartNumber = -1;

		for (long i = 30001; i < Problem_14.MAX_NUMBER; i += 2) {
			int length = getPathLength(i);
			if (length > maxLength) {
				maxLength = length;
				maxLengthStartNumber = i;
			}
		}
		System.out.println(m_pathLengths.size());

		return maxLengthStartNumber;
	}

	private int getPathLength(Long val) {
		long value = val;
		int pathLength = 0;
		for (; val > 1; pathLength++) {
			if (m_pathLengths.containsKey(val)) {
				pathLength += m_pathLengths.get(val);
				break;
			}
			val = val % 2 == 0 ? val / 2 : 3 * val + 1;
		}
		m_pathLengths.put(value, pathLength);
		optimiseMap(value);

		return pathLength;
	}

	private void optimiseMap(long keyAdded) {
		if (keyAdded % 2 == 1) {
			// odd key added.
			// 5 -> 16, 16 can be reached from only 5 or 32
			// 7 -> 22, 22 can be reached from only 7 or 44
			long keyToBeChecked = 3 * keyAdded + 1;
			if (m_pathLengths.containsKey(2 * keyToBeChecked))
				m_pathLengths.remove(keyToBeChecked);
		} else {
			// even key added.
			// 32 -> 16, 16 can be reached from only 5 or 32
			// 18 -> 9, 9 can be reached from only 18
			long keyToBeChecked = keyAdded / 2;
			if ((keyToBeChecked - 1) % 3 == 0) {
				if (m_pathLengths.containsKey((keyToBeChecked - 1) / 3))
					m_pathLengths.remove(keyToBeChecked);
			} else
				m_pathLengths.remove(keyToBeChecked);
		}
	}

	public static void main(String[] args) {
		Stopwatch stopwatch = new Stopwatch();
		stopwatch.start();
		System.out.println(new Problem_14().getLongestChainStartingNumber());
		stopwatch.stop();
		System.out.println("The reading for operation is: " + stopwatch);
	}
}

Popularity: 8% [?]

Project Euler : Fast Factorial Computation

Published on 2 years, 1 month ago in Problems. 0 Comments

The 20^{th} problem in Project Euler asked the summation of all the digits in 100!. I searched over the net for fast factorial algorithms and came across this site:

Fast Factorial Functions

I implemented the Poor Man’s algorithm to solve the problem. However, I wasn’t able to find out the logic behind the working of the algorithm. Poor Man’s algorithm for factorial returned no good searches. I need to keep looking.

The code given at the above site is in C++. It was a child’s play to convert it into Java. It was mostly copy-paste and remove any C++ specific method to Java one.

Below is the Java code:

public class Problem_20 {
	private long N;

	public String factorial(int n) {
		if (n < 0)
			return "n > 0 required as input";
		if (n < 2)
			return "1";
		DecInteger p = new DecInteger(1);
		DecInteger r = new DecInteger(1);
		N = 1;
		int h = 0, shift = 0, high = 1;
		int log2n = (int) Math.floor(Math.log(n) * 1.4426950408889634);
		while (h != n) {
			shift += h;
			h = n >> log2n--;
			int len = high;
			high = h - 1 | 1;
			len = (high - len) / 2;
			if (len > 0) {
				p = DecInteger.multiply(p, product(len));
				r = DecInteger.multiply(p, r);
			}
		}
		r = DecInteger.multiply(r, DecInteger.pow2(shift));

		return r.toString();
	}

	private DecInteger product(int n) {
		int m = n / 2;
		if (m == 0)
			return new DecInteger(N += 2);
		if (n == 2)
			return new DecInteger((N += 2) * (N += 2));
		return DecInteger.multiply(product(n - m), product(m));
	}

	public static void main(String[] args) {
		int n = 100;
		Problem_20 p = new Problem_20();
		String val = p.factorial(n);
		int sum = 0;
		for (int i = 0; i < val.length(); i++)
			sum += val.charAt(i) - '0';
		System.out.println(sum);
	}
}

class DecInteger {
	private final static long mod = 100000000L;
	private int[] digits;
	private int digitsLength;

	public DecInteger(long value) {
		digits = new int[] { (int) value, (int) (value >> 32) };
		digitsLength = 2;
	}

	private DecInteger(int[] digits, int length) {
		this.digits = digits;
		digitsLength = length;
	}

	public static DecInteger pow2(int e) {
		if (e < 31)
			return new DecInteger((int) Math.pow(2, e));
		return DecInteger.multiply(DecInteger.pow2(e / 2), DecInteger.pow2(e - e / 2));
	}

	public static DecInteger multiply(DecInteger a, DecInteger b) {
		int alen = a.digitsLength, blen = b.digitsLength;
		int clen = alen + blen + 1;
		int[] digits = new int[clen];
		for (int i = 0; i < alen; i++) {
			long temp = 0;
			for (int j = 0; j < blen; j++) {
				temp = temp + a.digits[i] * (long) b.digits[j] + digits[i + j];
				digits[i + j] = (int) (temp % DecInteger.mod);
				temp = temp / DecInteger.mod;
			}
			digits[i + blen] = (int) temp;
		}
		int k = clen - 1;
		while (digits[k] == 0)
			k--;
		return new DecInteger(digits, k + 1);
	}

	public String toString() {
		StringBuffer val = new StringBuffer(digitsLength * 10);
		for (int j = 0; j < digitsLength; j++)
			val.insert(0, digits[j]);
		return val.toString();
	}
}

Popularity: 19% [?]

Project Euler : Sum Of Digits In a^b

Published on 2 years, 1 month ago in Problems. 0 Comments

The problem no. 16 in Project Euler required us to find the sum of all the digits of the number 2^{1000}. Well, a no brainer would be to use the BigInteger and find the number by multiplication. I wanted a better solution.

But my knowledge and wits failed me. I must accept taking help on this one. I googled up a bit and found a very neat way of exponentiation. The basic funda is this:

2^n = 2 * 2^{n-1}

=> 2^n = 2^{n-1} + 2^{n-1}

So at any given time, if we have an array of digits of  say 2^p, then getting 2^{p+1} is as simple as doubling all the digits and adjusting the carry-overs. The same principle can be easily extended to deal with any base.

Below I have pasted my code which can find the sum of digits for any arbitrary a^b.

public class Problem_16 {
	public long sumOfDigits(int base, int exp) {
		int numberOfDigits = (int) Math.ceil(exp * Math.log10(base));
		int[] digits = new int[numberOfDigits];
		digits[0] = base;
		int currentExp = 1;

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

		while (currentExp < exp) {
			currentExp++;
			int carry = 0;
			for (int i = 0; i < digits.length; i++) {
				int num = base * digits[i] + carry;
				digits[i] = num % 10;
				carry = num / 10;
			}
		}

		long sum = 0;
		for (int digit : digits)
			sum += digit;

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

		return sum;
	}

	public static void main(String[] args) {
		int base = 2;
		int exp = 1000;
		System.out.println(new Problem_16().sumOfDigits(base, exp));
	}
}

Popularity: 6% [?]

Project Euler : Largest Product Of Five Consequtive Digits

Published on 2 years, 1 month ago 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: 4% [?]

Project Euler : Find the nth Prime

Published on 2 years, 1 month ago 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: 24% [?]

Project Euler : Palindrome Made From Product Of Three Digit Numbers

Published on 2 years, 1 month ago 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: 31% [?]

Project Euler : Finding The Largest Prime Factor Of A Given Number

Published on 2 years, 5 months ago in Problems. 0 Comments

The problem is this: Find the largest prime factor of a given number. One brute force way is to find a factor of the given number and then perform primality testing on the number. But the test to check if the number is prime or not is a costly operation if one does not have a set of all primes.

So there was a need for me to avoid the testing of a number for primality.

One interesting thing to be noticed is that the smallest factor of a number has to be prime. Suppose if it were not, then it implies that it can be written as a product of two smaller numbers which contradicts the hypothesis that the factor is the smallest factor.

So we can avoid the testing of primality by taking the smallest factor. But the problem requires us to determine the largest prime factor. The lergest prime factor can be recursively obtained by using the following:

public static long largestPrimeFactor(long n) {
    long prime = smallestPrimeFactor(n);
    return Math.max(prime, largestPrimeFactor(n/prime));
}

Where the smallest prime factor method returns the smallest factor of n.

One of the interesting things that I read while solving this problem was that after 3, all the prime numbers satisfy the general formula 6n-1, 6n+1. So the primes will be in the series :

6(1) – 1 = 5

6(1) + 1 = 7

6(2) – 1 = 11

6(2) + 1 = 13 …

In fact, primes after the number p belong to the series p# n + m, where p# is called the primorial. Look up the wiki entry to learn more.

Popularity: 4% [?]