• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Store String and array of digits

 
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello Ranchers,

I have 3 strings. I want a way to store for each string a collection of digits.

Or I want for each array to store the products of digits.

731671765313
306249192251
196744265747

I think of a Map<String, List<Integer>> products = new HashMap<>();

But I don't know how to write the code so  for each string I must store a collection of digits.


Thanks in advance!

Best regards!
 
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's two examples how to convert your strings to an array / list of ints:
   


Output:

 
Bartender
Posts: 732
10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You need o give a better explanation of what you want to do.
For example, given the three lines you show, what collection of digits do you want?

And as for "for each array to store the products of digits.", that is even more unclear.
How many products do you want for each string?
Do you want one (presumably the product of all the single digits in the line)?
Or perhaps the produce of the first and second, and the product of the second and third, etc.?
Or the product of the first 3, and the second three, etc.?
 
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am afraid I don't like using String#split to split that array into individual Strings. The method with the Stream looks unnecessarily convoluted to me. There is a method in all Strings which converts them to arrays. Why can't you print the array with Arrays#toString?
You can use a Stream to calculate the transverse product of digits.
 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So, I want to store in a structure:

(731671765313, [7, 3,2,1,6,7,1,7,6,5,3,1,3]
306249192251, [3,0,6,2,4,9,1,9,2,2,5,1]
196744265747, [1,9,6,7,4,4,2,6,5,7,4.7] )

or

(731671765313, 7*3*1*6*7*1*7*6*5*3*1*3
306249192251, 3*0*6*2*4*9*1*9*2*2*5*1
196744265747, 1*9*6*7*4*4*2*6*5*7*4*7 )

My solution is complicated for what must be done.

Output will be maximum of product.
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Dana,

for once we seem to be allowed to give ready made code, so here goes:

Can you show us your (complicated) method?
 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I must remember reduce(...). Some very raw beef going that way, as well as this th‍read going elsewhere. This is closely related to DU's other t‍hread, so I shall merge the two. If you don't know that DU is multiplying thirteen digits, you don't know why there is any reason to map to a long.

That may mean the posts will be in the wrong order.
 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I merged your stuff with the following thread. I hope that is okay by you.
 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello Ranchers,

It's about problem 8 of Euler project:

Largest product in a series
Problem 8
Published on Friday, 11th January 2002, 08:00 pm; Solved by 255293; Difficulty rating: 5%
The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?



Output is: 2.3514624E10


This is correct version.

Below will ne the wrong version: the only difference will be the type of variables.

My question is: how is avoid an such mistake?




Output is:2091059712


I think the output should be negative number, but it's not.


 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The worst case scenario would be 13 places of the digit 9, or 9^13, or 2.5 trillion. You'd need a long.
 
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You need a long definitely to achieve a solution. (long (-2)^63 to ((2^63)-1) range) 64 bits.
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rajith Pemabandu wrote:You need a long definitely to achieve a solution. (long (-2)^63 to ((2^63)-1) range) 64 bits.


Misplaced parens. Should be (-(2^63))
Raising (-2) to an odd power results in a negative number, but raising it to an even power would have resulted in a positive value.
(-(2^63)) will always be negative, even if you change 63 to 62.
 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why the compiler didn't say anything?

 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
if I have


Outputs are:

2541865828329
-754810903

 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dana Ucaed wrote:Why the compiler didn't say anything?

Because the compiler is designed to look for breaches of the rules of syntax. It cannot be expected to look for logic errors. That is what programmers are there for.

Your outputs follow the rules of integer arithmetic. You have suffered an overflow error. Haven't you been taught about numerical overflow?
 
Sheriff
Posts: 7125
184
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dana Ucaed wrote:if I have


Outputs are:

2541865828329
-754810903


It may seem like this output is "wrong" or an error, but like Campbell said, it's numeric overflow.  The compiler won't complain about it.

Numeric overflow happens because of the way integers are represented in bits.  If you have a signed integer (one that can become negative) you need a "place" to hold these numbers.  With bits you just have 0 and 1 to work with, no minus sign.  So the decision was made to use "two's complement" to hold negatives.  Two's complement says to invert the bits and add one to the result.  It's probably easier to show an example.  Assume we have eight bits (a byte).  Then the number one looks like this:  Two's complement first says to invert the bits: then add one With a byte, you can represent the numbers 127 to -128 this way.  But notice how the representation for -1 looks like the number 256.  If the byte is unsigned, this is the case.  But with a signed byte, the numeric progression goes like this:

This is why you get negative numbers if a signed integer overflows.
 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I don't explain how is obtained the first value when I declared int as type of variable:
Output is:2091059712 .

My question is : why don't appear overflow when I used int as type of variable.

Maybe I don't said what you want clear.

Thanks a lot for your time.


 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dana Ucaed wrote:. . . Output is:2091059712 . . . . why don't appear overflow when I used int as type of variable. . . .

I presume that is the transverse product of consecutive digits, rather than the String whose digits you want to multiply. Otherwise the transverse product would be 0.
Compare that number with the limits on the int type, and I think you shou‍ld be able to see the explanation. You happened to be lucky with that part of the text.
And I have just seen a shortcut which you can use to reduce the amount of calculation you will have to do on Project Euler.
 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I know limits of datatype int.

The last post of Campbell didn't help me.

