• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Generate largest number arranging a no. of given non negative integer numbers

January 16, 2018 by Dhaval Dave

Problem : Generate largest number –

Given a list of non negative integers, arrange them in such a manner that they form the largest number possible. The result is going to be very large, hence return the result in the form of a string.
Input:
The first line of each test case contains the size of the array(N), and the second line has the elements of the array.
Output:
Constraints : 1 ≤ N ≤ 100   and   0 ≤ A[i] ≤ 1000
Example:

Input: Output:
A) 3
3 327 94
A) 943327
B) 5
48 728 156 91
B) 9172848156

Solution :
Logic :

1. User entered numbers are kept stored in an array.
2. One function returns left most digit of array elements.
3. Left most digit of numbers are compared.

A) if left most digits of an array element is less than that of next element, swapping occurs,number with grater left most digit gets placed in array before the number with lesser left most digit.
B) if left most digits of an array element is grater than that of next element, both elements remain in their place as earlier.
C) if left most digit of one element is same to that of next element, two different numbers are formed by combining two elements one after another & reverse ,then these two numbers are compared .Now two array elements are sorted according to grater number formed by two elements. Suppose 5 & 578 are two number to be sorted. Two numbers formed combining these two elements are 5578 & 5785.Now 5785 is larger than 5578 .So 578 is stored in array before 5 .

4. Entered numbers are arranged in proper desired order & remain stored in array consecutively.
5. Then largest number will be printed by printing all elements of that array without any space.
Code :

#include "iostream";
using namespace std;
int dig1_max(int);
void num_max(int * , int * );
main() {
    int n, temp, * arr, a, b;
    cout << "Enter number of non-negative numbers to be arranged : ";
    cin >> n;
    arr = new int[n];
    cout << ("\nEnter the numbers to be arranged : ") & amp;
    lt; & amp;
    lt;
    endl;
    for (int k = 0; k < n; k++)
        cin >> arr[k];
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (dig1_max(arr[j]) < dig1_max(arr[j + 1])) //comparing entered numbers' left most digit
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            } //swapping done between arr[i] &amp;amp; arr[i+1]
            else if (dig1_max(arr[j]) == dig1_max(arr[j + 1])) //comparing entered numbers' left most digit
            {
                a = arr[j];
                b = arr[j + 1];
                num_max( & a, & b);
                arr[j] = a;
                arr[j + 1] = b;
            } else {}
        }
    }
    cout << "The largest number formed combining entered numbers is ";
    for (int z = 0; z < n; z++)
        cout << arr[z];
}
int dig1_max(int x) //this function returns left most digit of argument
    {
        int n = 0;
        while (x > 0) {
            n = x % 10;
            x = x / 10;
        }
        return (n);
    }
void num_max(int * m, int * n) {
    int s = 1, k, c = 0, num1, num2, p, q;
    p = * m;
    q = * n;
    k = q;
    for (; k > 0; c++) {
        k = k / 10;
    } //counting no.of digit in integer number
    for (; c > 0; c--) {
        s = s * 10;
    }
    num1 = p * s + q; //number formed combining two array elements
    k = p;
    c = 0;
    for (; k > 0; c++) {
        k = k / 10;
    } //counting no. of digit in integer number
    s = 1;
    for (; c > 0; c--) {
        s = s * 10;
    }
    num2 = q * s + p; //number formed combining two array elemnets
    if (num1 > num2) //two formed numbers get compared
    { * m = p; * n = q;
    } else { * m = q; * n = p; //swapping done between two elements of array
    }
}

click here to see running code on Ideone

Explanation :

dig1_max(int x) function returns left most digit of the number that is passed to function as argument.
num_max(int * m,int *n) function compares two numbers (those are passed as argument) and helps in arranging them in array in such a manner that combination of one number & next number in array  makes larger number than  combination of reverse . Comparison is done at first based on left most digit of two numbers,if both number have same left most digit then based on number formed by combining two array elements.

Details discussion on how code executes with example input, diagram :

