- 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
all forums

this forum made possible by our volunteer staff, including ...

Marshals:

- Campbell Ritchie
- Bear Bibeault
- Devaka Cooray
- Liutauras Vilda
- Jeanne Boyarsky

Sheriffs:

- Knute Snortum
- Junilu Lacar
- paul wheaton

Saloon Keepers:

- Ganesh Patekar
- Frits Walraven
- Tim Moores
- Ron McLeod
- Carey Brown

Bartenders:

- Stephan van Hulst
- salvin francis
- Tim Holloway

posted 1 year ago

- 1

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!

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!

OCAJP 7

posted 1 year ago

Here's two examples how to convert your strings to an array / list of ints:

Output:

Output:

posted 1 year ago

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.?

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.?

posted 1 year ago

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.

You can use a Stream to calculate the transverse product of digits.

posted 1 year ago

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.

(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.

OCAJP 7

posted 1 year ago

hi Dana,

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

Can you show us your (complicated) method?

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

Can you show us your (complicated) method?

posted 1 year ago

I think this is related to the OP's other post

https://coderanch.com/t/678032/java/Type-variable-int-double

https://coderanch.com/t/678032/java/Type-variable-int-double

Campbell Ritchie

Marshal

Posts: 61777

193

posted 1 year ago

I must remember reduce(...). Some very raw beef going that way, as well as this thread going elsewhere. This is closely related to DU's other thread, 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.

That may mean the posts will be in the wrong order.

Campbell Ritchie

Marshal

Posts: 61777

193

posted 1 year ago

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.

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.

OCAJP 7

posted 1 year ago

The worst case scenario would be 13 places of the digit 9, or 9^13, or 2.5 trillion. You'd need a long.

posted 1 year ago

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

posted 1 year ago

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.

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.

posted 1 year ago

Why the compiler didn't say anything?

OCAJP 7

posted 1 year ago

if I have

Outputs are:

2541865828329

-754810903

Outputs are:

2541865828329

-754810903

OCAJP 7

Campbell Ritchie

Marshal

Posts: 61777

193

posted 1 year ago

Your outputs follow the rules of integer arithmetic. You have suffered an overflow error. Haven't you been taught about numerical overflow?

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.Dana Ucaed wrote:Why the compiler didn't say anything?

Your outputs follow the rules of integer arithmetic. You have suffered an overflow error. Haven't you been taught about numerical overflow?

posted 1 year ago

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

All things are lawful, but not all things are profitable.

posted 1 year ago

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.

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.

OCAJP 7

Campbell Ritchie

Marshal

Posts: 61777

193

posted 1 year ago

Compare that number with the limits on the` int `type, and I think you should 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.

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.Dana Ucaed wrote:. . . Output is:2091059712 . . . . why don't appear overflow when I used int as type of variable. . . .

Compare that number with the limits on the

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.

posted 1 year ago

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??

The last post of Campbell didn't help me.

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

OCAJP 7

Campbell Ritchie

Marshal

Posts: 61777

193

posted 1 year ago

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.

posted 1 year ago

I have 2 posts because there are different implementations.

Original problem was the same but solutions are different.

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.

OCAJP 7

posted 1 year ago

If the overflow is not the reason , what is the reason?

OCAJP 7

posted 1 year ago

Change product and maximumProduct to type long and it works.

posted 1 year ago

Multiple overflows.

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

Multiple overflows.

Piet Souris

Master Rancher

Posts: 3004

105

posted 1 year ago

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 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: 61777

193

posted 1 year ago

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.

- 1

Two 9s and a 6: there's the 3⁵ if we divide by 2.Piet Souris wrote:. . . 9781797784617 . . .

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

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.

posted 1 year ago

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.

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: 61777

193

posted 1 year ago

Aaaaaaaaaaaaaaaah! That is why it has those nice lots and lots of factors.Carey Brown wrote:. . . That is the largest product that your program could find that DIDN'T OVERFLOW. . . .

posted 1 year ago

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

What is the truth?

Campbell Ritchie wrote:

Two 9s and a 6: there's the 3⁵ if we divide by 2.Piet Souris wrote:. . . 9781797784617 . . .

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 anintwithout 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?

OCAJP 7

posted 1 year ago

Probably in JLS said something about product a n numbers.

OCAJP 7

posted 1 year ago

This exercise is for learning.

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.

OCAJP 7

posted 1 year ago

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

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.

All things are lawful, but not all things are profitable.

posted 1 year ago

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.

posted 1 year ago

- 1

If you're going to use streams, you should calculate the product using streams as well:

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

posted 1 year ago

Thanks Rob. I was struggling a bit with that and I wasn't aware of skip and limit.

posted 1 year ago

You're welcome.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

posted 1 year ago

I did some benchmarking on three different approaches to product(). Running each 100,000 times.

Campbell Ritchie

Marshal

Posts: 61777

193

posted 1 year ago

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.

It is sorta covered in the JavaRanch Style Guide. |

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!