Print the Maximum possible K digit number

Print the Maximum possible K digit number

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

Sorting STL reference

Program

[code lang=”c”]
#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;
}
[/code]

Suggested Reading…

To print all combinations for the given string

Program to find all the substring using java

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.

Leave a Reply

Your email address will not be published. Required fields are marked *