{"id":3887,"date":"2021-11-18T14:53:41","date_gmt":"2021-11-18T09:23:41","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3887"},"modified":"2022-07-06T10:32:19","modified_gmt":"2022-07-06T05:02:19","slug":"arrange-numbers-to-form-biggest-number","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/arrange-numbers-to-form-biggest-number\/","title":{"rendered":"Arrange Given Numbers to Form Biggest Number"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach\">Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given an <strong>array of numbers<\/strong>, arrange the numbers in such a way that the number formed from their <strong>concatenation<\/strong> will be of the <strong>largest possible value<\/strong>.<\/p>\n\n\n\n<p id=\"-sample-test-cases--\"><strong>Sample Test Cases:<\/strong><\/p>\n\n\n\n<p>Input 1:<\/p>\n\n\n\n<p>s = [546, 54, 548, 60]\n\n\n\n<p>Output 1:<\/p>\n\n\n\n<p>6054854654<\/p>\n\n\n\n<p>Explanation 1:<\/p>\n\n\n\n<p>Among all the permutations of the array, the order <strong>[60, 548, 546, 54]<\/strong> gives the largest concatenated number possible.<\/p>\n\n\n\n<p>Input 2:<\/p>\n\n\n\n<p>s = [1, 34, 3, 98, 9, 76, 45, 4]\n\n\n\n<p>Output 2:<\/p>\n\n\n\n<p>998764543431<\/p>\n\n\n\n<p>Explanation 2:<\/p>\n\n\n\n<p>Among all the permutations of the array, the order <strong>[9, 98, 76, 45, 4, 34, 3, 1]<\/strong> gives the largest concatenated number possible.<\/p>\n\n\n\n<h2 id=\"approach\">Approach<\/h2>\n\n\n\n<p>The idea is to sort the numbers in descending order, and then just concatenate them. However, observe that just sorting in descending order won\u2019t give us our optimal answer.<\/p>\n\n\n\n<p>Take the example of <strong>431<\/strong> and <strong>50<\/strong>, our code will concatenate it in order <strong>43150<\/strong> but observe that <strong>50431<\/strong> gives us a better result. So, the idea comes that we need to implement a <strong>custom sorting algorithm<\/strong> that sorts our array in a manner that we can obtain our optimal answer by concatenating it.<\/p>\n\n\n\n<p id=\"how-to-sort-the-array\"><strong>How to Sort the Array?<\/strong><\/p>\n\n\n\n<p>To compare the numbers <strong>A<\/strong> and <strong>B<\/strong>, we can view both of them as strings, and make them of the same length by calculating <strong>(A + B)<\/strong> and <strong>(B + A)<\/strong>. Then we can just compare these 2 strings lexicographically, and sort them according to it.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"124\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"compare the numbers A and B\"  class=\"wp-image-4006 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/compare-the-numbers-A-and-B-1024x124.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/compare-the-numbers-A-and-B-1024x124.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/compare-the-numbers-A-and-B-300x36.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/compare-the-numbers-A-and-B-768x93.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/compare-the-numbers-A-and-B-380x46.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/compare-the-numbers-A-and-B-550x66.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/compare-the-numbers-A-and-B-800x97.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/compare-the-numbers-A-and-B-1160x140.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/compare-the-numbers-A-and-B.png 1200w\" ><\/figure>\n\n\n\n<p><strong>Code \/ Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">string largestNumber(vector &amp;lt; string &amp;gt; &amp;amp; a) {\n  sort(a.begin(), a.end(), [ &amp;amp; ](const string &amp;amp; x,\n    const string &amp;amp; y) {\n    string newX = x + y;\n    string newY = y + x;\n    return newY &amp;lt; newX;\n  });\n  string ans = \"\";\n  for (auto x: a) {\n    ans += x;\n  }\n  return ans;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static String largestNumber(Vector &amp;lt; String &amp;gt; a) {\n  Collections.sort(a, new Comparator &amp;lt; String &amp;gt; () {\n    public int compare(String first, String second) {\n      String newF = first + second;\n      String newS = second + first;\n      return newF.compareTo(newS) &amp;lt;= 0 ? 1 : -1;\n    }\n  });\n  String ans = \"\";\n  Iterator itr = a.iterator();\n  while (itr.hasNext()) {\n    ans += itr.next();\n  }\n  return ans;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">from functools import cmp_to_key\n\n\ndef largestNumber(s):\n    s = map(str, s)\n    key = cmp_to_key(lambda a, b: 1 if a + b &amp;gt;= b + a else -1)\n    res = \"\".join(sorted(s, key=key, reverse=True))\n    res = res.lstrip(\"0\")\n    return res if res else \"0\"<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n * log(n))<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n\n\n\n<p id=\"-practice-problem-\"><strong>Practice Problem:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/old\/problems\/largest-number\/\" target=\"_blank\" rel=\"noreferrer noopener\">Largest Number<\/a><\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>1. How can the implementation of this problem be made easier?<\/strong><\/p>\n\n\n\n<p>A. The implementation of this problem becomes easier when we work with the <strong>numbers as strings<\/strong>.<\/p>\n\n\n\n<p><strong>2. What is the custom sorting method used in this problem called?<\/strong><\/p>\n\n\n\n<p>A. Such custom sorting methods are usually called <strong>Comparators<\/strong>.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an array of numbers, arrange the numbers in such a way that the number formed&hellip;\n","protected":false},"author":5,"featured_media":4005,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[578],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3887"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3887"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3887\/revisions"}],"predecessor-version":[{"id":10275,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3887\/revisions\/10275"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4005"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3887"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3887"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3887"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}