CareerCup

This is a DFS algorithm which gives correct results. Not sure how to improve this by smart algorithms.

#include <iostream>
#include <vector>
using namespace std;
void getMax(vector<int>& input, int k, int& maxNum, vector<int>& output){
    if (k == 0) {
        int sum = 0;
        for (auto v : input) {
            sum *= 10;
            sum += v;
        }//calculate the number after several swaps
        if (sum > maxNum) {
            maxNum = sum;
            output = input;
        }//update the results
        return;
    }
    
    for (int i = 0; i < input.size() - 1; i ++) {
        for (int j = i + 1; j < input.size(); j ++) {
            swap(input[i], input[j]);//try to swap input[i] with input[j]
            getMax(input, k - 1, maxNum, output);//takecare of the other k - 1 swaps
            swap(input[i], input[j]);//swap back
        }
    }
    return;
}
void swap2max(vector<int> input, int k) {
    if (input.size() < 2) {
        cout << "invalid input" << endl;
    }
    int maxNum = INT_MIN;
    vector<int> maxVec;
    getMax(input, k, maxNum, maxVec);//DFS function to call

    //print out the results here
    cout << "{ ";
    for (int i = 0; i < maxVec.size(); i ++) {
        cout << maxVec[i] << " ";
    }
    cout << " }" << endl;
    return;
}

int main(int argc, const char * argv[])
{

    vector<int> input1 = {1,3,2};
    swap2max(input1, 1);
    
    vector<int> input2 = {1,3,2};
    swap2max(input2, 2);
    
    vector<int> input3 = {7,8,9,9};
    swap2max(input3, 2);
    
    vector<int> input4 = {8,7,9,9};
    swap2max(input4, 2);
    return 0;
}

Solution in python :

#!/usr/bin/python

from sys import stdin,stdout,argv
import heapq

def kswaps(m, k):
  d=dict()
  for i in xrange(len(m)):
    l=d.setdefault(m[i], list())
    l.append(i)
  #print d

  i=9
  p=0
  while k>0 and i>=0 and p<len(m):
    #print k,i,p
    l=d.get(i, list())
    c=min(k, len(l))
    h=[]
    for j in xrange(c):
      heapq.heappush(h, (m[p], p))
      p+=1
    while len(h)>0:
      vd, vp = heapq.heappop(h)
      m[l.pop()] = vd
      m[vp] = i
      #print m
    k-=c
    i-=1

def main():
  m=[8,7,9,9]
  k=2
  print m, k
  kswaps(m, k)
  print m

if __name__ == "__main__":
  main()

complexity O(N)+O(k log k)

I tried to find a smart solution but in the end they all fail... I think an "intelligent brute force" in the for of DFS has to be used here. Imagine that your digits are in array A of digits. My algo is generally the following:
1.) you sort your digits in descending order, with this you receive the biggest possible number for this digits M.
2.) Your target number will have common prefix with this one (since the primary target in k swaps is to maximize the most significant digits);
3.) Now you start your dfs from the most significnat number(say, A[0]), if it is the same as M[0] you try to maximise the remaining 1..n-1 digits with k swaps. If it is not equal to M[0], you try to swap it with any digit in A that equals M[0] and for each such swap solve a subproblem for 1..n-1 digits with k-1 swaps.
4.) as soon your arrive at a problem with 0 swaps you check if the current number is the largest number generated so far, and if so, memorize it.

Although this solution has very roughly estimated complexity of O(n!/(n-k)!) (where n is the number of digits, and k is the number of swaps), I believe that the in-depth math analysis would prove it to be much faster. One more point is to involve dynamic programming, but this seems to work at the cost of very high memory consumption.

Algorithm:
a. We start at the leftmost digit (current-position=0).
b. We start with the highest digit value (current-digit-value=9).
c. We scan the number and note all the positions of the digits of the current digit value. Example: N=8799 , positions=[2, 3] (the digit 9 is in positions 2 and 3).
d. We put the K digits starting at the current position in a list (if some of these digits are equal or higher then the current digit value, then we skip them). Example: K=2 digits={8, 7} (the 2 digits starting from the current position).
e. Now we swap the rightmost digit from the "positions" list in step c, with the lowest value digit from "digits" list from step d. We repeat this with the next digit in each list, until either list is exhausted. Example: first swap right-most 9 with 7 (lowest value): N=8997, then swap second 9 from right with next leowest digit 8: N=9987.
f. Decrement K by the number of swaps made. Exit if K is zero. Example: K=0
g. Increment current-position similarly. Exit if we reached the end.
h. Decrement current-digit-value (current-digit-value=8). Exit if we reached zero.
i. Repeat steps c,d,e,f,g,h,i

Complexity: O(N)+O(k log k) if implementing the list in step d as a heap.

This question is a bit tricky. This is the logic I propose.

Put the numbers in an array A[n] (referenced by 0 to n-1)
For k=1:
Swap A[k-1] with the maximum number in A[k : n-1] such that the number is greater than A[k-1]. If there are 2 such numbers of same value greater than A[k-1], pick the rightmost one(one with larger index).
.
.
.
For k=i:
Swap A[k-i] with the maximum number in A[k : n-1] such that the number is greater than A[k-i]. If there are 2 such numbers of same value greater than A[k-i], pick the rightmost one(one with larger index).

Basic Selection Sort logic with a little modification till K-steps.
Whatever remains in the array is the solution.

Time : O(n) * k = effectively O(n)

This is just a simple K iterations of selection sort with one exclusions:
- when looking for maximum element from all leftmost ones we take the position of the "latest" one - e.g. for "26316" - if we are at "2" digit now we swap it with latest "6" - not with first met.

