A zero-indexed array A is defined, consisting of N different integers. In the range [1..(N + 1)], the array contains integers, indicating that exactly one element is missing.
For example, in array A such that:
For example, given array A such that:
- A[0] = 2
- A[1] = 3
- A[2] = 1
- A[3] = 5
the function should return 4, as it is the missing element.
Let’s write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- the elements of A are all distinct;
- each element of array A is an integer within the range [1..(N + 1)]
Solution:
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
| fun main(args: Array<String>) {
println("\${solution(intArrayOf(3,1,2,4,3))}")//4
println("\${solution(intArrayOf(2,3,1,5,4,8,7))}")//6
println("\${solution(intArrayOf(2,3,1,5,7,8,6,4))}")//9
}
//takes more time
fun solution1(A: IntArray): Int {
println("input: \${A.contentToString()} ")
var diff: Int? = null
val N = A.size
for (i in 0 until N-1) {
println("element: \${A[i]} ")
val firstArray = A.sliceArray(0..i+1-1)
val secondArray = A.sliceArray(i+1 until N)
var temp = Math.abs(firstArray.sum() - secondArray.sum())
if (diff == null) diff = temp
if (temp < diff)
diff = temp
}
return diff ?: 0
}
//takes less time
fun solution(A: IntArray): Int {
println("input: \${A.contentToString()} ")
//size = 5
var diff: Int? = null
val N = A.size -1 //4
var leftArray = IntArray(N)
var rightArray = IntArray(N)
var temp = 0
for (i in 0 until N) {
temp = temp + A[i+1-1]
leftArray[i] = temp
}
temp = 0
for (i in A.size -1 downTo 1) {
temp = temp + A[i]
rightArray[i-1] = temp
var temp = Math.abs(leftArray[i-1] - temp)
if (diff == null) diff = temp
if (temp < diff)
diff = temp
}
return diff ?: 0
}
}
|