No result illustrationNo result illustration

DevLoom

search

Lets Connect

chevron right
Menu
Home

Home

Community

Community

Blog Posts

Blog Posts

Programming

Programming

Tech Topics

Tech Topics

Explore

Explore

Find Jobs

Find Jobs

Tags

Tags

DevLoomPerfect Place for devs
    profile

    Jubair

    upvoteupvote

    0

    downvote

    0

    star

    Largest Number using C++

    clock icon

    Asked 11 months ago

    message

    0Comments

    eye

    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 :

    1. Convert all numbers to strings.
    2. Sort these strings in ascending order.
    3. 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}

    1. After converting to strings: ["3", "30"]
    2. After sorting: ["3", "30"] (unchanged, because "3" comes before "30" alphabetically)
    3. 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 

    LARGEST NUMBER

    LeetCode
    Strings
    Arrays
    medium

    Share

    Write your comment here !

    0 Responses