Here is the code (it's rather big because I need to convert from int to list of ints and back)

public static int find(int input, int k) {
        List<Integer> digits = new ArrayList<>();
        int n = input;
        while (n > 0) {
            digits.add(n % 10);
            n /= 10;
        }
        Collections.reverse(digits);

        int numberOfSwaps = 0, idx = 0;
        while (numberOfSwaps != k) {
            int pos = findLastBiggest(digits, idx);
            if (pos != idx) {
                // We managed to find the next number that is bigger than current
                swap(digits, idx, pos);
                numberOfSwaps++;
            }
            idx++;
        }
        return arrayToInt(digits);
    }

    private static int findLastBiggest(List<Integer> digits, int from) {
        int max = 0, maxPos = 0;
        for (int i = from; i < digits.size(); i++) {
            // Note, that latest max overrides the previous one even if they are equal
            if (digits.get(i) >= max) {
                max = digits.get(i);
                maxPos = i;
            }
        }
        // In case that we already on maximum - return the current pos
        if (max == digits.get(from)) {
            return from;
        }
        return maxPos;
    }
    private static void swap(List<Integer> digits, int from, int to) {
        int t =digits.get(from);
        digits.set(from, digits.get(to));
        digits.set(to, t);
    }

    private static int arrayToInt(List<Integer> digits) {
        int result = 0;
        for (int i : digits) {
            result = result * 10 + i;
        }
        return result;
    }

    public static void main(String[] args) {
        assert (find(34155, 2) == 55143);
        assert (find(12520, 2) == 52210);
    }

#include "stdafx.h"
#include <Windows.h>

class CNumberTransform
{
public:
	bool Init(UINT num, BYTE nDigits)
	{
		return (PrepareDigArray(num, nDigits) && PrepareDigTable());
	}

	//todo : use destructor for uninit

	UINT GetMaxNumberWithSwaps(BYTE nSwaps)
	{
		BYTE i = 0;
		BYTE curidx = m_digarraysize - 1;

		while (i < nSwaps && curidx > 0)
		{

			DIGITIDXNODE* pSwapNode = GetNodeToSwap(curidx);

			if (pSwapNode != NULL )
			{
				i++;
				
				BYTE digswap = m_digarray[pSwapNode->index];
				m_digarray[pSwapNode->index] = m_digarray[curidx];
				m_digarray[curidx] = digswap;

				Insert(pSwapNode);
			}

			curidx--;
			
		}

		return ConvertDigArrayToUINT();
	}

private:

	struct DIGITIDXNODE
	{
		BYTE index;
		DIGITIDXNODE* next;
	};

	bool PrepareDigArray(UINT num, BYTE nDigits)
	{
		//todo : check for the allocation faliure

		m_digarray = new BYTE[nDigits];
		m_digarraysize = nDigits;

		m_digidxnodearray = new DIGITIDXNODE[nDigits];

		for (BYTE i = 0; i < nDigits; i++)
		{
			BYTE dig = num % 10;
			num /= 10;

			m_digarray[i] = dig;

			m_digidxnodearray[i].index = i;
			m_digidxnodearray[i].next = NULL;
		}

		return true;
	}

	bool PrepareDigTable()
	{
		DIGITIDXNODE* digtableend[10];

		//init table heads to NULL
		for (BYTE i = 0; i < 10; i++)
		{
			m_digtable[i] = NULL;
		}

		for (BYTE i = 0; i < m_digarraysize; i++)
		{
			BYTE dig = m_digarray[i];
			DIGITIDXNODE* pNode = m_digidxnodearray + i;

			if (m_digtable[dig] == NULL)
			{
				//first node
				m_digtable[dig] = pNode;
			}
			else
			{
				digtableend[dig]->next = pNode;
			}

			digtableend[dig] = pNode;
		}

		return true;
	}

	void Insert(DIGITIDXNODE* node)
	{
		BYTE dig = m_digarray[node->index];

		if (m_digtable[dig] == NULL)
		{
			m_digtable[dig] = node;
		}
		else if (m_digtable[dig]->index > node->index)
		{
			DIGITIDXNODE* pTemp = m_digtable[dig];
			m_digtable[dig] = node;
			node->next = pTemp;
		}
		else
		{
			DIGITIDXNODE* pPrev = m_digtable[dig];
			DIGITIDXNODE* pCur = pPrev->next;
			while (pCur != NULL && pCur->index < node->index)
			{
				pPrev = pCur;
				pCur = pCur->next;
			}

			DIGITIDXNODE* pTemp = pPrev->next;
			pPrev->next = node;
			node->next = pTemp;
		}
	}

	DIGITIDXNODE* GetNodeToSwap(BYTE curidx)
	{
		DIGITIDXNODE* pRet = NULL;
		BYTE curdig = m_digarray[curidx];
		for (BYTE i = 9; i > curdig; i--)
		{
			DIGITIDXNODE* pNode = m_digtable[i];
			if (pNode != NULL &&  pNode->index < curidx)
			{
				//found the node
				pRet = pNode;
				//remove the node from the dig table
				DIGITIDXNODE* pNext = pNode->next;
				m_digtable[i] = pNext;
				break;
			}
		}

		return pRet;
	}

	DIGITIDXNODE*		m_digtable[10];

	BYTE*				m_digarray;
	DIGITIDXNODE*		m_digidxnodearray;
	BYTE				m_digarraysize;


	UINT ConvertDigArrayToUINT()
	{
		UINT nRet = 0;
		
		for (BYTE i = 1; i <= m_digarraysize; i++)
		{
			nRet *= 10;
			nRet += m_digarray[m_digarraysize - i];
		}

		return nRet;
	}


};

int _tmain(int argc, _TCHAR* argv[])
{

	CNumberTransform cnt;

	cnt.Init(7899, 4);
	UINT maxnum = cnt.GetMaxNumberWithSwaps(2);
	printf("new number is %d \n", maxnum);
	return 0;
}

def best_swap(m, k):
    index = {}
    l = []
    x = m
    n=0
    while x>0:
        l.append((x%10, n))
        index[x%10] = n
        x = x/10
        n += 1
    l.sort()

    def swap(m, i, j):
        a = (m/10**i)%10
        b = (m/10**j)%10
        # print "swapping", a, "and", b
        m = m + a*(10**j - 10**i) + b*(10**i - 10**j)
        index[a] = j
        index[b] = i
        return m
    try:
        for i in xrange(k):
            val, pos = l.pop()
            while pos == n-1:
                val, pos = l.pop()
                n -= 1
            m = swap(m, index[val], n-1)
            n -= 1
    except:
        # if you're already with the best number, but can still swap
        pass    
    return m

package google;

import java.util.Scanner;

/**
 *
 * @author brian
 */
public class Google {

    /**
     * @param args the command line arguments
     */
    
    int numofdig;
   String usernumber;
   int number;
    Scanner input=new Scanner(System.in); 
int inddig[]; 
int numofswap;
int max;
int flag;
int swap=0;

int check(int i)
{
        int temp;
   
       for(int j=i;j<inddig.length-2;j++)
       {
           if(inddig[j]==inddig[j+1])
           {
               flag=1;
       }
           
   }
       if(flag==1)
       {
           
            for(int j=i;j<inddig.length-2;j++)
       {
           
       temp=inddig[i];
           for(int k=j+1;k<inddig.length-2;k++)
           {
           if(temp>inddig[k])
           {
        swap=1;       
           }
       }
       }
   
    
    
    
    
    
    
       }
   
    
    return swap;
    
    
    
    
}


int max(int[] temp,int j)
{
 int limit=0;
    max=temp[j];
    
    for(int p=j;p<=temp.length-2;p++)
    {
        if(max<=temp[p]){
     max=temp[p];
     limit=p;
    }

    }
   
    return limit;
    
    
    
}
int max1(int[] temp,int j)
{
 int limit=0;
    max=temp[j];
    
    for(int p=j;p<=temp.length-2;p++)
    {
        if(max<temp[p]){
     max=temp[p];
     limit=p;
    }

    }
   
    return limit;
    
    
    
}

int breakdig(int temp)
{
    int temp1[]=new int[numofdig+1];
    int n ;
    n=temp;
    int i=0;
        while(n>0)
        {
          n=temp%10;  
        
            temp1[i]=n;
            i++;
            temp=temp/10;
        }
        int k=0;
    for(int j=temp1.length-2;j>=0;j--)
    {
         
    inddig[k]=temp1[j];    
    k++;
    }
   
    
 
   swap();
    return 0;
    
    
    
}
int swap()
{
int temp;
    int j = 0,i=0;
    int k;
    int sk;
    while(numofswap>0)
    {
       sk=check(i);
       
       if(sk==0){
         j=max(inddig,i);
       }
       
       else
       {
            j=max1(inddig,i);
           
       }
       
       
       
    
        temp=inddig[i];
      
        inddig[i]=inddig[j];
        inddig[j]=temp;
        
       i++;
        numofswap--;
        
    }
    
    display();
    
 
    
    
    return 0;
    
    
    



}


int display()
{
    
    
   
String result = "";
    for(int s=0;s<=inddig.length-2;s++)
    {
        
        
        result+=String.valueOf(inddig[s]);
    }
   
   System.out.println("Ans : "+result);
        return 0;
    
    
    
}



    int getnum(String temp)
            {
                
            numofdig=temp.length();
            number=Integer.parseInt(temp);
            
                inddig=new int [numofdig+1];
                breakdig(number);
                
        return 0;
                
                
            }
    
    int input()
    {
        
        System.out.println("Enter the number");
             usernumber=input.next();
        System.out.println("Enter the number of swaps");
        numofswap=input.nextInt();
   
        getnum(usernumber);
        
        
        
        
        return 0;
        
        
        
    }
    
    
    
    
    public static void main(String[] args) {
        
        new Google().input();
        // TODO code application logic here
    }
    
}

public class Google {

    /**
     * @param args the command line arguments
     */
    
    int numofdig;
   String usernumber;
   int number;
    Scanner input=new Scanner(System.in); 
int inddig[]; 
int numofswap;
int max;
int flag;
int swap=0;

int check(int i)
{
        int temp;
   
       for(int j=i;j<inddig.length-2;j++)
       {
           if(inddig[j]==inddig[j+1])
           {
               flag=1;
       }
           
   }
       if(flag==1)
       {
           
            for(int j=i;j<inddig.length-2;j++)
       {
           
       temp=inddig[i];
           for(int k=j+1;k<inddig.length-2;k++)
           {
           if(temp>inddig[k])
           {
        swap=1;       
           }
       }
       }
   
    
    
    
    
    
    
       }
   
    
    return swap;
    
    
    
    
}


int max(int[] temp,int j)
{
 int limit=0;
    max=temp[j];
    
    for(int p=j;p<=temp.length-2;p++)
    {
        if(max<=temp[p]){
     max=temp[p];
     limit=p;
    }

    }
   
    return limit;
    
    
    
}
int max1(int[] temp,int j)
{
 int limit=0;
    max=temp[j];
    
    for(int p=j;p<=temp.length-2;p++)
    {
        if(max<temp[p]){
     max=temp[p];
     limit=p;
    }

    }
   
    return limit;
    
    
    
}

int breakdig(int temp)
{
    int temp1[]=new int[numofdig+1];
    int n ;
    n=temp;
    int i=0;
        while(n>0)
        {
          n=temp%10;  
        
            temp1[i]=n;
            i++;
            temp=temp/10;
        }
        int k=0;
    for(int j=temp1.length-2;j>=0;j--)
    {
         
    inddig[k]=temp1[j];    
    k++;
    }
   
    
 
   swap();
    return 0;
    
    
    
}
int swap()
{
int temp;
    int j = 0,i=0;
    int k;
    int sk;
    while(numofswap>0)
    {
       sk=check(i);
       
       if(sk==0){
         j=max(inddig,i);
       }
       
       else
       {
            j=max1(inddig,i);
           
       }
       
       
       
    
        temp=inddig[i];
      
        inddig[i]=inddig[j];
        inddig[j]=temp;
        
       i++;
        numofswap--;
        
    }
    
    display();
    
 
    
    
    return 0;
    
    
    



}


int display()
{
    
    
   
String result = "";
    for(int s=0;s<=inddig.length-2;s++)
    {
        
        
        result+=String.valueOf(inddig[s]);
    }
   
   System.out.println("Ans : "+result);
        return 0;
    
    
    
}



    int getnum(String temp)
            {
                
            numofdig=temp.length();
            number=Integer.parseInt(temp);
            
                inddig=new int [numofdig+1];
                breakdig(number);
                
        return 0;
                
                
            }
    
    int input()
    {
        
        System.out.println("Enter the number");
             usernumber=input.next();
        System.out.println("Enter the number of swaps");
        numofswap=input.nextInt();
   
        getnum(usernumber);
        
        
        
        
        return 0;
        
        
        
    }
    
    
    
    
    public static void main(String[] args) {
        
        new Google().input();
        // TODO code application logic here
    }
    
}

I know that this answer is not fully correct (as Moi found the case, when this doesn't work), but as I spent a lot of time and would like to safe it for anyone, who comes here to find the solution, but cannot underestand it. So I added lots of comments and will explain it here.

To my mind if this algorithm is provided on the interview - they would accept it anyway, though it's not always correct :))

So, the main idea is to recurse the list and support the following invariant:
- maximum equal elements in the current sublist are moved to the head
- the swapped elements are moved to their position in descending order

So at each iteration we find the next LEN maximum elements and substitute them with LEN elements at the head of current sublist. Though elements at the head must be sorted so that to support the invariant.

Hope, this helps anybody, as I spend half a day on this and initially wrote incorrect greedy algorithm, suppose, that there are many such people.

public static void kSwap(List<Integer> input, int k) {
        if (k == 0 || input.size() <= k) {
            return;
        }

        // Finding the maximum digit in the list
        int m = getMaxDigit(input, k);

        // This contains all indexes in the array, that == m
        List<Integer> maxPositions = new ArrayList<>();

        // This contains all values from 0 to maxPosition.size()
        List<Integer> forSwapping = new ArrayList<>();

        int leftCursor = 0;
        // We iterate two cursors - one from the end that gathers indeces of all values == m
        // and the other from the head - just increment. Loop stops when cursors meet
        for (int i = input.size() - 1; i > 0 && i > leftCursor; i--) {
            if (input.get(i) == m) {
                forSwapping.add(input.get(leftCursor));
                maxPositions.add(i);
                leftCursor++;
            }
        }
        int len = maxPositions.size();

        // The most important part - we sort the 'head' in ascending order
        // to move in place of maximum elements in correct order
        Collections.sort(forSwapping);

        // Now just swap max item elements with #len first ones
        for (int i = 0; i < len; i++) {
            input.set(i, m);
            input.set(maxPositions.get(i), forSwapping.get(i));
        }

        // Recurse for sublist (#len first elements are already inplace)
        kSwap(input.subList(len, input.size()), k - len);
    }

    private static int getMaxDigit(List<Integer> input, int k) {
        return input.stream().max(Comparator.<Integer>naturalOrder()).get();
    }

    public static void main(String[] args) {
        List<Integer> l = new ArrayList<>(Arrays.asList(1, 3, 2));
        int k = 1;
        kSwap(l, k);
        System.out.println(l);

        l = new ArrayList<>(Arrays.asList(1, 3, 2));
        k = 2;
        kSwap(l, k);
        System.out.println(l);

        l = new ArrayList<>(Arrays.asList(7, 8, 9, 9));
        k = 2;
        kSwap(l, k);
        System.out.println(l);

        l = new ArrayList<>(Arrays.asList(8, 7, 9, 9));
        k = 2;
        kSwap(l, k);
        System.out.println(l);

        l = new ArrayList<>(Arrays.asList(8, 7, 6, 9, 5, 9));
        k = 3;
        kSwap(l, k);
        System.out.println(l); // This is not correct :((

    }

Not time to code, will just give an outline.
Index for walking forward.
Array size 10 of indexes for walking backward, initialized with last occurence of digit. array[5] will have last index of 5.
state variable start with 9 and decrement to 0.
walking forward, if state 9 and not 9, swap with array[9]. update array[9] walking backward but stop as soon as reached forward index.
Do all states like that but stop as soon as reached amount of swaps.

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package google;

import java.util.Scanner;

/**
 *
 * @author brian
 */
public class Google {

    /**
     * @param args the command line arguments
     */
    
    int numofdig;
   String usernumber;
   long number;
    Scanner input=new Scanner(System.in); 
long inddig[]; 
int numofswap;
long max;
int flag;
int swap=0;
int global=0;

int check(int i)
{
    
    int main=0;
        double temp;
   
       for(int j=i;j<inddig.length-2;j++)
       {
           if(inddig[j]==inddig[j+1])
           {
               flag=1;
       }
           
   }
       if(flag==1)
       {
           
            for(int j=i;j<inddig.length-2;j++)
       {
           
       temp=inddig[i];
           for(int k=j+1;k<inddig.length-2;k++)
           {
           if(temp>inddig[k])
           {
        swap=1;
      
           }
       }
       }
   
  
    
    
    
    
       }
   
    
    return swap;
    
    
    
    
}


int max(long[] temp,int j)
{
    int cswap=j;
 int limit=0;
    max=temp[j];
    int s=j;
    for(int p=j;p<=temp.length-2;p++)
    {
        if(max<=temp[p]){
     max=temp[p];
     limit=p;
     cswap=j+1;
    }

    }
while(cswap==j)
{
    j++;
    
         max=temp[j];
        for(int p=j;p<=temp.length-1;p++)
    {
        if(max<temp[p]){
     max=temp[p];
     limit=p;
    }

    }
}
   if(limit==0)
   {
       global=0;
   }
    return limit;
    
    
    
}
int max1(long[] temp,int j)
{
    int cswap=j;
 int limit=0;
    max=temp[j];
    
    for(int p=j;p<=temp.length-2;p++)
    {
        if(max<temp[p]){
     max=temp[p];
     limit=p;
     cswap=j+1;
     
    }

    }
    
    while(cswap==j)
{
    j++;
    
         max=temp[j];
        for(int p=j;p<=temp.length-1;p++)
    {
        if(max<temp[p]){
     max=temp[p];
     limit=p;
       cswap=j+1;
    }

    }
        
}
   global=j;


  
        
      
               
     
     
   if(limit==0)
   {
       global=0;
   }
   
  
    return limit;
    
    
    
}

int breakdig(long temp)
{
    long temp1[]=new long[numofdig+1];
    long n ;
    n=temp;
    int i=0;
        while(temp>0)
        {
          n=temp%10;  
        
            temp1[i]=n;
            i++;
            temp=temp/10;
        }
        int k=0;
    for(int j=temp1.length-2;j>=0;j--)
    {
         
    inddig[k]=temp1[j];    
    k++;
    }
   
    
 
   swap();
    return 0;
    
    
    
}
int swap()
{
    
long temp;
    int j = 0;
    global=0;
    int k;
    int sk;
    while(numofswap>0)
    {
       sk=check(global);
       
       if(sk==0){
         j=max(inddig,global);
       }
       
       else
       {
            j=max1(inddig,global);
           
       }
       
       
       
    
        temp=inddig[global];
      
        inddig[global]=inddig[j];
        inddig[j]=temp;
        
       global++;
        numofswap--;
   
    }
    
    display();
    
 
    
    
    return 0;
    
    
    



}


int display()
{
    
    
   
String result = "";
    for(int s=0;s<=inddig.length-2;s++)
    {
        
        
        result+=String.valueOf(inddig[s]);
    }
   
   System.out.println("Ans : "+result);
        return 0;
    
    
    
}



    int getnum(String temp)
            {
                
            numofdig=temp.length();
            number=Integer.parseInt(temp);
            
                inddig=new long [numofdig+1];
                breakdig(number);
                
        return 0;
                
                
            }
    
    int input()
    {
        
        System.out.println("Enter the number");
             usernumber=input.next();
        System.out.println("Enter the number of swaps");
        numofswap=input.nextInt();
   
        getnum(usernumber);
        
        
        
        
        return 0;
        
        
        
    }
    
    
    
    
    public static void main(String[] args) {
        
        new Google().input();
        // TODO code application logic here
    }
    
}

vector<int> largest_swap(vector<int> num, int swap)
{
if(num.size() == 0 || swap == 0) return num;
vector<vector<int>> result;
largest_swap(result, num, swap,0);
return get_largest(result);
}
void largest_swap(vector<vector<int>> & result, vector<int> num, int swap, int location)
{
if(location == num.size() -1 || swap == 0)
{
result.push_back(num);
return;
}

int max = num[location];
for(int i = location + 1; i < num.size(); i ++)
{
if(max < num[i]) max = num[i];
}

if(max != num[location])
{
for(int i = location + 1; i < num.size(); i ++)
{
if(num[i] == max)
{
swap(num[location], num[i]);
largest_swap(result, num, swap -1, location + 1);
swap(num[location], num[i]);
}
}
}
else
{
largest_swap(result, num, swap, location + 1);
}
}

vector<int> largest_swap(vector<int> num, int swap)
{
if(num.size() == 0 || swap == 0) return num;
vector<vector<int>> result;
largest_swap(result, num, swap,0);
return get_largest(result);
}
void largest_swap(vector<vector<int>> & result, vector<int> num, int swap, int location)
{
if(location == num.size() -1 || swap == 0)
{
result.push_back(num);
return;
}

int max = num[location];
for(int i = location + 1; i < num.size(); i ++)
{
if(max < num[i]) max = num[i];
}

if(max != num[location])
{
for(int i = location + 1; i < num.size(); i ++)
{
if(num[i] == max)
{
swap(num[location], num[i]);
largest_swap(result, num, swap -1, location + 1);
swap(num[location], num[i]);
}
}
}
else
{
largest_swap(result, num, swap, location + 1);
}
}

vector<int> get_largest (vector<vector<int> result)

Below is my java solution to the problem. The time complexity of my solution is O(M*K), where M is equal to the number of digits of M and K is k. What do you think? Please leave feedBack.

public int maxPossibleInteger ( int m, int k){
		//Turn M into charArray
		char [] charArrayOfM = String.valueOf(m).toCharArray();
		
		int j =0;
		while ( k > 0) {
			int max = charArrayOfM[j];
			int tempIndexID =0;
			
			//Loop through Char array to find largest digit
			//Start at index j+1
			for ( int i=(j+1); i< (charArrayOfM.length ); i++){
				if ( charArrayOfM[i] > max){
						tempIndexID=i;
						max = charArrayOfM[i];
				}}
			
			//Swap Char if Necessary
			if ( charArrayOfM[j] < max){
				char tempChar = charArrayOfM[tempIndexID];
				charArrayOfM[tempIndexID] =charArrayOfM[j];
				charArrayOfM[j]= tempChar;
				}	
			k--;
			j++;
		}
		int maxInteger= Integer.parseInt(String.valueOf(charArrayOfM));
	return maxInteger;
	}

solve this problem with O(n) complexity,
(1) if K >= arr.length - 1, sort the arr by descending order
(2) iterate the array, count the number of 1 ~ 9.
(3) swap from digit 9 to 1 in a loop. As to one digit, swap Min(k, count[digit]) count.
(4) sort the element which are swapped by descending order, pay attention to the element which is unnecessary to be swapped.

code:

public void swapToMax(int[] arr, int k) {
		if (k >= arr.length - 1) {
			// counting sort by descending order, it takes O(n)
			sortDesc(arr, 0, arr.length - 1);
			return;
		}
		int[] exsit = new int[10];
		for (int i = 0; i < arr.length; i++) {
			exsit[arr[i]]++;
		}
		int index = exsit.length - 1;
		int swapIndex = 0;
		while (k > 0 && index > 0 && swapIndex < arr.length) {
			if (exsit[index] > 0) {
				// numbers of elements to swap
				int dis = Math.min(k, exsit[index]);
				for (int i = swapIndex; i < swapIndex + dis; i++) {
					if (arr[i] == index) {
						// skip the element which should not be swapped
						exsit[index]--;
					}
				}
				sortDesc(arr, swapIndex, swapIndex + dis - 1);
				for (int i = swapIndex + dis; i < arr.length; i++) {
					if (k == 0 || exsit[index] == 0) {
						break;
					}
					if (arr[i] == index) {
						while (arr[swapIndex] == index) {
							swapIndex++;
						}
						swap(arr, swapIndex, i);
						k--;
						exsit[index]--;
						swapIndex++;
					}
				}
			}
			index--;
		}
	}

Here's a solution that I cheated a little to get.

def maxNum(M, k):
    x = [int(x) for x in str(M)]
    y = k
    z = sorted(x, reverse = True) # nondeterminism
    def swap(i, j, l):
        tmp = l[i]
        l[i] = l[j]
        l[j] = tmp
        return l
    def find_index(number, i, l):
        num = number
        for x in range(i, len(l)):
            if l[x] == num:
                return x
        
    for i in xrange(y):
        if x[i] < z[i]:
            index = find_index(z[i], i, x)
            x = swap(i, index, x)
    X = int(''.join([str(i) for i in x]))
    print X

import java.util.Scanner;

public class SwapToGetMaxNumber {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		
		int M = s.nextInt();
		int K = s.nextInt();
		
		//Assuming k<= len(M)
		System.out.println(getMax(Integer.toString(M),K));
		
	}

	private static String getMax(String m, int k) {
		if (k==0)
			return m;
		char[] chArr = m.toCharArray();
		int maxPos =0;
		
		for(int i=0;i<chArr.length;i++){
			if (chArr[i]>chArr[maxPos])
				maxPos=i;
		}
		char t = chArr[0];
		chArr[0]=chArr[maxPos];
		chArr[maxPos]=t;
		
		return chArr[0] + getMax(new String(chArr).substring(1),k-1);
	}
}

This code (Scala) prints all combinations. Instead on print we can just get hold of the max and print that one.


val a = Array(8,7,9,9, 0, 9, 6, 5, 4, 9, 9)
val n = 2

def swapz(a: Array[Int], n: Int, idx: Int) : Unit = {
if (n==0) {
println(a mkString(","))
return
}

val bigs = a.drop(idx).max
for((x, i) <- a.view.zipWithIndex) {
if (x == bigs && i >= idx) {
val cp = a.map(i=>i).array
cp(i) = cp(idx)
cp(idx) = x
swapz(cp, n - 1, idx + 1)
}
}
}

swapz(a, 3, 0)

def swap2large(num, K):
nlen = len(num)
for i in range(0, nlen):
if K <= 0:
break;
cmax = num[i]
count = 0
found = False
swappos = i
for j in range(i + 1, nlen):
if num[j] > cmax:
cmax = num[j]
count = 1
swappos = j
elif num[j] == cmax and count > 0:
count += 1

if count == 0:
break

if count == 1:
num[i], num[swappos] = num[swappos], num[i]
K -= 1
continue

for j in range(i + 1, nlen):
if num[j] == cmax:
swappos = j
if found and K > 1:
break
elif num[j] < num[i]:
found = True


num[i], num[swappos] = num[swappos], num[i]
K -= 1
return num


print(swap2large([1, 3, 2], 1))
print(swap2large([1, 3, 2], 2))
print(swap2large([7, 8, 9, 9], 2))
print(swap2large([8, 7, 9, 9], 2))
print(swap2large([7, 8, 9, 9], 1))
print(swap2large([8, 7, 9, 9], 1))

I am not sure how correct the solution is but it works for almost all cases mentioned here

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	static int[] getMax(int[] inp,int k)
	{
		for(int i=0;i<k;i++)
		{
			int max=inp[i];
			int maxind =i;
			int min=inp[i];
			int minind =i;
			int l=0;
			for(int j=i;j<inp.length;j++)
			{
				if(inp[j]>=max)
				{
					maxind = j;
					max = inp[j];
				}
			}
			for(int j=i;j<inp.length;j++)
			{
				if(inp[j]==max)
				{
					l++;
				}
			}
			
			for(int j=0;j<i+l;j++)
			{
				if(inp[j]<min)
				{
					minind = j;
					min = inp[j];
				}
			}
			System.out.println(maxind+":"+minind);
			inp = swap(inp,maxind,minind);
		}
		return inp;
	}
	static int[] swap(int[] inp,int i, int j)
	{
		int temp = inp[i];
		inp[i] = inp[j];
		inp[j] = temp;
		return inp;
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		int[] in = {1,2,3,4};
		int[] out = getMax(in,2);
		for(int k=0;k<out.length;k++)
		{
			System.out.print(out[k]);
		}
		
	}
}

