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

#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

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
0 0 votes
Article Rating
Subscribe
Notify of
guest
5.4K Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
5.4K
0
Would love your thoughts, please comment.x
()
x