Summer of Algorithm String Problem - JAVA

#1

https://hack.codingblocks.com/contests/c/452/1291
Please help me out with this problem. I don’t understand why there is a wrong-answer in submission, though the output when run matches the given test case.
I solved the question by lexicographically sorting the given numbers.
My submission is: (for reference)
import java.util.*;
//import java.math.BigInteger;
public class Main {
static Scanner scn = new Scanner(System.in);
public static void main(String args[]) {
int t = scn.nextInt();
for(int i=0;i<t;i++){
int n = scn.nextInt();
int[] arr = new int[n];
fillArray(arr);
printLargestValue(arr);
}
}
public static void printLargestValue(int[] arr){
String[] lexoOrder = new String[arr.length];
for(int i=0;i<lexoOrder.length;i++){
lexoOrder[i]=arr[i]+"";
}
bubbleSortString(lexoOrder);
String res="";
for(int i=0;i<lexoOrder.length;i++){
res =res+lexoOrder[i];
}
//BigInteger ans = new BigInteger(res);
System.out.print(res+"\t");
}
public static void bubbleSortString(String[] arr){
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j].compareTo(arr[j+1])<0){
String temp = arr[j];
arr[j]= arr[j+1];
arr[j+1]=temp;
}
}
}
}
public static void fillArray(int[] arr){
for(int i =0;i<arr.length;i++){
arr[i]=scn.nextInt();
}
}
}

#2

Your code gives WA for :
1
2
901 9

Your output : 9019
Expected output : 9901

#3

Thanks for your reply, would look into it. Basically solving it lexicographically using only .compareTo() function is not going to help.

#4

I actually wanted to confirm. Is it that we have to do it lexicographically using .compareTo() function and just put a check on the case that you pointed out
OR
Is there a trick completely different that I am missing on?
Please help me with that!

#5

There are several ways to solve a given problem. Let me tell you the simplest way to approach this problem :
The idea is to use sort() function. We’ll write the comparator function as per our needs. What the comparator function does is if the first parameter should come before the second it’ll return true(1) else false(0). So we’ll maintain a vector of strings and and for the comp() function, we’ll compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y). If XY is larger, then X should come before Y in output, else Y should come before. For example, let X and Y be 901 and 9. To compare X and Y, we compare 9019 and 9901. Since 9901 is greater than 9019, we put Y first.
Refer this for implementation.

1 Like
#6

Thanks for sharing important code with us. I also start to learn Java from JAVA training in Delhi
I hope whether I get an issue you can help me.