 # Form the largest number?

1 Like

can you share the link for the problem ??

1 Like

Is this from some ongoing contest ??

Share the problem link first then we are going to tell us our approach.
We should confirm that it must not be from some ongoing contest.

no!! just i am solving the problem

but always the starting number should be max in order to obtain a max num

No you cant say this.
Like in example
Input-
2
61 100

The output will be 61100 , not 10061.

1 Like

as in your i/p and o/p in your solution there is a number 6 so it should come first

but i am unable to get the logic

Yes you are correct, I got a mistake in my approach.

We can use DP to solve this:
Let dp[i][j] be the max string we can make from index from i to j.
Our answer will be stored in dp[n-1]

Initial state will be dp[i][i] = arr[i] for i = 0 to n-1

Then for general i,j
dp[i][j] = max ( dp[i][j], dp[i][k] + dp[k+1][j], dp[k+1][j] + dp[i][k] )

Here is the function in case you want to have a look:

``````void solve(){
int n;
cin>>n;
vector<string> arr(n);
for(int i=0; i<n; ++i){
cin>>arr[i];
}
string dp[n][n];
for(int i=0; i<n; ++i){
dp[i][i] = arr[i];
}
for(int len=2; len<=n; ++len){
for(int i=0; i<n-len+1; ++i){
int j = i + len - 1;
dp[i][j] = "";
for(int k=i; k<j; ++k){
dp[i][j] = max<string>({ dp[i][j], dp[i][k] + dp[k+1][j], dp[k+1][j] + dp[i][k] });
}
}
}
// for(int i=0; i<n; ++i){
// 	for(int j=i; j<n; ++j){
// 		cout<<dp[i][j]<<" ";
// 	}
// 	cout<<'\n';
// }
cout<<dp[n-1]<<'\n';
}
``````

dp means dynamic programming

Problem is in the domain of strings.
So maybe we can handle problem like this.
Treat numbers as strings and sort lexicographically (from highest to lowest). Print all string in this order.

1 Like

Here you can do the SUBMIT thing.

3 Likes

You can compare the every character of the string if it is small add it to the right else to the left. Since the constraints are too small It gonna pass easily.

bool cmp(string x, string y){
string temp1 = x.append(y);
string temp2 = y.append(x);
return temp1.compare(temp2)>0?true:false;
}

void printLargestPossibleNumber(vectorarr){
sort(arr.begin(),arr.end(),cmp);
for(int i=0;i<arr.size();i++){
cout<<arr[i];
}
}

can anyone explain the above functions

i.e.,the sort function line