/*----------------------------------------- 🎙️ *Asked in Amazon* Given a list of non negative integers, arrange them such that they form the largest number. For example: Given [3, 30, 34, 5, 9], the largest formed number is 9534330. Note: The result may be very large, so you need to return a string instead of an integer. -----------------------------------------*/ #include #include #include #include #include using namespace std; void sort(vector& myVec) { int size = myVec.size(); for(int i = 0; i < size; i++) { for(int j = 0; j < size - 1; j++) { // Trick to get total digits of a number // log10(0) gives INF int rangeOne = (myVec[j] == 0)? 1 : floor(log10(myVec[j]) + 1); int rangeTwo = (myVec[j+1] == 0)? 1 : floor(log10(myVec[j+1]) + 1); // Concatenating two numbers // First with second and vice versa size_t num1 = (pow(10, rangeTwo) * myVec[j]) + myVec[j+1]; size_t num2 = (pow(10, rangeOne) * myVec[j+1]) + myVec[j]; // Comparing both numbers if(num1 < num2) { // Swapping size_t temp = myVec[j]; myVec[j] = myVec[j+1]; myVec[j+1] = temp; } } } } void display(const vector& myVec) { int size = myVec.size(); // Displaying vector cout << "Sequence:\n["; for(int i = 0; i < size; i++) { cout << myVec[i] << ((i == size - 1)? "]\n" : ", "); } } void concatNumber(const vector& myVec) { // Displaying largest concatenated number string largestNumber = "\0"; for(int i: myVec) { largestNumber += to_string(i); } cout << "Largest number: " << largestNumber << "\n\n"; } int main() { vector> vec = { {3, 30, 34, 5, 9}, {2, 5, 3, 9, 8, 0, 1, 4, 6, 7}, {100, 105, 19, 1088, 1, 13464, 2}, {88, 818, 8066, 879, 8, 1111, 103115}, {6, 1, 2, 4, 5, 3, 9, 8, 7}, {9, 30, 34, 5, 3}, {3, 30, 34, 50, 9}, {34, 77, 93, 2, 1}, {78, 32, 1, 2, 3}, {282, 200, 61, 152, 114, 531, 595, 610, 506, 840, 711}, {2822, 2002, 61, 1532, 1134, 531, 5935, 5026, 8430, 7311} }; for(auto it = vec.begin(); it != vec.end(); ++it) { display(*it); sort(*it); concatNumber(*it); } return 0; }

Largest Number Concatenation