#include<iostream>

using namespace std;

void klargest(int a[], int len, int k){
for(int i=0; i<k; i++){
int maxInd = i;
for(int j=i+1; j<len;j++){
if(a[j]>a[maxInd])
maxInd = j;
}

int temp = a[i];
a[i] = a[maxInd];
a[maxInd] = temp;
}
for(int i=0; i<len; i++)
cout<<a[i]<<" ";
cout<<endl;
}

int main(){
int a[4]={8,7,9,9};
for(int i=0; i<4; i++)
cout<<a[i]<<" ";
cout<<endl;
int k;
cout<<"Enter K"<<endl;
cin>>k;
klargest(a,4,k);

}

#include<iostream>

using namespace std;

void klargest(int a[], int len, int k){
    for(int i=0; i<k; i++){
        int maxInd = i;
        for(int j=i+1; j<len;j++){
            if(a[j]>a[maxInd])
                maxInd = j;
        }
        
        int temp = a[i];
        a[i] = a[maxInd];
        a[maxInd] = temp;
    }
    for(int i=0; i<len; i++)
        cout<<a[i]<<" ";
    cout<<endl;
}

int main(){
    int a[4]={8,7,9,9};
    for(int i=0; i<4; i++)
        cout<<a[i]<<" ";
    cout<<endl;
    int k;
    cout<<"Enter K"<<endl;
    cin>>k;
    klargest(a,4,k);

}

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;


