Thanks so much for your explanation.
I had update the code to use bigint but it's still have runtime exception.
Can y plz help get it working ?
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
public class Solution {
private static final char[] ALPHAPET =
"abcdefghijklmnopqrstuvwxyz".toUpperCase().toCharArray();
public static void main(String[] args) {
try (Scanner scanner = new Scanner(new BufferedReader(new
InputStreamReader(System.in)))) {
int testCount = scanner.nextInt();
for (int testNumber = 1; testNumber <= testCount; testNumber++)
{
BigInteger maxPrime = scanner.nextBigInteger();
int seqLength = scanner.nextInt();
BigInteger[] seq = new BigInteger[seqLength];
for (int i = 0; i < seqLength; i++) {
seq[i] = scanner.nextBigInteger();
}
String result = solve(maxPrime, seq);
System.out.println("Case #" + testNumber + ": " + result);
}
}
}
static String solve(BigInteger maxPrime, BigInteger[] seq) {
HashSet primes = new HashSet();
BigInteger[] valuesExpanded= new BigInteger[seq.length + 1];
BigInteger commonBigInt = seq[1].gcd(seq[0]);
BigInteger number1 = seq[0].divide(commonBigInt);
// BigInteger common = commonBigInt;
primes.add(number1);
primes.add(commonBigInt);
valuesExpanded[0] = number1;
valuesExpanded[1] = commonBigInt;
for (int i = 1; i < seq.length; i++) {
valuesExpanded[i+1] = seq[i].divide(commonBigInt);
commonBigInt = valuesExpanded[i+1];
primes.add(commonBigInt);
}
BigInteger[] sortedPrimes = new BigInteger[primes.size()];
primes.toArray(sortedPrimes);
Arrays.sort(sortedPrimes);
Map<BigInteger, Character> dictionary = new HashMap<>();
for (int i = 0; i < sortedPrimes.length; i++) {
dictionary.put(sortedPrimes[i], ALPHAPET[i]);
}
char[] decoded = new char[valuesExpanded.length];
for (int i = 0; i < valuesExpanded.length; i++) {
decoded[i] = dictionary.get(valuesExpanded[i]);
}
return String.valueOf(decoded);
}
}
On Monday, March 23, 2020 at 4:20:17 PM UTC+2, Bartholomew Furrow wrote:
>
> int maxPrime = scanner.nextInt(); // not working for the large dataset
>
> The reason it isn't working is because when you ask for scanner.nextInt(),
> you're saying "Java, please take the next chunk of text, interpret it as a
> number, and store that number in the 32-bit 'int' type."
>
> The 32-bit 'int' type can handle numbers between -2^31 and 2^31 - 1, which
> is about -2 billion to 2 billion. It can't handle hundred-digit numbers
> like the ones in this problem.
> For a lot of problems, you can make things better by using the 'long' type
> instead of the 'int' type. That can handle numbers between -2^63 and
> 2^63-1, which is about -9*10^18 to 9*10^18. Still not enough for the big
> numbers in this problem.
>
> For this problem, you want Java's BigInteger class.
> BigInteger maxPrime = scanner.nextBigInteger();
>
> BigInteger can handle essentially arbitrary numbers (It probably couldn't
> handle a number whose decimal representation can't fit in RAM, but that
> isn't your problem here). You'll have to look up the API to see how to use
> it.
>
> Good luck!
> Bartholomew
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/e1bcd20e-0dfa-4dec-89b9-503bb3f218b6%40googlegroups.com.
