HackerRankStuff/minimum_swaps_2.py at master · elenalind/HackerRankStuff · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
###################
# Minimum Swaps 2 #
# You are given an unordered array consisting of consecutive integers  [1, 2, 3, ..., n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.
#
# For example, given the array  we perform the following steps:
#
# i   arr                         swap (indices)
# 0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
# 1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
# 2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
# 3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
# 4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
# 5   [1, 2, 3, 4, 5, 6, 7]
# It took  swaps to sort the array.
#
# Function Description
#
# Complete the function minimumSwaps in the editor below. It must return an integer representing the minimum number of swaps to sort the array.
#
# minimumSwaps has the following parameter(s):
#
# arr: an unordered array of integers
# Input Format
#
# The first line contains an integer, , the size of .
# The second line contains  space-separated integers .
#
# Constraints
#
# Output Format
#
# Return the minimum number of swaps to sort the given array.
#
# Sample Input 0
#
# 4
# 4 3 1 2
# Sample Output 0
#
# 3
# Explanation 0
#
# Given array
# After swapping  we get
# After swapping  we get
# After swapping  we get
# So, we need a minimum of  swaps to sort the array in ascending order.
#
# Sample Input 1
#
# 5
# 2 3 4 1 5
# Sample Output 1
#
# 3
# Explanation 1
#
# Given array
# After swapping  we get
# After swapping  we get
# After swapping  we get
# So, we need a minimum of  swaps to sort the array in ascending order.
#
# Sample Input 2
#
# 7
# 1 3 5 2 4 6 8
# Sample Output 2
#
# 3
# Explanation 2
#
# Given array
# After swapping  we get
# After swapping  we get
# After swapping  we get
# So, we need a minimum of  swaps to sort the array in ascending order.


#!/bin/python

import math
import os
import random
import re
import sys

# Complete the minimumSwaps function below.
def minimumSwaps(arr):
    l = []
    l = list(arr)
    count = 0
    temp = 0
    x = 0
    for i in range(0,len(l)-1):
        for j in range(0,len(l)-1):
            if l[j] == j+1:
                j += 1
            elif l[j] != j:
                x = l[j]
                y = l[l[j]-1]
                l[l[j]-1] = x
                l[j] = y
                count += 1
    return count

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(raw_input())

    arr = map(int, raw_input().rstrip().split())

    res = minimumSwaps(arr)

    fptr.write(str(res) + '\n')

    fptr.close()