Google Interview Question
SDE-2sCountry: India
also a correct solution, using std::map, with one round of greedy swap
#include <stdio.h>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <algorithm>
#define BUFFER_SZ 100
bool cmp(char * one, char * two)
{
return strcmp(one, two) > 0;
}
void greedySwap(char * input, int k, char * result)
{
memset(result, 0, BUFFER_SZ);
strcpy_s(result, BUFFER_SZ, input);
char * str = new char[2];
str[1] = '\0';
for (int j = 0; j < k; ++j)
{
char max = -1;
int index = -1;
if (k > strlen(result))
{
return;
}
for (int z = j; z < j+strlen(result + j); ++z)
{
str[0] = result[z];
if (atoi(str) > max)
{
max = atoi(str);
index = z;
}
}
char temp = result[index];
result[index] = result[j];
result[j] = temp;
}
}
void swap(char * input, int k, char *& result)
{
greedySwap(input, 1, result);
if (k == 1)
{
return;
}
--k;
std::map<char *, int, bool(*)(char*, char*)> swaps (cmp);
std::map<char *, int, bool(*)(char*, char*)> numbers (cmp);
int len = strlen(result);
numbers.insert(std::make_pair(result, 1));
while (k >= 0)
{
for (std::map<char *, int>::iterator it = numbers.begin(); it != numbers.end(); ++it)
{
char * pCurrent = it->first;
for (int i = 1; i < len; ++i)
{
for (int j = i+1; j < len; ++j)
{
if ( pCurrent[i] != pCurrent[j])
{
char * pNext = _strdup(pCurrent);
pNext[i] = pCurrent[j];
pNext[j] = pCurrent[i];
if (!(swaps.insert(std::make_pair(pNext, 1))).second)
{
delete pNext;
}
}
}
}
}
for (std::map<char *, int>::iterator it = numbers.begin(); it != numbers.end(); ++it)
{
delete it->first;
}
numbers.clear();
numbers.swap(swaps);
--k;
}
result = new char[100];
strncpy_s(result, BUFFER_SZ, numbers.begin()->first, BUFFER_SZ);
for (std::map<char *, int>::iterator it = numbers.begin(); it != numbers.end(); ++it)
{
delete it->first;
}
}
int main(int argc, char * argv[])
{
char * result = new char[BUFFER_SZ];
char * one = "132";
swap(one, 1, result);
printf("one: %s \n", result); // output = 312
char * two = "132";
swap(two, 2, result);
printf("two: %s \n", result); //output = 321
char * three = "7899";
swap(three, 2, result); //output 9987
printf("three: %s \n", result);
char * four = "8799";
swap(four, 2, result); // output 9987
printf("four: %s \n", result);
char * five = "1189119999";
swap(five, 5, result);
printf("five: %s \n", result); // output 9999981111.
system("pause");
delete result;
return 0;
}
Another greedy algorithm takes O(n^2) time, but it can only provides a merely correct answer.
Assume the digits are stored in array num[].
for(int i=0; i<num.length(), k>0; i++, k--){
1. each time, find the rightmost largest digit among num[i+1,...,length-1]. Let's say it is it is num[large_pos].
2. if num[large_pos] equals num[i], then i++. until found a i, where num[i]<num[large_pos].
3. swap(num[i], num[large_pos])
}
An example is 1289349999, k is 4
1289349999
^ ^
9289349991
^ ^
9989349921
^ ^
9999349821
^ ^
9999349821
^ ^
9999943821
^
Each time, it gives a best solution from current to next step. But it doesn't guarantee a global best solution.
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++;
}
}
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)
improved solution in python.
Complextiy: time O(N)+O(k log k), space O(N)
import heapq
def kswaps(m, k):
def kswaps_int(digit, pos, k):
l=[]
for i in xrange(pos, len(m)):
if m[i]==digit:
l.append(i)
c=len(l)
h=[]
while c>0 and pos<len(m):
if m[pos]<digit:
heapq.heappush(h, (m[pos], pos))
c-=1
pos+=1
while len(h)>0:
vd, vp = heapq.heappop(h)
ip = l[-1]
if ip>vp:
m[ip], m[vp] = m[vp], m[ip]
l.pop()
k-=1
else:
pos-=1
return pos, k
pos=0
digit=9
while k>0 and digit>=0:
pos, k = kswaps_int(digit, pos, k)
digit-=1
def main():
m=[7, 9, 8, 6, 5, 9, 9, 9]
k=3
print m, k
kswaps(m, k)
print m
if __name__ == "__main__":
main()
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.
I think you have flaw in your solution.
consider next example : 1189119999 and k = 5;
The correct answer will be 9999981111.
Your algorithm on step c will get all indexes of '9' {3,6,7,8,9} , on step d indexes of 5 lower digits while skipping '9'th {0,1,2,4,5}.
Then you starting swap digits in ascending order with 9th from right to left.
It will give you 9998991111.
The problem is with last 9. After 4 swap operation and before last one your number looks like 99 "89" 991111, ( i put in quotes the only unswapped digits ). The correct answer achieved by swap 8 with already used in swap '9'.
The solution i think is to remember how much digits you skipped in step d, lets say it x digits, and after k-x swap operations, do next x swaps with the already swapped '9'th from right to left
EDIT :
No, my solution won't work too.
consider 191899 k = 3
after two swaps 999811 , it is allready maximum , now my solution will do last swap and will make it 998911.
We can solve it if we will check that we are not swapping 9 to lower index, but i am not sure i see all the problems with this algorithm,
EDIT 2:
It seems this greedy algorithm is working.
code :
#include "kswap.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
using namespace std;
class comp {
public:
bool operator() (pair<int, int> a, pair <int,int> b)
{
if (a.first == b.first)
{
return a.second > b.second;
}
return a.first > b.first;
}
};
vector<int> getIndexesOfCurrentDigit(int curr_digit, int k, vector <int> *vec)
{
vector <int> indexes;
for (int i = (int)vec->size() -1 ; i > 0 ; i--)
{
if ( (int)indexes.size() == k )
{
return indexes;
}
if ((*vec)[i] == curr_digit)
{
indexes.push_back(i);
}
}
return indexes;
}
vector<pair<int,int>> getHeapOfLowerDigits(int curr_digit, int size, int k, vector <int> *vec ,int *x)
{
vector <pair<int,int>> heap;
for (int i = 0; i < vec->size(); i++)
{
if (heap.size() == size)
{
make_heap(heap.begin(),heap.end(), comp());
return heap;
}
if ((*vec)[i] <= curr_digit)
{
if ((*vec)[i] < curr_digit)
{
heap.push_back(make_pair((*vec)[i],i));
}
else
{
(*x)++;
}
}
}
make_heap(heap.begin(),heap.end(), comp());
return heap;
}
void carefullSwap(vector<int> indexes, vector<pair<int,int>> heap, int curr_digit,int x, int *k, vector <int> *vec)
{
int high_digit_index, lower_digit_index = 0;
int swaps = 0;
int i = 0;
int size = (int)heap.size();
while(heap.empty() == false)
{
high_digit_index = indexes[i++];
lower_digit_index = heap.front().second;
pop_heap(heap.begin(), heap.end(), comp());
heap.pop_back();
//swap
if(lower_digit_index < high_digit_index )
{
int tmp = (*vec)[high_digit_index];
(*vec)[high_digit_index] = (*vec)[lower_digit_index];
(*vec)[lower_digit_index] = tmp;
swaps++;
}
if(swaps == (size - x) )
{
indexes = getIndexesOfCurrentDigit(curr_digit, *k, vec);
i = 0;
}
}
*k = *k - swaps;
}
void kswap (vector <int> * vec , int k)
{
for (int curr_digit = 9 ; curr_digit > 1 ; curr_digit--)
{
if (k == 0)
{
return;
}
int x = 0;
vector<int> indexes = getIndexesOfCurrentDigit(curr_digit, k, vec);
vector<pair<int,int>> heap = getHeapOfLowerDigits(curr_digit,(int)indexes.size(), k, vec , &x);
carefullSwap(indexes, heap, curr_digit, x, &k, vec);
}
}
Testing:
k - 2
input - 8799
output - 9987
k - 2
input - 7899
output - 9987
k - 2
input - 34155
output - 55143
k - 2
input - 12520
output - 52210
k - 3
input - 876959
output - 998657
k - 2
input - 1399
output - 9931
k - 5
input - 1189119999
output - 9999981111
k - 5
input - 191899
output - 999811
k - 350
input - 123456789098765432199998888777777266655
output - 999999888888777777776666655545433222110
k - 35
input - 123456789098765432199998888777777266655
output - 999999888888777777143216650775432266655
k - 9
input - 123456789098765432199998888777777266655
output - 999999888858765432143218760777777266655
Program ended with exit code: 0
EDIT 3 the last one.
No this solution doesn't work either. I got to conclusion you can't do it with greedy algorithm. You have to do some routines recursively
If someone could tell me how easily i can come to conclusion that some problem can't be solved greedy, i will appreciate it.
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);
}
I think this greedy algorithm does not give correct solution to the test case : "M = 8799 and K = 2 output = 9987".
agree, there is no way to solve this greedely.
Below I provided the recursive solution (not the first one to provide it, though) with deep explanation of steps.
#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.
Simplification. Do not need array because doing one index at a time. Just backward index, but start from end at every state decrement
/*
* 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;
}
Alisovenko,
Thank you for leaving feedback.
why is my int conversion incorrect? It works in eclipse.
My out works for all inputs in the question and potentially inputs I see on this page.
Example of output:
In M is 876959, K is 3
Output: 998657
sorry, conversion is correct, I thought each decimal will be converted to direct ASCII symbol 1.
check inputs 8799 and 7899 they must provide the same result for k=2
Alisovenko,
Again, Thank you for leaving feedback. You are correct, my solution is incorrect!! (See below). So this means my Java algorithm finds a suboptimal solution. Is it best to find all suboptimal solutions, then select the best solution from there?
Output:
In M is 8799, K is 2
Output: 9987
In M is 7899, K is 2
Output: 9978
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--;
}
}
In step 4, if array is {8, 7, 9, 9} or {7, 8, 9, 9} and k = 2, we will swap 8 to the first occurrence of 9, swap 7 to the second occurrence. So, it is the same as we sort the element which will be swap to the larger digits, then swap the element with the larger number one by one.
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))
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;
}
}
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++;
}
}
#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);
}
}
Input: 8, 7, 6, 9, 5, 9 and k=3
You get: 9, 9, 8, 6, 5, 7.
Optimum: 9, 9, 8, 7, 5, 6 (swap 8 with 6, then 6 with the rightmost 9 and then 7 with the middle 9)
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)
You're no considering that some numbers could already be in the correct position, thus they must not be swapped, i.e., [ 8, 7, 4, 2, 3 , 5 ], k = 1.
Also you CANNOT build a heap of size n in less than O(nlogn).
This is a DFS algorithm which gives correct results. Not sure how to improve this by smart algorithms.
- zect October 05, 2014