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

#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;
}

Suggested Reading…

To print all combinations for the given string

Program to find all the substring using java