Thread: Product of array values

Ok, I have failed miserably at trying to move my original comment from here:

http://www.javaprogrammingforums.com...html#post43986

So appolagies for that.

Anyway I have since managed to solve the problem but I can't help but feel that part of it is a little 'clunky'! (To a trained eye it probably all looks 'clunky'). I havn't managed to work out how to implement your solution sean4u yet but I will persist with it. My current solution is:

import java.util.*;
 
public class ConsecutiveNumbers {
	private static final String inputDigitString = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
	private int[] inputDigitIntArray = new int[inputDigitString.length()];
	private int[] productArray = new int[inputDigitString.length() - 4];
 
	public ConsecutiveNumbers() {
		for (int i = 0; i < inputDigitString.length(); i++) {
			inputDigitIntArray[i] = Character.digit(inputDigitString.charAt(i), 10);
		}
	}
 
	public int[] setProductArray() {
		int numOfConNums = 5;
 
		for (int i = 0; i < inputDigitIntArray.length - (numOfConNums - 1); i++) {
			productArray[i] = (inputDigitIntArray[i] * inputDigitIntArray[i + 1] * inputDigitIntArray[i + 2] * inputDigitIntArray[i + 3] * inputDigitIntArray[i + 4]);
		}
		return productArray;
	}
 
	public int sortProductArray() {
		Arrays.sort(productArray);
		return productArray[productArray.length - 1];
	}
 
	public static void main(String[] args) {
		ConsecutiveNumbers arrayOne = new ConsecutiveNumbers();
		arrayOne.setProductArray();
		System.out.println("Max: " + arrayOne.sortProductArray());
	}
}

The part that I am specifically unhappy with is the expression Im using to fill the productArray:

for (int i = 0; i < inputDigitIntArray.length - (numOfConNums - 1); i++) {
			productArray[i] = (inputDigitIntArray[i] * inputDigitIntArray[i + 1] * inputDigitIntArray[i + 2] * inputDigitIntArray[i + 3] * inputDigitIntArray[i + 4]);
		}

How can I condense that down to be more elegant?

Hi Kevin,

Yes it does work, yes it does what I want and yes I understand it. So I guess I should be happy It was more out of curriosity that I wanted to see if the whole idea could be refined.

The project on the whole is to find the largest product of 5 consecutive numbers from a large number (inputDigitString). My basic approach was to input the number as a String and then convert it to an Int[] so I could isolate the individual numbers. I then used a for loop to run through each int, find the product of the 5 int (ie. i * i+1 * i+2 * i+3 * i+4) and store those values in a second array. Then its just a case of sorting the array so I get the largest value at the end.

With regards to your for loop, is it possible to enter a for loop into the index of an array? ie.

for (int i = 0; i < inputDigitIntArray.length - (numOfConNums - 1); i++) {
			productArray[i] = inputDigitIntArray[....for loop inside here....];
		}

...Obviousley providing an int is returned.

Instead of doing +0, +1, +2,

The reason OP is using constant array index increments is because of my suggestion to 'slide a window':
http://www.javaprogrammingforums.com...html#post43985

The point of the 'sliding window' is that when you're finding the products of all lists of 5 consecutive integers in the list (the objective, possibly also omitted from this thread), there's a brute-force solution that does every 5-way product (multiplying each individual number 5 times in 5 separate products) from scratch. That would be a nest of two for-loops, whether the inner for-loop was in a method or not. It hardly matters for 5 in the inner loop (and possibly not for the OP's objective), but algorithmically that's an O(N^2) solution where an O(N) one exists: simply divide the previous result by its first multiplicand and multiply it by the last in the current 5.

The +1, +2 etc are possibly an evolutionary mutation on the 'window' theme which is still O(N^2) and may die out when the fitter variant emerges. I hope that explains a bit why you're looking at some weirdness in OP's source: it's my fault.

If you loop for every element in your input integer array, you can multiply your product variable by the current element each time. If the current element is placed 4 or higher, you output the product because it is the product of 5 terms. After you output the product and still in the same if clause, you divide the product by the element at here-4 and the product is now the product of the last 4 terms. There's no need to keep a separate array for the product terms - all you care about is the product and being able to find the element that "falls out of the window" each time around the loop.

I can see that but if I don't store the products in a second array how do I compare the products to find the largest product? Presumably I would need to store the value in a variable and then perform some sort of comparison to determin if the new product is larger than the stored variable.

But, the real answer is probably that you're approaching this from a weird direction, as that does look strange to me.

Could you possibly explain why I'm approaching this from a weird direction? How would you have approached the problem?

store the value in a variable and then perform some sort of comparison to determin if the new product is larger than the stored variable

That is the answer to the question you asked. You'll need to do this each time around the loop, but I held off pointing out yesterday that you were creating a list of results for a problem that said "find the greatest". You can do it exactly as you say above.

PS. What does OP stand for?

Urban Dictionary: op

I meant the first definition, unless urbandictionary presents the page to you in a different order.

Thanks.

Ok, I've implemented your idea but there is a problem with it. Zero causes the equation to breakdown. assume the numbers are as follows:

1234501123456789

1*2*3*4*5 = 120 (This works fine as the starting value)
2*3*4*5*0 = 0 (120/1 * 0 = 0 this works fine)
3*4*5*0*1 = 0 (0/2 * 1 = 0 this works)
4*5*0*1*1 = 0 (0/3 * 1 = 0 this works)
5*0*1*1*2 = 0 (0/4 * 2 = 0 this works)
0*1*1*2*3 = 0 (0/5 * 3 = 0 this works)
1*1*2*3*4 = 24 (0/0 * 4 = 0 this doesn't work)
...

Once the product value becomes 0 you can't get out of it by using the previouse value as a starting point.

Absolutely right - I didn't see that one coming! It's going to make the loop look a bit messier, but you could check for 'a zero leaving the window' and recalculate the 5-way product. I can't think immediately of a better way of doing it.

Ill sleep on it and see if I can come up with a solution. Thanks for your help.

All 5-way products that include a zero term are themselves zero. If your current greatest is greater than zero then on first encountering a zero element in the input array, you could reset your product to 1 and your window 'fullness' to 0. It may not be any less messy than recalculating the last 4 when the zero exits. You'd have to keep a separate int to keep track of how 'full' your window is. Yet another alternative may be to keep a count of how many zero terms are in the window, skipping the multiply / divide until a zero exits while the zero-count is 1.

You could always go back to doing it with a nested for loop... :-)