Tag Archive for 'product'

Project Euler : Largest Sum Of Digits In Exponentiation

Published on August 25, 2011 in Problems. 0 Comments

The problem 56 of project euler requires one to sum the digits of the exponentiation a^b, where 1<= a,b <= 100, and find the largest sum.

Well, let’s just say I did it by proper brute force. Here’s my java code:

    public static int largestSumOfDigitsInExponentiationNew(int baseMax, int exponentMax) {
        int largest = 0;

        for (int i = 1; i <= baseMax; i++) {
            BigInteger num = BigInteger.valueOf(i);
            BigInteger prev = num;
            largest = Problem_56.checkLargestSum(prev, largest);
            for (int j = 2; j <= exponentMax; j++) {
                prev = prev.multiply(num);
                largest = Problem_56.checkLargestSum(prev, largest);
            }
        }

        return largest;
    }

    private static int checkLargestSum(BigInteger number, int curentLargest) {
        int sum = NumberUtil.getSumOfDigits(number);
        return curentLargest < sum ? sum : curentLargest;
    }

Popularity: 5% [?]

Project Euler : Finding Largest 9-Pandigital Number Formed As A Concatenated Product

Published on January 10, 2011 in Problems. 0 Comments

Problem 38 of Project Euler states the problem of finding the largest 1-9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1, 2, .. ,n) where n > 1. As an example, take the number 192 and its products with 1, 2 and 3.

192 * 1 = 192

192 * 2 = 384

192 * 3 = 576

The concatenated number 192384576 is a 9-digit pandigital number. Another example is that of multiplying 9 with (1, 2, 3, 4, 5) to yield the number 918273645.

The above serves as a hint. We now know that the required answer is at least greater than 918273645. Let us try to eliminate a few options.

Consider all 2 digit numbers in the interval [91, 98]. Their multiplication with 1, 2 and 3 will yield 2, 3 and 3 digit numbers respectively. Concatenating these numbers will result in a 8 digit number. But we need a 9-digit number. So we can rule out this case.

Consider all 3 digit numbers in the interval [918, 987]. Their multiplication with 1 and 2 will yield 3 and 4 digit numbers respectively. With the same logic as the previous case, we can rule out these numbers.

Consider all 4 digit numbers in the interval [9182, 9876]. Their multiplication with 1 and 2 will yield 4 and 5 digit numbers respectively. This is the range we are looking for.

After reducing the search space to 694 numbers, a simple java code did the work. It makes a call to NumberUtil.isNPandigital(int) which returns true if the number is pandigital and false otherwise.

public class Problem_38 {
    public static int getValue() {
        for (int i = 9876; i > 9183; i--) {
            int val = i * 100002;
            if (NumberUtil.isNPandigital(val)) return val;
        }

        return -1;
    }
}

Popularity: 9% [?]

Project Euler : Problem 32 – All Round Pandigital

Published on May 27, 2010 in Problems. 0 Comments

The problem requires one to find a product of two numbers such that the multiplicand/multiplier/product can be written as a 1 through 9 pandigital.

An example would be: 39 * 186 = 7254

Working with paper and a pencil, one can discover that the two form of solution are:

a * bbbb = cccc

aa * bbb = cccc

So all that was required to be done was generate all 9 digit permutations of 1-9 and then check if the arrangement satisfies any of the two cases mentioned above.

public class Problem_32<I extends Integer> {
	public static void main(String[] args) {
		System.out.println(new Problem_32<Integer>().computeSum());
	}

	public int computeSum() {
		int sum = 1;
		Set<Integer> products = new HashSet<Integer>();

		Iterator<CombinatoricsVector<I>> permutationIterator = getPermutationGenerator();
		while (!permutationIterator.isDone()) {
			permutationIterator.next();
			CombinatoricsVector<I> permutation = permutationIterator.getCurrentItem();
			products.add(checkCaseA(permutation));
			products.add(checkCaseB(permutation));
		}

		for (Integer i : products)
			sum += i;

		return sum;
	}

