Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
2.2.
Solution
3.
Approach 1
3.1.
Implementation
3.1.1.
Code1(Considering Given Array Elements are string)
3.2.
C++
3.2.1.
Output
3.2.2.
Code2(Considering given array elements are integers)
3.3.
C++
3.3.1.
Output
3.4.
Complexity Analysis
4.
Approach 2: (Only in Python)
4.1.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
How do you find the largest number formed from an array?
5.2.
How do you find a number in an array?
5.3.
What are the examples of comparison-based sorting and non-comparison based sorting algorithms?
5.4.
What do you mean by “constant extra space” in a problem?
6.
Conclusion
Last Updated: Jun 2, 2024
Easy

Largest Number Formed From an Array

Author Aniket Majhi
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Numbers might seem straightforward, but what if creating the biggest number wasn't just about adding them up? In this blog post, we'll delve into a fascinating problem: constructing the largest possible number by rearranging the digits from individual numbers in an array.

Largest Number Formed From an Array

Problem Statement

You are given an array of numbers. You need to arrange them in such a way that they form the biggest number.

Example

Let’s understand the above problem statement by giving an example,

Input

{12, 96, 871}

Output

9687112

Explanation

All possible arrangements of elements of the given array are,

{12, 96, 871} = 1296871

{12, 871, 96} = 1287196

{96, 12, 871} = 9612871

{96, 871, 12} = 9687112

{871, 12, 96} = 8711296

{871, 96, 12} = 8719612
 

Among all possible arrangements of numbers, we found the biggest number as 9687112 by arranging the numbers in the array as {96, 871, 12}. So the answer is 9687112.

Also Read - Selection Sort in C

Solution

You might be thinking about why not sorting the array in descending order and then concatenating all the elements, right?

But this simple sort wouldn’t work all the time. Consider the case where the array elements are {103, 87, 9}. If we follow the simple sorting technique, then the result would be 103879. But here, the answer would be 987103.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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++

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++

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 ArrayMultiple Left Rotation in an Array in O(1)Next Greater and Smaller Element for Every Element in an ArrayUnderstanding Insertion Sort, Understanding Quick SortMerge 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.!

Previous article
Making elements of two arrays identical with minimum increment/decrement
Next article
Three-way Partitioning of an Array Around a Given Range
Live masterclass