Find maximum number

1

Question — You are given an array of and you are given a number k . For every i where 1<=i<=k you are given two numbers a and b . a and b are the index of array and you need to swap them . At every swapping there is an new array formed . You need to find the array when we merge all of the numbers make the largest number.

1<=n,k<=1e5

Example — input — n and k where n- total integer in array array value — 1<=array[i]<=1e5

input — 6 3 1 2 3 4 5 6 ------ 1 4 — after swapping a[1] and a[4] array becomes — 423156 ------ 2 5 — after swapping a[2] and a[5] array becomes — 453126 ------ 3 6 — after swapping a[3] and a[6] array becomes — 456123

so if we consider all the 3 numbers the maximum is — 456123

I can tell you my approach but I fail .Intially i was thinking I can take them into string and then just take the maximum out of it but I fail because the array range is from 1 to 1e5 . So if you have any approach help me out. And it is not from any ongoing contest . I dont have any proof for that but it is not.The question is from yesterday off campus test contest and it is over yesterday.

thankyou.

3

@shravan660 If you sort it your index position differ and you are end up getting wrong answer .If you tell me with an example its better.

4

anyone know how to solve this…

5

Can you provide the question link. It will be helpful.

6

Let’s try to think smartly. Let a shift operation be of type swap(i, j), where i and j are indices and such that i < j(indexing starts from the right, so, the MSD is at the index 0). Then it only makes sense to do this operation where A[i] < A[j]. So, discard all the operations where it is otherwise. Now, further we want the replacement to happen such that larger digit comes at as smaller index as possible, so, if there two swap operations where A[i1] < A[j1] and A[i2] < A[j2]. Then choose the smaller of i1 or i2. If It’s a tie between i1 and i2 then choose the greater of A[j1] and A[j2].
Ofcourse, you need to handle one more case when for all swap operations (i, j) A[i] > A[j] then choose the greater of all i. If there is a tie then choose the one with greatest of all A[j].