public class Tester {
	
	
	public static void main(String args[]){
	
		List<Integer> digitsOfNumber=  getDigits(7899);
		
		int swapCount = (int)(getMaxBySwapping(digitsOfNumber));
		System.out.println(swapCount);
		
		
	}



	private static float getMaxBySwapping(List<Integer> digitsOfNumber) {
		
		
		List<Integer> processingList = new ArrayList<Integer>(digitsOfNumber);
		List<Integer> maxIntegerOrder = new ArrayList<Integer>();
		int size = digitsOfNumber.size();
		String s = "";
		float numberOfSwaps = 0;
		
		for(int i = 0;i<size;i++){
			Integer maxDigit = (getMaxDigit(processingList));
			maxIntegerOrder.add(maxDigit);
			processingList.remove(maxDigit);
		}
		
		for(int i=0;i<size;i++){
			
			if(! maxIntegerOrder.get(i).equals(digitsOfNumber.get(i)))
				numberOfSwaps+=0.5;
		}
		
		return numberOfSwaps;
		
	}



	private static Integer getMaxDigit(List<Integer> digitsOfNumber) {
		 int max = 0;
		 for(int i =0;i<digitsOfNumber.size();i++){
			 if(digitsOfNumber.get(i)>max){
				 max = digitsOfNumber.get(i);
			 }
		 }
		 return max;
	}