Let say, entered number by user are 3,327,94.
Now array arr is like

Now, for loops in program run for i=0,j=0.
If(dig1_max(arr[j])<dig1_max(arr[j+1]))
dig1_max(3) function returns 3, dig1_max(327) function returns 3
if(dig1_max(arr[j])==dig1_max(arr[j+1]))
=>if(3=3) =>true
a=3,b=327

num_max(&a,&b)
num1=p*s+q=3*1000+327=3327
num2=q*s+p=327*10+3=3273
if(num1>num2) //condition true here

No change in array elements’ position  After execution of this function,

Now ,for loops in program run for i=0,j=1
if(dig1_max(arr[j])<dig1_max(arr[j+1])) => if(3<9)=>condition true , swaping is done between element of arr[1] & arr[2],means 327 & 94 swap their position in array.
Now, array is like

Now,for loops in program runs  for i=1,j=0.
if(dig1_max(arr[j])<dig1_max(arr[j+1]))
If(3<9)=>condition true  , Swaping between 3 & 94 occur in array

Now, array is like

Now, for loops in program run for i=1 ,j=1
if(dig1_max(arr[j])<dig1_max(arr[j+1]))
If(3<3) //condition false
else if(dig1_max(arr[j])==dig1_max(arr[j+1]))
=>if(3=3) //no change occurs in array actually.
Now, array is like

All elements of array arr are printed without any space. So it prints 943327 .This is the largest number can be formed by combination of entered numbers.

Another Code To Generate largest number :

#include "iostream";#
include "algorithm";#
include "vector";#
include "string";
using namespace std;
int num_max(string, string);
int main() {
    int n;
    string str;
    cout << "Enter number of non-negative numbers to be arranged : ";
    cin >> n;
    cout << "\nEnter the numbers to be arranged : ";
    vector < string > vec;
    for (int k = 0; k < n; k++) {
        cin >> str;
        vec.push_back(str); //inputted string gets into vector
    }
    sort(vec.begin(), vec.end(), num_max); //sorting done according to num_max() function
    cout << "\nThe largest number formed combining entered numbers is ";

    for (int I = 0; vec.size(); I++)
        cout << vec[I];
    return 0;
}
int num_max(string A, string B) //this function compares two numbers as string
    {
        string AB = A.append(B);
        string BA = B.append(A);
        if (AB.compare(BA) > 0)
            return 1;
        else
            return 0;
    }

click here to see running code on Ideone

 Explanation:

Entered numbers by user are inputted as string & stored in vector.sort function is called with 3 arguments sorting starting position by begin function, sorting position by end function, the function (num_max() function) according to which sorting will be done.Compare function compares two strings AB & BA , if 1is returned ,then AB is grater than BA, in the sort function AB will get ahead of BA.If 0 is returned ,then BA is grater than AB ,in the sort function BA will get ahead of AB .Then elements of vector will be printed in desired sorted order.

Similar Articles

Filed Under: Amazon Interview Question

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

CodeChef Code SGARDEN

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Given a float number convert it into the string WITHOUT using any inbuilt Function

Right view of Binary tree

Urban Ladder Written Test.

Print Power Set of a Set

The Magic HackerEarth Nirvana solutions Hiring Challenge

Implement a generic binary search algorithm for Integer Double String etc

VMWare Openings

flattens 2 D linked list to a single sorted link list

Facebook Interview Question : Interleave List

Python Array String

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Singly linked list

Find the smallest window in a string containing all characters of another string

SAP Hiring Off-Campus General Aptitude

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

Serialise Deserialise N-ary Tree

Python List

SAP Interview Questions

Find two non repeating elements in an array of repeating elements

Find the number ABCD such that when multipled by 4 gives DCBA.

strtok()

Leetcode: Edit Distance

Password Predictor

Implement LRU Cache

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Best Java Book | Top Java Programming Book for Beginners

Printing intermediate Integers between one element & next element of array

Copyright © 2025 · Genesis Framework · WordPress · Log in