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;
}
You can also try this code with Online C++ Compiler
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;
}
You can also try this code with Online C++ Compiler
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.!
24+ registered 
