| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
n = 6 a[] = {1, 1, 5, 2, 5, 5} answer = 1 ( swap a[0] with a[4] or a[5] )
n = 8 a[] = {1, 5, 5, 1, 4, 6, 1, 1} answer = 2 (swap a[0] with a[1] and a[5] with a[6] )
n = 8 a[] = {3, 1, 1, 5, 3, 3, 5, 5} answer = 2 (swap a[0] with a[1] and a[5] with a[6] )
indexing from zero in above examples.
Can anyone answer this?
I need also to know answer of this problem
You can solve it using brute force if the limit is smaller than 1e5
What if n up to 1e9 ?
Do you know dp ? I think you can solve it using dp , but I'm not sure . I will think about it, nice problem : ).
I know DP , But DP Work if limit is short , It won't work
Sad :') if n is 1e5 will it work ? right?
I Think Also no , It won't work with dp
Do you know dp better than n^2?
Most things better than n^2 will work for 1e5
right? , I didn't solve problems using dp.
I don't Know dp will solve this problem better than n^2
If You solve it using DP
using memoization you need to loop to all who is adjacent is same element as them then Swap it and make answer will be minimum of all recurrences.
In Worst Case it will be O(n^2)
First make boolean array its name is vis after that ,We Can make Memoization Function Starting From First Element that its Adjacent element has same value and inside Function we will loop to adjacent elements that have same value and if we found element then increase answer by one and vis[i] = true , and swap element and make recursion on it.
The Complexity of This in worst Case is O(n^2)
Bakry Hi, I am not able to understand how memoization is working here, could you please explain it in a little more detail please? Thank You in advance :)
Btw, this question was asked on an onsight google interview recently.
my comment is from 3 years, I don't remember any details and I think my solution was wrong.
Your Welcome :)
I will ask also Tomorrow about solution that will work well if n equal 10 ^ 9
I didn't Find Solution For This Problem.
Did you find any solution ?
No I can't answer it with dp better than n^2