## moizik

BAN USERI 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.

inhnnsoc , you are absolutely right. I think there a minor defect in a icomputational solution.

Score should start from zero every time we encounter a 'b' , this is how we can determine the longest sequence of consecutive 'a' .

So the algorythm should be

1. find first 'b'

2. from the next position after the first 'b', find the maximum continuous sub list of 'a'

3. if it is longer than prefix sequence (from start to first b) then reverse the first 'b' and the end of maximal subsequence of 'a'

here is correct code and results for your example

```
def maxswap(clist):
clen = len(clist)
i, j = 0, 0
while i < clen:
if clist[i] == 'b':
break
i += 1
if i == clen:
return [0, 0]
val = - i # first fix, initial val should represent length of starting
# 'a' sequence
rj = i
cval = 0
for j in range(i + 1, clen):
if clist[j] == 'a':
cval += 1
else:
cval = 0 # second fix , we should start over calculation
# when we see 'b'
if cval > val:
rj = j
val = cval
if rj == i:
return [0, 0]
return [i, rj]
print ( maxswap ( 'baaabaabbbbbb' ) )
print ( maxswap ( 'baabaaabbbbbb' ) )
```

output:

kirillmoizik$ python test.py

[0, 3]

[0, 6]

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

define array[100]

- moizik October 23, 2014run over data and for each entry lower than 100 set array[current_number] = 1

then run over data secondly and for every entry lookup if complementary number exist in array.

o(n) time

0(1) place