Assume we are given an array of non-negative integers, and we need to arrange the numbers in such a way that they form the largest possible number.
Sample input | Output |
[10, 7, 9, 2, 3] | 973210 |
[4, 6, 8, 2, 3] | 86432 |
For this purpose, we need to write a function findMaxNum
that takes an integer array arr
and its size n
as input.
int findMaxNum(int arr[], int n);
This function should return the largest number that can be formed from the given array as an integer.
In this code, we aim to find the largest possible number that can be formed by concatenating the given array of numbers. The code utilizes a custom comparison function and sorting algorithm to arrange the numbers to maximize the resulting value. Let's take a look at the implementation.
#include <iostream>#include <algorithm>#include <string>using namespace std;bool compareNumbers(int a, int b){string num1 = to_string(a);string num2 = to_string(b);return (num1 + num2) > (num2 + num1);}int findMaxNum(int arr[], int n){sort(arr, arr + n, compareNumbers);string largestNumStr = "";for (int i = 0; i < n; i++){largestNumStr += to_string(arr[i]);}return stoi(largestNumStr);}int main(){int arr[] = {10, 7, 9, 2, 3};int n = sizeof(arr) / sizeof(arr[0]);int largestNumber = findMaxNum(arr, n);cout << "Largest Number: " << largestNumber << endl;return 0;}
Now, let's take a closer look at the C++ code and understand its workings in depth.
Lines 7-12: compareNumbers
function takes two integers as input arguments and compares them by converting them to strings and concatenating them.
Lines 9-10: Converts the integer a
and integer b
to a string using the to_string
function from the string library.
Line 11: Compares the concatenation of num1
and num2
with the concatenation of num2
and num1
and returns true
if the first concatenation is greater than the second concatenation, and false
otherwise.
Line 15: findMaxNum
takes an array of integers arr
and its size n
as input.
Line 17: Sorts the array arr
in descending order using the compareNumbers
custom comparison function.
Line 19: Initializes an empty string named largestNumStr
.
Line 22: This line converts each element of the array to a string and appends it to the largestNumStr
string.
Line 25: This line converts the largestNumStr
string to an integer using the stoi
function and returns it.