Largest Number using C++
Asked 11 months ago
0Comments
0 Views
The task is to arrange a list of integers(non-negative) in such a way that they form the largest possible number when concatenated. The result should be returned as a string due to its potentially large size.
Initial Approach :
- Convert all numbers to strings.
- Sort these strings in ascending order.
- Concatenate these strings in reverse order (to get descending order).
string largestNumber(vector<int> &nums) {
vector<string> snums;
for (auto n : nums) {
snums.push_back(to_string(n));
}
sort(snums.begin(), snums.end());
string ans = "";
for (int i = snums.size() - 1; i >= 0; i--) {
ans = ans + snums[i];
}
return ans;
}This approach fails for some cases. Let's take your example: nums = {3, 30}
- After converting to strings: ["3", "30"]
- After sorting: ["3", "30"] (unchanged, because "3" comes before "30" alphabetically)
- After reversing and concatenating: "303"
But the correct answer should be "330"!
Why It Fails:
The issue is that regular string sorting (lexicographical order) doesn't always give us the largest number. In this case, "30" should come before "3" to form the largest number, but alphabetically, "3" comes first.
The Solution:
Custom Comparator To fix this, we need to change how we compare these strings. Instead of using the default alphabetical order, we create a special way to compare them:
static bool mycomp(string a, string b) {
return a + b > b + a;
}What does this do?
- For any two strings a and b, it checks which order makes a bigger number: a followed by b, or b followed by a.
- If a+b is bigger, it means a should come first in our sorted list.
Now, let's see how this works for {3, 30}:
Convert to strings: ["3", "30"]
When sorting, it compares:
"3" + "30" = "330"
"30" + "3" = "303"
"330" is bigger, so "3" comes first
After sorting: ["3", "30"]
Concatenate: "330"
This gives us the correct answer!Final Code !
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// USING COMPARATOR !
// This function compares two strings to determine their order
static bool mycomp(string a, string b)
{
// Return true if a+b is greater than b+a
// This ensures the correct order for forming the largest number
return a+b > b+a;
}
// Function to form the largest number from a vector of integers
string largestNumber(vector<int> &nums)
{
// Convert integers to strings
vector<string> snums;
for (auto n : nums)
{
snums.push_back(to_string(n));
}
// Sort the strings using our custom comparator
sort(snums.begin(), snums.end(), mycomp);
// Concatenate the sorted strings
string ans = "";
for (auto str : snums)
{
ans += str;
}
// Handle the case where the result is all zeros
if (ans[0] == '0')
return "0";
return ans;
}
int main()
{
// Test case
vector<int> nums = {3, 30};
string result = largestNumber(nums);
// Print the result
cout << result << " ";
return 0;
}
Give it a try in LEETCODE
Share