- Prepare
- Algorithms
- Implementation
- Larry's Array
- Discussions

# Larry's Array

# Larry's Array

+ 0 comments I think this problem can be solved by finding the smallest number of swaps so that it becomes an increasing chain, but this number of swaps must be divisible by 2 because in this lesson, each time you swap, you have to swap consecutively. swap 2 times in a row and if those times are numbers that are not divisible by 2 then it will be incorrect because in 1 swap you cannot swap 3 times in a row in 1 time.

int count = 0 ; int n = A.size() ; List<Integer> tempArr = new ArrayList<>(A) ; List<Integer> sorted = new ArrayList<>(A) ; Map<Integer, Integer> indexMap = new LinkedHashMap<>() ; for(int i = 0; i < n ; i++ ) { indexMap.put(A.get(i),i) ; } Collections.sort(sorted) ; for(int i = 0 ; i < n ; i++ ) { if(tempArr.get(i) != sorted.get(i)) { count ++ ; int newValue = tempArr.get(i) ; int newIndex = indexMap.get(sorted.get(i)) ; indexMap.put(newValue, newIndex); Collections.swap(tempArr, i, indexMap.get(sorted.get(i))); indexMap.put(sorted.get(i), i); } } if(count %2 == 0) { return "YES" ; } else { return "NO" ; }

+ 1 comment Let me try to explain the method to solve this problem, instead of just giving the code.

When given any array, for example, 1, 3, 7, 8, 6, 5, 4, 2

find each number in ascending order.

- find the number 1. it is in the correct position already, no need to move
find the number 2, it should move forward. We just need to move number 2 forward each time by jumping over 2 numbers array changes to 1, 2, 3, 7, 8, 6, 5, 4

find the number 3, it is already in the correct position after step 2, no need to move

find the number 4, it should also jump over two numbers each time, array change to 1, 2, 3, 4, 7, 8, 6, 5

after jumping number 5, array change to 1, 2, 3, 4, 7, 5, 8, 6 (jumping over 8, 6 only)

for step 5, swap 7, 5, 8 to change to 1, 2, 3, 4, 5, 8, 7, 6

find number 6, and jump it to change array to 1, 2, 3, 4, 5, 6, 8, 7

this result shows the array could not be ordered finally, return "NO".

For the above step b, think about why we should make the number 2 jump over two numbers every time. That is the key of the question.

+ 0 comments *hemlo everyone*

+ 1 comment is that example wrong or I 'm not understanding the problem correctly? the rotation of [5,4,3] can not be performed directly according to problem description, right? 4,3,5 then 3,5,4

A rotate [1,6,5,2,4,3] [6,5,2] [1,5,2,6,4,3] [5,2,6] [1,2,6,5,4,3] [5,4,3] [1,2,6,3,5,4] [6,3,5] [1,2,3,5,6,4] [5,6,4] [1,2,3,4,5,6] YES

+ 1 comment hey can someone help me out with this problem? im new to competitive programming and my friend sent me this. he wants me to solve it but as i said, im still new so can yall teach me? here is the problem https://www.hackerrank.com/newbie-challenge

Sort 326 Discussions, By:

Please Login in order to post a comment