## Approach 1

As we have seen previously, the simple sorting technique is not working. We could somehow customise the sorting algorithm.

In the simple sorting algorithm, instead of using the default comparison, we would use our customised **comparator function** for deciding which element to put where.

The algorithm is as follows:

- Create a compare function which takes two elements.

- Concatenate the two elements of the array as given below,

If two elements are a and b.

First, concatenate a and b to form **ab**, then b and a to form** ba**.

- Then compare these numbers(
**ab** and **ba**).

- If
**ab is greater than ba, then return true otherwise return false.**

### Implementation

The implementation of the above approach is shown below.

#### Code1(Considering Given Array Elements are string)

### C++

`#include<bits/stdc++.h>`

using namespace std;

bool comp(const string &a, const string &b) {

string temp1 = a + b;

string temp2 = b + a;

// true if ab > ba

// false otherwise

return temp1 > temp2;

}

int main() {

vector<string> elements;

// initiaized vector

elements.push_back("12");

elements.push_back("96");

elements.push_back("871");

// sort function with compare function

sort(elements.begin() , elements.end() , comp);

cout << "The biggest number is: ";

for(int i = 0; i < elements.size() ; i++) {

cout << elements[i];

}

return 0;

}

#### Output

In the above approach, we considered the array elements to be strings.

Now,** letâ€™s consider the array elements to be an integer**.

#### Code2(Considering given array elements are integers)

### C++

`#include<bits/stdc++.h>`

using namespace std;

bool comp(const int &a , const int &b) {

int aa = a , bb = b;

int rev_a = 0, rev_b = 0;

// reverse a and b and store in rev_a and rev_b

while(aa) {

rev_a = rev_a * 10 + aa % 10;

aa /= 10;

}

while(bb) {

rev_b = rev_b * 10 + bb % 10;

bb /= 10;

}

long long int ab = a , ba = b;

// forming ab

while(rev_b) {

ab = ab * 10 + rev_b % 10;

rev_b /= 10;

}

//forming ba

while(rev_a) {

ba = ba * 10 + rev_a % 10;

rev_a /= 10;

}

return ab > ba;

}

int main() {

vector<int> elements;

elements.push_back(12);

elements.push_back(96);

elements.push_back(871);

// size of the vector

int n = elements.size();

sort(elements.begin() , elements.end() , comp);

cout << "The largest Number is: ";

for(int i = 0; i < elements.size() ; i++) {

cout << elements[i];

}

return 0;

}

#### Output

In the above approach, we used the integer as an array element. **The limitation of this approach is that if the numbers are very big, this method wonâ€™t work as it canâ€™t store numbers beyond 10^18**. But if we use the element of the array as a string, then there would not be such kind of limitations.

### Complexity Analysis

**Time Complexity: O(nlogn)**

**Space Complexity: O(1)**

**You can also read about - **Strong number in c

**Approach 2: (Only in Python)**

This approach tackles the problem of forming the largest number possible by rearranging the digits from individual numbers in an array. Here's the solution explained with Python implementation and complexity analysis:

**1. Custom Comparison Function: **The key lies in creating a custom comparison function to sort the array elements. This function prioritizes numbers that would lead to a larger number after concatenation.

```
def compare(a, b):
"""
Compares two strings (numbers) for custom sorting.
Returns True if a should come before b in the sorted list.
"""
ab = str(a) + str(b) # Concatenate a and b
ba = str(b) + str(a) # Concatenate b and a
return int(ab) > int(ba) # Return True if ab is larger
```

**2. Sorting with Custom Comparison: **We then use the sorted function with our custom compare function to sort the array.

```
def largest_number(nums):
"""
Returns the largest number formed by rearranging digits in the array.
"""
sorted_nums = sorted(nums, key=lambda x: compare(x, x)) # Sort using compare
# Handle leading zeros (special case)
if sorted_nums[0] == 0 and len(set(sorted_nums)) == 1:
return "0"
return "".join(map(str, sorted_nums)) # Join sorted numbers as string
```

**Explanation**

- The compare function checks which combination (a appended to b or b appended to a) results in a larger number.
- Sorting the array with this comparison ensures elements that contribute to a larger overall number come first.
- Finally, joining the sorted numbers as a string forms the largest possible number.

**Complexity Analysis**

- Time Complexity: O(n log n). This is due to the sorting using sorted function, which typically uses a comparison-based sorting algorithm like merge sort or quicksort.
- Space Complexity: O(1). The custom comparison function and string manipulations do not introduce significant additional space requirements compared to the input array size.

## Frequently Asked Questions

**How do you find the largest number formed from an array?**

Sort elements with a custom logic to prioritize creating a bigger number after concatenation, not numeric value.

**How do you find a number in an array?**

Linear search (iterate through the array checking if each element matches the target number).

**What are the examples of comparison-based sorting and non-comparison based sorting algorithms?**

Comparison based sorting: **mergesort, quicksort, bubble sort, heap sort, insertion sort, selection sort**. Non-comparison based sorting:** radix sort, bucket sort, count sort.**

**What do you mean by â€śconstant extra spaceâ€ť in a problem?**

The space(memory ) you have taken to solve the problem doesnâ€™t depend on the input variable.

## Conclusion

We hope that this blog has helped you enhance your knowledge regarding **Arrange Given Numbers to Form the Biggest Number**. If you would like to learn more, check out our articles on__ Find the Minimum Element in a Rotated Sorted Array__, __Multiple Left Rotation in an Array in O(1)__, __Next Greater and Smaller Element for Every Element in an Array__, __Understanding Insertion Sort__,__ Understanding Quick Sort__, __Merge Sort__** **, Book Allocation Problem. Do upvote our blog to help other ninjas grow.

Head over to our practice platform __Code360__ to practice top problems, attempt __mock tests__, read __interview experiences__,__ interview bundle__, follow __guided paths__ for placement preparations and much more.!