Given a array int a[]={2,5,1,9,3,7,2,8,9,3} and the no. of swap operations.We are allowed to do swap operations.


  • 0
    A

    Given a array int a[]={2,5,1,9,3,7,2,8,9,3} and the no. of swap operations.We are allowed to do swap operations.
    swap constraint: exchange only adjacent element.
    Find the max number that can be formed using swap operations. Fab.com

    Example : 2 ,5,8,7,9 and N=2 , so only two swap operation can be performed.
    output : 8,2,5,7,9


  • 0

    @amanbabu, could you share please, the company tag and an example? Thanks


  • 0

    @amanbabu Welcome to the new Discuss! If applicable, could you please add the company tag? Please see here for instructions on how to do so, thanks.


  • 0

    @amanbabu Could you please also add at least one example to your description? Thanks!


  • 0
    G

    Maybe dp+greedy works. use example a[]={8,8,1,9,3,7,2,8,9,3} and N=6.

    1. Use two pointers to find in a[0,...6] to get 8 and 9;
    2. swap 9 with 8, cost 3 steps, get {9,8,8,1,3,7,2,8,9,3}, N=3
    3. Use two pointers to find 9-1, 8-3, 8-7, 1-2, then get 1 and 7
    4. swap 7 with 1, cost 2 steps, get {9,8,8,7,3,1,2,8,9,3}, N=1
    5. continue, swap 2 with 1, then N=0, end.

  • 0

    @GoGoDong just to make problem clearer. N - number of adjacent swaps, what will be the result in case we have [5,4,3,2,1] and N = 3 ? also can we swap the same adjacent indexes multiple times. I the example I provide , can we do swaps [5,4,3,1,2 ],[5,4,3,2,1],[5,4,3,1,2]?


  • 0
    G

    @elmirap
    My understanding is still 54321
    I'm thinking that, if the array is already non-increasing, the "two-pointers" phase will fail to find two numbers to swap, so go to end directly.


  • 0

    @GoGoDong Can you tell me the 3 swaps , you will do to get 54321


  • 0
    G

    @elmirap Oh! Sorry I did not understand what you meant before.
    @amanbabu said "the no. of swap operations. We are allowed to do swap operations"
    So I thought it's OK not to use up all the N steps. Is it?


  • 0

    it is not specified whether he means max number of swaps or the exact number of swaps.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.