	private static List<Integer> getDigits(int i) {
		List<Integer> digitsOfNumber = new Stack<Integer>();
		while(i >0){
			digitsOfNumber.add(i%10);
			i = i/10;
		}
		Collections.reverse(digitsOfNumber);
		return digitsOfNumber;
	}
	

	
		
	

}

void maxString(char *num, int swaps) {
  while (swaps > 0 && num != '\0') {
    char max = num[0];
    int maxIndex = 0;
    for (i = 1; i < swaps && num[i] != '\0'; i++) {
      if (num[i] > max) {
        max = num[i];
        maxIndex = i;
      }
    }
    memmove(num, num + 1, maxIndex);
    swap -= maxIndex;
    num++;
  }
}

This question is K level DFS. We may use recursive calls with depth of K to solve it.

// N digit value is stored as digit vector. 
int findMax(vector<int>& value, int K)
{
	// hashmap to record the swap history and to mark if the value has been traversed
	hash_map<int, int> swapHist; 
	int max = getValue(value);  // convert the digit vector to integer value
        swapHist[max] = -1; // end point
	findMaxRecur(value, K, max, swapHist);  // each level down, K is reduced by one
        printSwap(max, swapHist);
        return max;
}

void findMaxRecur(vector<int>& value, int k, int& max, hash_map<int, int>& swapHist)
{
	if ( k == 0 )
		return;
	int n = value.size();
	int curVal = getValue(value);
	for ( int i = 0; i < n-2; ++i )
	{
		for ( int j = i+1; j < n -1 ; ++j )
		{
			// perform one swap
			int vi = value[i];
			int vj = value[j];
			value[j] = vi;
			value[i] = vj;
			int newVal = getValue(value);
			if ( swapHist.find(newVal) == swapHist.end()) // node has not been visited
			{
				if ( newVal > max )
					max = newVal; 
				swapHist[newVal] = curVal;
				findMaxRecur(value, k-1, max, swapHist); // go to one level down
			}
			value[i] = vi;
			value[j] = vj; // restore the value vector
		}
	}
}
int getValue(const vector<int>& value)
{
	int val = 0;
	for (int i = 0; i < value.size(); ++i )
	{
		val *= 10;
		val += value[i];
	}
	return val;
}
void printSwaps(const vector<int>& value, const hash_map<int, int>& swapHist)
{
	list<int> hist;
	int val = getValue(value);
	int prevVal = swapHist[val];
	while ( prevVal != -1 )
	{
		hist.push_fron(prevVal);
		prevVal = swapHist(prevVal);
	} // reverse the history 
	std::cout << " Swaps: " 
	for ( list<int>::iterator it = hist.begin(); it != hist.end(); ++it )
		std::cout << *it << " -> ";
	std::cout <<  val << std::endl;
}

i think just like this for example "1234976" find the biggest continous two digits(if both of them are bigger than the first digit ,we beleve it is continous: 9>1,7>1) and then swap it with the first,
The result is: 97 23416

The left part(23416) recursive using the above method.

If we find the digit that is not continous, we just swap it with the first (6>1),
The result is 97 (6 3412)


Time is O(n^2)

