Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 14 of 14

Thread: Product of array values

  1. #1
    Member
    Join Date
    Sep 2011
    Posts
    63
    My Mood
    Confused
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Product of array values

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

    Help with ArrayList ( Adding certain elements together)

    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?


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,159
    My Mood
    Hungover
    Thanks
    141
    Thanked 595 Times in 510 Posts

    Default Re: Product of array values

    I'm not sure what you're trying to do there, but just by glancing at it, you could condense that into a nested for loop. Instead of doing +0, +1, +2, just use another for loop and increment by that variable.

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

    But also, I wouldn't worry TOO much about using the most elegant solution. Does it work? Does it do what you want? Do you understand why it does that?
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Member
    Join Date
    Sep 2011
    Posts
    63
    My Mood
    Confused
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: Product of array values

    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.

  4. #4
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,159
    My Mood
    Hungover
    Thanks
    141
    Thanked 595 Times in 510 Posts

    Default Re: Product of array values

    Not exactly, but you could certainly write a method that performs a for loop and returns a value. Then you could put a call to that method inside the brackets.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  5. #5
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Product of array values

    Instead of doing +0, +1, +2,
    The reason OP is using constant array index increments is because of my suggestion to 'slide a window':
    Help with ArrayList ( Adding certain elements together)

    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.

  6. #6
    Member
    Join Date
    Sep 2011
    Posts
    63
    My Mood
    Confused
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: Product of array values

    If I was to evolve the solution to take advantage of the window idea, so it looked something like this:

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

    How would I go about filling the first index?

    PS. What does OP stand for?
    Last edited by tarkal; September 27th, 2011 at 03:25 PM.

  7. #7
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Product of array values

    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.

  8. #8
    Member
    Join Date
    Sep 2011
    Posts
    63
    My Mood
    Confused
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: Product of array values

    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?

  9. #9
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Product of array values

    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.

  10. #10
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Product of array values

    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.

  11. #11
    Member
    Join Date
    Sep 2011
    Posts
    63
    My Mood
    Confused
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: Product of array values

    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.

  12. #12
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Product of array values

    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.

  13. #13
    Member
    Join Date
    Sep 2011
    Posts
    63
    My Mood
    Confused
    Thanks
    7
    Thanked 0 Times in 0 Posts

    Default Re: Product of array values

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


  14. #14
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Product of array values

    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... :-)

Similar Threads

  1. calculate sum and product
    By swampfox in forum What's Wrong With My Code?
    Replies: 6
    Last Post: September 27th, 2011, 03:55 PM
  2. Problem with array values
    By Harry Blargle in forum Collections and Generics
    Replies: 5
    Last Post: September 17th, 2011, 04:05 PM
  3. The sum and product of a positive number between 1000 and 9999.
    By metaleddie13 in forum Member Introductions
    Replies: 1
    Last Post: September 15th, 2011, 04:39 AM
  4. need help inputting values into an array
    By pds8475 in forum What's Wrong With My Code?
    Replies: 3
    Last Post: January 22nd, 2011, 08:47 PM
  5. Substitution of Values in Array
    By nyeung in forum Collections and Generics
    Replies: 2
    Last Post: October 26th, 2009, 08:02 PM