	/**
	 * Case A :: a x bbbb = cccc
	 *
	 * @return cccc if above equality holds, -1 otherwise
	 */
	private int checkCaseA(CombinatoricsVector<I> permutation) {
		int a = permutation.getValue(0);
		int b = get4Number(permutation, 1);
		int c = get4Number(permutation, 5);

		return a * b == c ? c : -1;
	}

	/**
	 * Case B :: aa x bbb = cccc
	 *
	 * @return cccc if above equality holds, -1 otherwise
	 */
	private int checkCaseB(CombinatoricsVector<I> permutation) {
		int a = get2Number(permutation, 0);
		int b = get3Number(permutation, 2);
		int c = get4Number(permutation, 5);

		return a * b == c ? c : -1;
	}

	private int get2Number(CombinatoricsVector<I> permutation, int startIdx) {
		return permutation.getValue(startIdx) * 10 + permutation.getValue(startIdx + 1);
	}

	private int get3Number(CombinatoricsVector<I> permutation, int startIdx) {
		return permutation.getValue(startIdx) * 100 + permutation.getValue(startIdx + 1) * 10
		        + permutation.getValue(startIdx + 2);
	}

	private int get4Number(CombinatoricsVector<I> permutation, int startIdx) {
		return permutation.getValue(startIdx) * 1000 + permutation.getValue(startIdx + 1) * 100
		        + permutation.getValue(startIdx + 2) * 10 + permutation.getValue(startIdx + 3);
	}

	private Iterator<CombinatoricsVector<I>> getPermutationGenerator() {
		ArrayList<I> array = new ArrayList<I>();
		for (int i = 1; i < 10; i++)
			array.add((I) new Integer(i));

		Iterator<CombinatoricsVector<I>> permutationIterator = new PermutationGenerator<I>(new CombinatoricsVector<I>(
		        array)).createIterator();
		permutationIterator.first();

		return permutationIterator;
	}
}

Popularity: 13% [?]

Project Euler : Finding The nth Digit Of The Fractional Part Of Irrational Number

Published on January 5, 2010 in Problems. 0 Comments

The Problem 40 of Project Euler required just a pencil and a paper to get the answer. We are given an irrational decimal fraction by concatenating consecutive integers:

0.123456789101112131415 …

The 12^{th} digit of this irrational number is 1 and is denoted as d_{12}. The problem requires us to determine the product:

d_1 x d_{10} x d_{100} x d_{1000} x d_{10000} x d_{100000} x d_{1000000}

A simple enumeration of digits and their positions works out easily.

To begin with, there are only 9 single digit numbers, namely, 1 – 9. So the first 9 places are occupied by single digit numbers. Next, there are 90 double digit numbers from 10 – 99. So these occupy a total of 180 places. We have now accounted for 189 places in out irrational number.

Determine the digits d_{100} and d_{1000} are as simple as illustrated below:

For d_{100}:

Excess from last known digit position = 100 – 9 = 91

Numbers crossed in 91 positions = 91 / 2 = 45

Since the remainder is 1, we want the 1st digit of the 46th number from the one that appeared on position 9.

Thus the number we seek is 9 + 46 = 54, and the digit is therefore 5.

For d_{1000}:

Excess from last known digit position = 1000 – 189 =18 1

Numbers crossed in 811 positions = 811 / 3 = 270

Since the remainder is 1, we want the 1st digit of the 271st number from the one that appeared on position 189.

Thus the number we seek is 99 + 271 = 370, and the digit is therefore 3.

Repeating the same for all the digits we needed, the result is:

d_{1} = 1

d_{10} = 1

d_{100} = 5

d_{1000} = 3

d_{10000} = 7

d_{100000} = 2

d_{1000000} = 1

Thus the product is 210

Popularity: 7% [?]

Project Euler : Greatest Product of 4 Numbers In A 20×20 Grid

Published on December 17, 2009 in Problems. 0 Comments

