Form Biggest Number

#1

I understood the approach to the problem but I am not able to understand how to code a modified sort. I only know the sorting algorithms that have a time complexity of O(n^2), but these are not suitable to solve the problem. So what should I do?

#2

you need to implement a custom comparator function that receives two strings a and b, then finds str1 = a + b and str2 = b + a then if str1 > str2, then returns a should be first, else b should be first. You can read about comparator function here. Pretty easy to implement. https://www.geeksforgeeks.org/comparator-interface-java/

#3

I have not studied collections and class till now, so not able to understand how it is working. So can you explain in a more simpler way?

#4

Write bubble sort and the place where you compare the two elements just implement the thing I told you. Forget about comparators. Just check there if a+b <b+a then place a before b

#5

I have implemented as you said by using bubble sort and if a+b <b+a then place a before b, but I am getting wrong error and run error. Can you tell where is the mistake?

#6

Please post your code as well.

#7
#8

@anugrahrastogi
code is fine just a change
if(Long.parseLong(ab) < Long.parseLong(ba)) instead of Integer.parseInt(ab) < Integer.parseInt(ba)
and add new line each and every Steps
correct code
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
	
	Scanner s = new Scanner(System.in);
	
	int t = s.nextInt();
	
	while(t-- > 0) {
		
		int n = s.nextInt();
		String[] arr = new String[n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = s.next();
		}
		
		for(int i = 0; i < n-1; i++) {
			for(int j = 0; j < n-i-1; j++) {
				
				String ab = arr[j] + arr[j+1];
				String ba = arr[j+1] + arr[j];
				
				if(Long.parseLong(ab) < Long.parseLong(ba)) {
					String temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		
		for(int i = 0; i < n; i++)
			System.out.print(arr[i]);
		System.out.println();	
	}
	
	s.close();

}

}

#9

My code has a complexity of O(n^2) and the optimized code would have a complexity of O(n log n) so how did all the test case pass?

#10

you don’t know comparator in java
Leave it for now

#11

But my question is how was a code with time complexity O(n^2) got excepted?

#12

Because the test cases aren’t that strict over here. Anyways, this was meant for you to learn modifications to sorting techniques