Can someone say me the reason for which Output is:2091059712??



 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
2091059712's prime factors are 2⁹ × 3⁵ × 7⁵, which suggests that you have 7s, 3/6/9s and 2/4/8s in the text you are multiplying, and no 5/0s. Five 7s, but I can't tell how many of the other digits. It is very unlikely that you got that number from an overflow. Please show us the input which produced that output.
 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:2091059712's prime factors are 2⁹ × 3⁵ × 7⁵, which suggests that you have 7s, 3/6/9s and 2/4/8s in the text you are multiplying, and no 5/0s. Five 7s, but I can't tell how many of the other digits. It is very unlikely that you got that number from an overflow. Please show us the input which produced that output.






I have 2 posts because there are different implementations.

Original problem was the same but solutions are different.

 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If the overflow is not the reason , what is the reason?



 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Change product and maximumProduct to type long and it works.
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dana Ucaed wrote:If the overflow is not the reason , what is the reason?


Multiple overflows.
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:2091059712's prime factors are 2⁹ × 3⁵ × 7⁵, which suggests that you have 7s, 3/6/9s and 2/4/8s in the text you are multiplying, and no 5/0s. Five 7s, but I can't tell how many of the other digits. It is very unlikely that you got that number from an overflow. Please show us the input which produced that output.


9781797784617

(in the code I gave, use this:


@Dana,

with Project Euler, when brute force is a viable solution (by far not always applicable), it is always nice to look out for some optimizations. For instance, say:

S0 = d1 * d2 * d3 * ... * d13
S1 = d2 * d3 * d4 * ... * d13 * d14

can you write: S1 = S0 * alpha? And thus: what is alpha? And what if alpha < 1? Or > 1? And what has this to do with the excersize?
 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:. . . 9781797784617 . . .

Two 9s and a 6: there's the 3⁵ if we divide by 2.
Five 7s: There's the 7⁵
Two 8s, a 4 and a 6: if we divide that by 3 we get 2⁹
Spot on It just so happens that this number will fit into the limits of an int without overflow errors.
Notice you have two 1s, which count as a unit for multiplication. Remembering what the products of other digits would be, work out what would be an annihilator. When you find that annihilator, you can move on to the next thirteen characters following it. I think PS is hinting about the same thing.
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dana Ucaed wrote:I know limits of datatype int.
Can someone say me the reason for which Output is:2091059712??


That is the largest product that your program could find that DIDN'T OVERFLOW. Other products (including the correct answer) did overflow and ended up being negative numbers which were less than maximumProduct.
 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:. . . That is the largest product that your program could find that DIDN'T OVERFLOW. . . .

Aaaaaaaaaaaaaaaah! That is why it has those nice lots and lots of factors.
 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Piet Souris wrote:. . . 9781797784617 . . .

Two 9s and a 6: there's the 3⁵ if we divide by 2.
Five 7s: There's the 7⁵
Two 8s, a 4 and a 6: if we divide that by 3 we get 2⁹
Spot on It just so happens that this number will fit into the limits of an int without overflow errors.
Notice you have two 1s, which count as a unit for multiplication. Remembering what the products of other digits would be, work out what would be an annihilator. When you find that annihilator, you can move on to the next thirteen characters following it. I think PS is hinting about the same thing.



Carey Brown said it is overflow, but Campbell said it's not overflow.

What is the truth?

 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Probably in JLS said something about product a n numbers.

 
Dana Ucaed
Ranch Hand
Posts: 460
6
Netbeans IDE Oracle Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:

Campbell Ritchie wrote:2091059712's prime factors are 2⁹ × 3⁵ × 7⁵, which suggests that you have 7s, 3/6/9s and 2/4/8s in the text you are multiplying, and no 5/0s. Five 7s, but I can't tell how many of the other digits. It is very unlikely that you got that number from an overflow. Please show us the input which produced that output.


9781797784617

(in the code I gave, use this:


This code is for Java 8?
I used Java 7.
@Dana,

with Project Euler, when brute force is a viable solution (by far not always applicable), it is always nice to look out for some optimizations. For instance, say:

S0 = d1 * d2 * d3 * ... * d13
S1 = d2 * d3 * d4 * ... * d13 * d14

can you write: S1 = S0 * alpha? And thus: what is alpha? And what if alpha < 1? Or > 1? And what has this to do with the excersize?



This exercise is for learning.

 
Knute Snortum
Sheriff
Posts: 7125
184
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dana Ucaed wrote:
Carey Brown said it is overflow, but Campbell said it's not overflow.

What is the truth?


They're both right, but Carey said it more clearly:

That is the largest product that your program could find that DIDN'T OVERFLOW. Other products (including the correct answer) did overflow and ended up being negative numbers which were less than maximumProduct.

 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm still learning Java 8 so I thought I'd give this problem a try. Let me know if you see a better way of doing this.
 
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you're going to use streams, you should calculate the product using streams as well:
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Rob. I was struggling a bit with that and I wasn't aware of skip and limit.
 
Rob Spoor
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You're welcome.
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I did some benchmarking on three different approaches to product(). Running each 100,000 times.

 
Campbell Ritchie
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Presumably it would make no significant difference to the performance of your first method if you passed an int[] instead of the long[]. Probably no difference to the other two, either.
 
reply
    Bookmark Topic Watch Topic
  • New Topic