1 setup a vector<int> freq[10] to record frequency and index of each digit, scan the input once to record, now we know each digit's correct position of descendant order
2 from 9~0 in freq array fetch first 2*K digit which is not in his correct position, unless get to latest digit.
3 loop these 2*K digit in descendant order, if current is not in his correct position, just swap the digit with the one in his correct position, each time we switch, swapcount ++. (note during this step, some digit which is not in correct position previously could be swapped to his correct position, so that's why 2*K is necessary)
4 if swapcount reach K, return.

I have crafted a solution of O(N) + O(K*logK). An implementation of O(N+K) is still possible. Please refer, cpluspluslearning-petert.blogspot.co.uk/2014/11/data-structure-and-algorithm-find.html, for more detail. It takes a while to explain what I am doing. So have a coup of tea and read through if interested. Here is the code.

#include <set>
#include <string>
#include <unordered_map>

const int TOTAL_NUM_OF_DIGITS = 10;

struct SwapPair {
    SwapPair(char src, char dst)
    : a(src < dst ? src : dst),
    b(src > dst ? src : dst)
    {}

    bool operator()(const SwapPair& rhs) const {
        return a == rhs.a && b == rhs.b;
    }

    char a;
    char b;
};

struct SwapPairInfo {
    SwapPairInfo(char src, char dst, size_t f)
    : aLessThanb(src < dst), frequency(f)
    {}

    bool aLessThanb;
    size_t frequency;
};

struct SwapPairHash{
    size_t operator()(const SwapPair& key) const {
        return std::hash<long>()(key.a) ^
            std::hash<long>()(key.b);
    }

    bool operator()(const SwapPair& k1, const SwapPair& k2) const {
        return k1.operator()(k2);
    }
};

// to track the (x,y) and (y,x) pair
typedef std::unordered_map<SwapPair, SwapPairInfo, SwapPairHash, SwapPairHash> SwapPairHashMap;

std::string FindLargestNumber(const std::string& numbers,
                                                   std::vector<size_t> allDigitsMap[TOTAL_NUM_OF_DIGITS])
{
    for (size_t charIdx = numbers.size(); charIdx > 0; --charIdx) {
        assert(numbers[charIdx - 1] >= '0' && numbers[charIdx - 1] <= '9');
        allDigitsMap[numbers[charIdx - 1] - '0'].push_back(charIdx - 1);
    }

    std::string result;
    for (int num = TOTAL_NUM_OF_DIGITS - 1; num >= 0; --num) {
        if (!allDigitsMap[num].empty()) {
            for (size_t index = 0; index < allDigitsMap[num].size(); ++index) {
                result.push_back('0' + num);
            }
        }
    }

    return result;
}

std::string SwapKcharsBySorting(const std::string& numbers, const std::set<size_t>& swapIndices)
{
    size_t digitsCount[TOTAL_NUM_OF_DIGITS] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    for (std::set<size_t>::const_iterator cIter = swapIndices.begin();
                             cIter != swapIndices.end(); ++cIter) {
        ++digitsCount[numbers[*cIter] - '0'];
    }

    std::vector<char> sortedSwapChars;
    for (int num = TOTAL_NUM_OF_DIGITS - 1; num >= 0; --num) {
        if (digitsCount[num] > 0) {
            for (size_t index = 0; index < digitsCount[num]; ++index) {
                sortedSwapChars.push_back('0' + num);
            }
        }
    }

    std::string result(numbers);
    size_t index = 0;
    for (std::set<size_t>::const_iterator cIter = swapIndices.begin();
        cIter != swapIndices.end(); ++cIter, ++index) {
        result[*cIter] = sortedSwapChars[index];
    }

    return result;
}

std::string KswapSolution(const std::string& numbers, const size_t k)
{
    if (k == 0 || numbers.empty()) {
        return numbers;
    }

    std::vector<size_t> digitsMap[TOTAL_NUM_OF_DIGITS];
    const std::string largestNum = FindLargestNumber(numbers, digitsMap);
    assert(largestNum.size() == numbers.size());

    if ((k + 1) >= numbers.size()) {
        // special case to reach the maximal value any way
        return largestNum;
    }


    // find the index to swap
    SwapPairHashMap swapPairHM;
    size_t swapCount = k;
    std::set<size_t> swapIndices;
    size_t tempIndexOfDigitsMap[TOTAL_NUM_OF_DIGITS] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    for (size_t index = 0; index < numbers.size() && swapCount > 0; ++index) {
        if (largestNum[index] != numbers[index]) {
            const SwapPair sp(numbers[index], largestNum[index]);
            SwapPairHashMap::iterator found = swapPairHM.find(sp);
            if (found == swapPairHM.end()) {
               // keep (x,y)
               swapPairHM.insert(std::make_pair(sp,
                    SwapPairInfo(numbers[index], largestNum[index], 1)));
                --swapCount;
                swapIndices.insert(index);
                swapIndices.insert(digitsMap[largestNum[index] - '0'].at(
                    tempIndexOfDigitsMap[largestNum[index] - '0']));
                ++tempIndexOfDigitsMap[largestNum[index] - '0'];
            }
            else {
                bool aLessThanb = numbers[index] < largestNum[index];
                if (found->second.aLessThanb == aLessThanb) {
                    // (x, y) again
                    ++found->second.frequency;
                    --swapCount;
                }
                else {
                    // (y,x) found
                    if (found->second.frequency > 0) {
                        // there is (x,y) available, then do not reduce swapCount
                        --found->second.frequency;
                    }
                    else {
                        // there is not (x,y) available, then change it to (y, x) pair
                        ++found->second.frequency;
                        found->second.aLessThanb = aLessThanb;
                        --swapCount;
                    }
                }

                swapIndices.insert(index);
                swapIndices.insert(digitsMap[largestNum[index] - '0'].at(
                    tempIndexOfDigitsMap[largestNum[index] - '0']));
                ++tempIndexOfDigitsMap[largestNum[index] - '0'];
            }
        }
    }

    return SwapKcharsBySorting(numbers, swapIndices);
}

// TEST

#include <cassert>
void TestCornerCases()
{
    assert(KswapSolution("", 1).empty());
    assert(KswapSolution("9", 1) == "9");
    assert(KswapSolution("19", 1) == "91");
    assert(KswapSolution("19", 0) == "19");
    assert(KswapSolution("1234", 3) == "4321");
    assert(KswapSolution("119798699", 8) == "999987611");
}

void TestCases()
{
    assert(KswapSolution("132", 1) == "312");
    assert(KswapSolution("132", 2) == "321");
    assert(KswapSolution("7899", 2) == "9987");
    assert(KswapSolution("8799", 2) == "9987");
    assert(KswapSolution("1189119999", 5) == "9999981111");
    assert(KswapSolution("191899", 3) == "999811");
    assert(KswapSolution("191899", 2) == "999811");
    assert(KswapSolution("34155", 2) == "55143");
    assert(KswapSolution("12520", 2) == "52210");
    assert(KswapSolution("876959", 3) == "998756");
    assert(KswapSolution("6899459999", 5) == "9999998654");
    assert(KswapSolution("68994579999", 5) == "99999987654");
    assert(KswapSolution("689984599382999", 5) == "999999988382654");
    assert(KswapSolution("68994593999", 5) == "99999986543");
    assert(KswapSolution("68994597999", 5) == "99999987654");
    assert(KswapSolution("689945932999", 5) == "999999862543");
    assert(KswapSolution("876959", 2) == "996857");
    assert(KswapSolution("123456789098765432199998888777777266655", 350)
                == "999999888888777777776666655554433222110");
    assert(KswapSolution("123456789098765432199998888777777266655", 35)
                == "999999888888777777776666655554433222110");
    assert(KswapSolution("123456789098765432199998888777777266655", 9)
                == "999999888878765432165438210777777266655");
}

#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

void backtrack(string& a, const string& sorted, string& result, int s, int p);

int main() {
	string a;
	cin>>a;
	string sorted;
	vector<int> count(10,0);
	for(int i=0;i<a.size();i++) {
		count[a[i]-'0']++;
	} 
	int k=0;
	for(int i=9;i>=0;i--) {
		sorted.append(count[i],'0'+i);
	}
	string result="";
	int s;
	cin>>s;
	backtrack(a,sorted,result,s,0);
	cout<<result<<endl;
}

void backtrack(string& a, const string& sorted, string& result, int s, int p) {
	if(s==0 || p>=a.size()) {
		result = max(result,a);
	}
	else if(sorted[p]==a[p]) {
		backtrack(a,sorted,result,s,p+1);
	}
	else {
		for(int i=p+1;i<a.size();i++) {
			if(a[i]==sorted[p]) {
				swap(a[p],a[i]);
				backtrack(a,sorted,result,s-1,p+1);
				swap(a[p],a[i]);
			}
		}
	}
}

public void Maximize(short[] digits, int startInd, int kSwap){
		if(digits == null || startInd < 0){
			return;
		}
		
		// while a swap is possible
		while (kSwap > 0 && startInd <= digits.length - 2)
		{
			int max = -1;
			int maxInd = -1;
			for(int i = startInd; i < digits.length; i++){
				if(digits[i] >= max){
					max = digits[i];
					maxInd = i;
				}
			}
			
			while(startInd < digits.length && digits[startInd] == max){
				startInd++;
			}	
			
			//Swap
			short temp = digits[startInd];
			digits[startInd] = digits[maxInd];
			digits[maxInd] = temp;
		
			kSwap--;
			startInd++;
		}		
	}

public void Maximize(short[] digits, int startInd, int kSwap){}

#include <iostream>
using namespace std;
/*
  Greedy Approach - Selection sort descending order
*/
int Kswap(int num, int k)
{
    
    
    string arr = to_string(num);
    int i, j, min_idx;
    int n =arr.length();
    // One by one move boundary of unsorted subarray
    for (i = 0; i < k; i++)
    {
        // Find the max element in unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++)
          if (arr[j] > arr[min_idx])
            min_idx = j;
 
        // Swap the found max element with the first element
        swap(arr[min_idx], arr[i]);
    }
    
    
    int ans = stoi(arr);
    return ans;
}
 

int main() {
	// your code goes here
	cout<<Kswap(254,2)<<endl;
	cout<<Kswap(132,1)<<endl;
	cout<<Kswap(132,2)<<endl;
	
	return 0;
}

#include <iostream>
using namespace std;
/*
   Approach - Selection sort descending order
*/
int Kswap(int num, int k)
{
    
    
    string arr = to_string(num);
    int i, j, min_idx;
    int n =arr.length();
    // One by one move boundary of unsorted subarray
    for (i = 0; i < k; i++)
    {
        // Find the max element in unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++)
          if (arr[j] > arr[min_idx])
            min_idx = j;
 
        // Swap the found max element with the first element
        swap(arr[min_idx], arr[i]);
    }
    
    
    int ans = stoi(arr);
    return ans;
}
 

int main() {
	// your code goes here
	cout<<Kswap(254,2)<<endl;
	cout<<Kswap(132,1)<<endl;
	cout<<Kswap(132,2)<<endl;
	
	return 0;
}

I dont think we need DFS. Below is my solution with nlogn running time because of sorting step.
Have tried all above examples and they all work correctly.
1. reverse sort the characters and keep in an array, also prepare a positions hashMap against each digit with value as positions of occurrence of that digit (In increasing order).
2. Now create 4 lists. 2 for keeping positions of swapFrom and swapTo, 2 for keeping actual bigger numbers and smaller numbers.
3. run a loop for 0 to number of swaps, do below
I) if swappedIn and swappedOut number are same, dont count it as a swap.
II) insert biggest position of swappedIn number in positionsSwappedFrom so that we can insert smaller numbers at these positions later.
III) positionsSwappedTo, bigger, smaller are simple enough to understand from code.
4. sort the smaller numbers in decreasing orders so that we can insert these in those positions from which bigger numbers came.
5. sort positionsSwappedFrom in increasing order.
6. populate the chars array with help of above 4 lists.
7. create answer string from this chars array.
{{public class Solution {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(swap(sc.next(), sc.nextInt()));
}

public static String swap(String input, int swaps) {
if (input == null || input.length() < 2 || swaps < 1) return input;
char[] chars = input.toCharArray();
Map<Character, List<Integer>> positions = new HashMap<>();

List<Character> sorted = new ArrayList<>();
for (int i = 0; i < chars.length; i++) {
char ch = chars[i];
sorted.add(ch);
if (!positions.containsKey(ch)) {
positions.put(ch, new ArrayList<>());
}
positions.get(ch).add(i);
}
Collections.sort(sorted, Comparator.reverseOrder());

List<Integer> positionsSwappedFrom = new ArrayList<>();
List<Integer> positionsSwappedTo = new ArrayList<>();

int i = -1;
List<Character> bigger = new ArrayList<>();
List<Character> smaller = new ArrayList<>();

while (swaps > 0) {
i++;
if(chars.length <= i) {
break;
}
if (chars[i] == sorted.get(i)) {
continue;
}

List<Integer> charPositions = positions.get(sorted.get(i));
positionsSwappedFrom.add(charPositions.remove(charPositions.size() - 1));
positionsSwappedTo.add(i);
swaps--;
bigger.add(sorted.get(i));
smaller.add(chars[i]);
}

Collections.sort(smaller, Comparator.reverseOrder());
Collections.sort(positionsSwappedFrom);

for(int swap=0; swap<smaller.size(); swap++) {
chars[positionsSwappedTo.get(swap)] = bigger.get(swap);
chars[positionsSwappedFrom.get(swap)] = smaller.get(swap);
}
return new String(chars);
}
}
}}

