Print the Maximum possible K digit number
![Print the Maximum possible K digit number](https://wisdomoverflow.com/wp-content/uploads/2019/04/Screenshot-366.png)
Question
Given an array of numbers and a number k. Print the maximum possible k digit number which can be formed using given numbers.
Logic
- We are given an array and k. we have to form a number with k digit which is maximum. Ex: In Sample_1 k=3 so we find the largest possible number with 3 digits. We use Brute force method to solve this.
- First, we sort the array so we can find the maximum possible number. Array after sorting arr[] = { 973, 9, 4, 1 }
- Take the first element from the array and add that with other elements till the count reaches k.
- If the digit count is lesser continue adding. Ex: If we take 9 and 9+4 = 94 then count<k (2<3) so again 94+1. Now count==k.
- If count exceeds skip that element Ex: 973+9 (count >k)
- When the count is reached, check whether it is greater than previous max value and store it.
- Repeat the same for all array elements.
Note
Program
#include<iostream> //std::cout/cin #include<vector> //std::vector #include<algorithm> //std::sort using namespace std; int main() { int n,k; cin>>n>>k; if(n<k) { cout<<"size of k is larger"; return 0; } vector<string> a(n); /*Get array elements*/ for(int i = 0; i<n; i++) { cin>>a[i]; } /*Sort array elements using sort()*/ sort(a.rbegin(),a.rend()); for(int i = 0; i<n; i++) { cout<<a[i]<<" "; } cout<<endl; string max; /*If the largest number count is equal to k*/ if(a[0].size()==k) { max=a[0]; } /*Using brute force method to find all the combinations*/ for(int i = 0; i<n; i++) { string var = a[i]; for(int j = 0; j<n; j++) { if(i == j) continue; //cuz we don't add two same numbers string temp = var+a[j]; //adding two digits ex: 5+6= 56 int s = temp.size(); // size of number ex:56.size() => 2 /*Digit count equals to k */ if(s == k) { /*Larger than max*/ if(max<temp) { max = temp; } } /*Digit count greater*/ if(s>k) { continue; //continue without changing var } /*Digit count lesser*/ if(s<k) { var = temp; //update the var Ex: 56<k then var = 56 } } } /*Printing largest possible number*/ cout<<max<<endl; }