This is the 11th problem from Project Euler and I have used brute force to solve it.

Brute force:

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

public class Problem_11 {
	private static int s_gridSize = 20;

	public int getMaxProduct(int[][] numberGrid) {
		int maxProduct = 0;

		for (int i = 0; i &amp;amp;lt; Problem_11.s_gridSize; i++)
			for (int j = 0; j &amp;amp;lt; Problem_11.s_gridSize; j++) {
				int max = getMax(new int[] { getHorizontalProduct(i, j, numberGrid),
				        getVerticalProdut(i, j, numberGrid), getDiagonalProductA(i, j, numberGrid),
				        getDiagonalProductB(i, j, numberGrid) });
				if (max &amp;amp;gt; maxProduct)
					maxProduct = max;
			}

		return maxProduct;
	}

	private int getHorizontalProduct(int iIndex, int jIndex, int[][] numberGrid) {
		if (iIndex &amp;amp;gt; Problem_11.s_gridSize - 4)
			return 0;
		else
			return numberGrid[iIndex][jIndex] * numberGrid[iIndex + 1][jIndex] * numberGrid[iIndex + 2][jIndex]
			        * numberGrid[iIndex + 3][jIndex];
	}

	private int getVerticalProdut(int iIndex, int jIndex, int[][] numberGrid) {
		if (jIndex &amp;amp;gt; Problem_11.s_gridSize - 4)
			return 0;
		else
			return numberGrid[iIndex][jIndex] * numberGrid[iIndex][jIndex + 1] * numberGrid[iIndex][jIndex + 2]
			        * numberGrid[iIndex][jIndex + 3];
	}

	private int getDiagonalProductA(int iIndex, int jIndex, int[][] numberGrid) {
		if (iIndex &amp;amp;gt; Problem_11.s_gridSize - 4 || jIndex &amp;amp;gt; Problem_11.s_gridSize - 4)
			return 0;
		else
			return numberGrid[iIndex][jIndex] * numberGrid[iIndex + 1][jIndex + 1] * numberGrid[iIndex + 2][jIndex + 2]
			        * numberGrid[iIndex + 3][jIndex + 3];
	}

	private int getDiagonalProductB(int iIndex, int jIndex, int[][] numberGrid) {
		if (iIndex &amp;amp;gt; Problem_11.s_gridSize - 4 || jIndex &amp;amp;lt; 3)
			return 0;
		else
			return numberGrid[iIndex][jIndex] * numberGrid[iIndex + 1][jIndex - 1] * numberGrid[iIndex + 2][jIndex - 2]
			        * numberGrid[iIndex + 3][jIndex - 3];
	}

	private int getMax(int... numbers) {
		int max = numbers[0];
		for (int i = 1; i &amp;amp;lt; numbers.length; i++)
			if (numbers[i] &amp;amp;gt; max)
				max = numbers[i];
		return max;
	}

	public static int[][] getNumbersGrid(String fileName) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new FileReader(fileName));

		int[][] numberGrid = new int[Problem_11.s_gridSize][];

		for (int i = 0; i &amp;amp;lt; Problem_11.s_gridSize; i++) {
			numberGrid[i] = new int[Problem_11.s_gridSize];
			String[] nums = bufferedReader.readLine().split(&amp;amp;quot; &amp;amp;quot;);
			for (int j = 0; j &amp;amp;lt; Problem_11.s_gridSize; j++)
				numberGrid[i][j] = Integer.parseInt(nums[j]);

		}

		return numberGrid;
	}

	public static void main(String[] args) throws IOException {
		String fileName = &amp;amp;quot;problem_11.in&amp;amp;quot;;
		System.out.println(new Problem_11().getMaxProduct(Problem_11.getNumbersGrid(fileName)));
	}
}

Popularity: 5% [?]

Project Euler : Fast Factorial Computation

Published on December 16, 2009 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: 17% [?]

Project Euler : Sum Of Digits In a^b

Published on December 14, 2009 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: 5% [?]

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: 3% [?]