{{I dont think we need DFS. Below is my solution with nlogn running time because of sorting step.
Have tried all above examples and they all work correctly.
1. reverse sort the characters and keep in an array, also prepare a positions hashMap against each digit with value as positions of occurrence of that digit (In increasing order).
2. Now create 4 lists. 2 for keeping positions of swapFrom and swapTo, 2 for keeping actual bigger numbers and smaller numbers.
3. run a loop for 0 to number of swaps, do below
I) if swappedIn and swappedOut number are same, dont count it as a swap.
II) insert biggest position of swappedIn number in positionsSwappedFrom so that we can insert smaller numbers at these positions later.
III) positionsSwappedTo, bigger, smaller are simple enough to understand from code.
4. sort the smaller numbers in decreasing orders so that we can insert these in those positions from which bigger numbers came.
5. sort positionsSwappedFrom in increasing order.
6. populate the chars array with help of above 4 lists.
7. create answer string from this chars array.
public class Solution {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(swap(sc.next(), sc.nextInt()));
}

public static String swap(String input, int swaps) {
if (input == null || input.length() < 2 || swaps < 1) return input;
char[] chars = input.toCharArray();
Map<Character, List<Integer>> positions = new HashMap<>();

List<Character> sorted = new ArrayList<>();
for (int i = 0; i < chars.length; i++) {
char ch = chars[i];
sorted.add(ch);
if (!positions.containsKey(ch)) {
positions.put(ch, new ArrayList<>());
}
positions.get(ch).add(i);
}
Collections.sort(sorted, Comparator.reverseOrder());

List<Integer> positionsSwappedFrom = new ArrayList<>();
List<Integer> positionsSwappedTo = new ArrayList<>();

int i = -1;
List<Character> bigger = new ArrayList<>();
List<Character> smaller = new ArrayList<>();

while (swaps > 0) {
i++;
if(chars.length <= i) {
break;
}
if (chars[i] == sorted.get(i)) {
continue;
}

List<Integer> charPositions = positions.get(sorted.get(i));
positionsSwappedFrom.add(charPositions.remove(charPositions.size() - 1));
positionsSwappedTo.add(i);
swaps--;
bigger.add(sorted.get(i));
smaller.add(chars[i]);
}

Collections.sort(smaller, Comparator.reverseOrder());
Collections.sort(positionsSwappedFrom);

for(int swap=0; swap<smaller.size(); swap++) {
chars[positionsSwappedTo.get(swap)] = bigger.get(swap);
chars[positionsSwappedFrom.get(swap)] = smaller.get(swap);
}
return new String(chars);
}
}
}}

The logic is fairly simple assuming that the number is stored in an array.So once the number is stored in an array we can modify the bubble sort to run the outer loop only for k times.At the end of the loop,the k largest numbers will be at the end in their appropriate position(see working of bubble sort) After this you can reverse the contents of array to get the maximum possible integer.

