I'm trying a problem from sphere's online judge where I need to find a palindrome for a integer of up to a million digits, I thought about using java's functions for reversing strings, but would they allow for a string to be this long?
+2
A:
I believe they can be up to 2^31-1 characters, as they are held by an internal array, and arrays are indexed by integers in Java.
aperkins
2009-07-24 20:26:55
The internal implementation is irrelevant - there's no reason why the character data couldn't be stored in an array of longs, for instance. The problem is the interface uses ints for length. `getBytes` and similar may have problems if you try for a very large string.
Tom Hawtin - tackline
2009-07-24 20:45:59
That is true - I was implying that fact. My bad.
aperkins
2009-07-24 20:49:53
+10
A:
You should be able to get a String of length Integer.MAX_VALUE (always 2147483647 (2^31 - 1) by the Java specification, the maximum size of an array, which the String class uses for internal storage) or half your maximum heap size (since each character is two bytes), whichever is smaller.
Bill the Lizard
2009-07-24 20:27:36
... or your maximum heap size divided by 2 ... since character is 2 bytes
ChssPly76
2009-07-24 20:29:37
how do I find out the maximum heap size? Also, I don't know which java virtual machine the judge is using to test my problem is Integer.MAX_VALUE part of the spec of JVM dependant?
omgzor
2009-07-24 20:40:43
Integer.MAX_VALUE is _always_ 2147483647 (2^31 - 1), that's part of the Java Specification.
cd1
2009-07-24 20:45:10
Assuming a 64-bit JVM, since you'd need 8GB of virtual memory to store a string of that length.
Robert Fraser
2009-07-24 20:59:33
@dmindreader: Integer.MAX_VALUE is JVM *independent*, so you can always guarantee it will be the same. @CD1: Thanks for clarifying that while I was AFK, I added it to my answer. :)
Bill the Lizard
2009-07-24 23:32:29
Actually you want to divide your memory by 4-6 as you need a StringBuilder or the like to build your String i.e. there must be two copies in memory at some point. If your StringBuilder's capacity is just right, divide by 4, but if its not divide by 6 is safer.
Peter Lawrey
2009-07-25 06:53:30
@Peter: I don't follow you. Why do you say "there must be two copies in memory at some point"? Is this due to some limitation of the JVM, or are you talking about an implementation of the palindrome problem that dmindreader is trying to solve?
Bill the Lizard
2009-07-25 12:56:56
A:
Integer.MAX_VALUE is max size of string + depends of your memory size but the Problem on sphere's online judge you don't have to use those functions
Mite Mitreski
2009-07-24 20:29:28
+1
A:
Have you considered using BigDecimal instead of String to hold your numbers?
Thorbjørn Ravn Andersen
2009-07-24 21:58:27
It depends on what the application is going to do with the numbers. If it is going to just do textual things like finding palindromes, counting (decimal) digits, then a String is better. If it is going to be doing arithmetic, a BigDecimal (or BigInteger) is better.
Stephen C
2009-07-25 00:54:35
The problem is "For each K, output the smallest palindrome larger than K." (where K is the number given). It would be trivially simple to output the first palindrome smaller than K. You require arithmetic to find one larger than K. Example: Find the next palindrome larger than 999999999999, or the next palindrome larger than 12922.
Thorbjørn Ravn Andersen
2009-07-25 06:48:18