CODEWITHSUNDEEP
javaalgorithmsortingselection-sort
Sk_Hssn
Sk_Hssn

Reputation: 45

Create an algorithm that arranges them in order to form the largest possible integer

I am struggling with this coding problem in Java. It has to be solved using an algorithm. It is supposed to give me the largest possible inter that can be formed with the numbers in the array: {10, 7, 76, 415}. I tried to solve it using selection sort. So far I have is this code below but it's giving me the wrong output. My code:

public class largestNumber { public static int largestNumber(int[] arr) {

    for (int i = 1; i < arr.length -1; i++) {
        for (int j = i +1; j < arr.length; j++) {
            String temp1 = Integer.toString(i) + Integer.toString(j);
            String temp2 = Integer.toString(j) + Integer.toString(i);
            
            if (Integer.parseInt(temp2) > Integer.parseInt(temp1)) {
                int swap = arr[i];
                arr[i] = arr[j];
                arr[j] = swap;
            }
        }

    
    }
    
    String ansNum = "";
    for (int i = 0; i < arr.length; i++) {
        ansNum += Integer.toString(arr[i]);
        
    }
    
    return Integer.parseInt(ansNum);

}
public static void main(String[] args) {   
    int [] arr = {10, 7, 76, 415};
    int output = largestNumber(arr);
    System.out.println(output); //Print out the number
}

}

The given output from this code is:10415767 But the right answer is: 77641510

Please give your feedback and thoughts.

Upvotes: 0

Views: 568

Answers (2)

Deepak
Deepak

Reputation: 1

public class largestNumber { 
  public static int largestNumber(int[] arr) {

    for (int i = 0; i < arr.length -1; i++) {
        for (int j = i +1; j < arr.length; j++) {
            String temp1 = Integer.toString(arr[i]) + Integer.toString(arr[j]);
            String temp2 = Integer.toString(arr[j]) + Integer.toString(arr[i]);//rectified
            
            if (Integer.parseInt(temp2) > Integer.parseInt(temp1)) {
                int swap = arr[i];
                arr[i] = arr[j];
                arr[j] = swap;
            }
        }

    
    }
    
    String ansNum = "";
    for (int i = 0; i < arr.length; i++) {
        ansNum += Integer.toString(arr[i]);
        
    }
    
    return Integer.parseInt(ansNum);

}
    public static void main(String[] args) {   
        int [] arr = {10, 7, 76, 415};
        int output = largestNumber(arr);
        System.out.println(output); //Print out the number
    }
}

Upvotes: 0

Shridhar R Kulkarni
Shridhar R Kulkarni

Reputation: 7063

Fix the bugs as shown below and it should work.

for (int i = 0; i < arr.length; i++) { //correction here
        for (int j = i +1; j < arr.length; j++) {
                String temp1 = Integer.toString(arr[i]) + Integer.toString(arr[j]); //correction here
                String temp2 = Integer.toString(arr[j]) + Integer.toString(arr[i]); //correction here

To write some elegant code, I would have used a comparator as shown below:

        String[] stringArr = new String[arr.length];
        for(int i = 0; i < arr.length; i++)
            stringArr[i] = String.valueOf(arr[i]);
    
        Comparator<String> comp = new Comparator<String>(){
            @Override
            public int compare(String str1, String str2){
                String s1 = str1 + str2;
                String s2 = str2 + str1;
                return s2.compareTo(s1);
            }
         };
        
        Arrays.sort(stringArr, comp);
    
        String ansNum = "";
        for(int i = 0; i < stringArr.length; i++) {
            ansNum += stringArr[i];
            
        }
        
        return Integer.parseInt(ansNum);

To talk about time complexity, the two for loops in your code makes this solution O(n^2) whereas with the use of sort it becomes O(nlog(n)) where n is the number of elements in the input array. So, not only the code becomes elegant with the use of comparator, in this case it becomes efficient too.

Upvotes: 0

Related Questions