package com.algo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SwapToMax {

	private static void swapToMax(List<Integer> values, int k) {

		if (values.size() <= 1 || k == 0) {
			return;
		}

		List<Integer> maxLocations = maxLocations(values);

		Collections.sort(values.subList(0, maxLocations.size()));
		Collections.reverse(values.subList(0, maxLocations.size()));

		int i = 0;
		for (Integer location : maxLocations) {
			int temp = values.get(i);
			values.set(i, values.get(location));
			values.set(location, temp);
			i++;
		}

		swapToMax(values.subList(maxLocations.size() - 1, values.size() - 1), k
				- maxLocations.size());

	}

	private static List<Integer> maxLocations(List<Integer> values) {

		if (values.size() == 0) {
			return Collections.emptyList();
		}

		int max = values.get(0);
		List<Integer> maxLocations = new ArrayList<>();
		maxLocations.add(0);

		for (int i = 1; i < values.size(); i++) {
			if (values.get(i) == max) {
				maxLocations.add(i);
			} else if (values.get(i) > max) {
				maxLocations.clear();
				max = values.get(i);
				maxLocations.add(i);
			}
		}

		return maxLocations;
	}

	public static void main(String[] args) {

		List<Integer> l = new ArrayList<>(Arrays.asList(8, 7, 9, 9));
		int k = 2;
		swapToMax(l, k);
		System.out.println(l);
	}

}

Solution above has too many mistakes...

package com.algo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SwapToMax {

	private static void swapToMax(List<Integer> values, int k) {

		if (values.size() <= 1 || k == 0) {
			return;
		}

		List<Integer> maxLocations = maxLocations(values, k);

		Collections.sort(values.subList(0, maxLocations.size()));
		Collections.reverse(values.subList(0, maxLocations.size()));

		int i = 0;
		for (Integer location : maxLocations) {
			int temp = values.get(i);
			values.set(i, values.get(location));
			values.set(location, temp);
			i++;
		}

		swapToMax(values.subList(maxLocations.size(), values.size()), k
				- maxLocations.size());

	}

	private static List<Integer> maxLocations(List<Integer> values, int k) {

		if (values.size() == 0) {
			return Collections.emptyList();
		}

		int max = values.get(0);
		List<Integer> maxLocations = new ArrayList<>();
		maxLocations.add(0);

		for (int i = 1; i < values.size(); i++) {
			if (values.get(i) == max) {
				maxLocations.add(i);
			} else if (values.get(i) > max) {
				maxLocations.clear();
				max = values.get(i);
				maxLocations.add(i);
			}
		}

		int maxAllowed = Math.min(k, values.size() / 2);
		while (maxLocations.size() > maxAllowed) {
			maxLocations.remove(0);
		}

		return maxLocations;
	}

	public static void main(String[] args) {

		List<Integer> l = new ArrayList<>(Arrays.asList(1, 3, 2));
		int k = 1;
		swapToMax(l, k);
		System.out.println(l);

		l = new ArrayList<>(Arrays.asList(1, 3, 2));
		k = 2;
		swapToMax(l, k);
		System.out.println(l);

		l = new ArrayList<>(Arrays.asList(7, 8, 9, 9));
		k = 2;
		swapToMax(l, k);
		System.out.println(l);

		l = new ArrayList<>(Arrays.asList(8, 7, 9, 9));
		k = 2;
		swapToMax(l, k);
		System.out.println(l);

	}

}

package google;

import java.util.Scanner;

/**
*
* @author brian
*/
public class Google {

/**
* @param args the command line arguments
*/

int numofdig;
String usernumber;
int number;
Scanner input=new Scanner(System.in);
int inddig[];
int numofswap;
int max;





int sort(int k)
{
int temp;

for(int i=k;i<inddig.length-2;i++)
{
if(inddig[k]>=inddig[k+1])
{
temp=inddig[k];
inddig[k]=inddig[k+1];
inddig[k+1]=temp;
}




}
System.out.println("Sorted Elements");
for(int s=0;s<=inddig.length-2;s++)
{
System.out.println(inddig[s]);
}

return 0;
}


int max(int[] temp,int j)
{
int limit=0;
max=temp[j];
for(int s=0;s<=temp.length-2;s++)
{

System.out.println(temp[s]);
}
for(int p=j;p<=temp.length-2;p++)
{
if(max<temp[p]){
max=temp[p];
limit=p;
}

}
System.out.println("Max Element in Array:"+temp[limit]);
return limit;



}

int breakdig(int temp)
{
int temp1[]=new int[numofdig+1];
int n ;
n=temp;
int i=0;
while(n>0)
{
n=temp%10;

temp1[i]=n;
i++;
temp=temp/10;
}
int k=0;
for(int j=temp1.length-2;j>=0;j--)
{

inddig[k]=temp1[j];
k++;
}



swap();
return 0;



}
int swap()
{
int temp;
int j,i=0;
int k;
while(numofswap>0)
{

sort(i);
j=max(inddig,i);
System.out.println("j="+j);

temp=inddig[i];
System.out.println("i="+i);
inddig[i]=inddig[j];
inddig[j]=temp;

i++;
numofswap--;
}

display();




return 0;






}


int display()
{
for(int s=0;s<=inddig.length-2;s++)
{
System.out.println(inddig[s]);
}
return 0;



}



int getnum(String temp)
{

numofdig=temp.length();
number=Integer.parseInt(temp);
System.out.println("number of digits"+numofdig);
inddig=new int [numofdig+1];
breakdig(number);

return 0;


}

int input()
{

System.out.println("Enter the number");
usernumber=input.next();
System.out.println("Enter the number of swaps");
numofswap=input.nextInt();

getnum(usernumber);




return 0;



}




public static void main(String[] args) {

new Google().input();
// TODO code application logic here
}

}

package google;

import java.util.Scanner;

/**
*
* @author brian
*/
public class Google {

/**
* @param args the command line arguments
*/

int numofdig;
String usernumber;
int number;
Scanner input=new Scanner(System.in);
int inddig[];
int numofswap;
int max;





int sort(int k)
{
int temp;

for(int i=k;i<inddig.length-2;i++)
{
if(inddig[k]>=inddig[k+1])
{
temp=inddig[k];
inddig[k]=inddig[k+1];
inddig[k+1]=temp;
}




}


return 0;
}


int max(int[] temp,int j)
{
int limit=0;
max=temp[j];

for(int p=j;p<=temp.length-2;p++)
{
if(max<temp[p]){
max=temp[p];
limit=p;
}

}

return limit;



}

int breakdig(int temp)
{
int temp1[]=new int[numofdig+1];
int n ;
n=temp;
int i=0;
while(n>0)
{
n=temp%10;

temp1[i]=n;
i++;
temp=temp/10;
}
int k=0;
for(int j=temp1.length-2;j>=0;j--)
{

inddig[k]=temp1[j];
k++;
}



swap();
return 0;



}
int swap()
{
int temp;
int j,i=0;
int k;
while(numofswap>0)
{

sort(i);
j=max(inddig,i);


temp=inddig[i];

inddig[i]=inddig[j];
inddig[j]=temp;

i++;
numofswap--;
}

display();




return 0;






}


int display()
{



String result = "";
for(int s=0;s<=inddig.length-2;s++)
{


result+=String.valueOf(inddig[s]);
}

System.out.println("Ans : "+result);
return 0;



}



int getnum(String temp)
{

numofdig=temp.length();
number=Integer.parseInt(temp);

inddig=new int [numofdig+1];
breakdig(number);

return 0;


}

int input()
{

System.out.println("Enter the number");
usernumber=input.next();
System.out.println("Enter the number of swaps");
numofswap=input.nextInt();

getnum(usernumber);




return 0;



}




public static void main(String[] args) {

new Google().input();
// TODO code application logic here
}

}

40 responses and no one has mentioned heap?

Build a max-heap of size n from the digits. Pop-out the maximum element from the heap, swap it with the left most digit (then shift left-most pointer by one to the right). Repeat k times. Deleting an element from the heap also balances the heap, which is a O(log(heap_size)) operation.

Time complexity: O(n + klogn), space complexity : O(n). Note that any comparison (and swap) based algorithm CANNOT sort an array of size n in less than O(nlogn). If k = n, the time complexity becomes O(nlogn)

How about:
j = 0
WHILE k > 0
Get highest digit (i) position from A in range of [j, digit_count]
New Number := A[i] + A \ {i}
K = K - 1
J = J + 1
END_WHILE

Example:
A=7899 K=2

J = 0
I = [78(9)9] at index 2
A=9[789]

J = 1
I = 9[78(9)] at index = 3
A = 9978