TapeEquilibrium

May 14, 2022

A non-empty zero-indexed array A is given consisting of N integers. On a tape, Array A represents numbers. Any integer P, such as such that 0 < P < N, divides the tape into two non-empty sections: A\[0], A\[1], …, A\[P − 1], A\[P], A\[P + 1], …, A\[N − 1]. The value of the difference between the two components is: |(A\[0] + A\[1] + … + A\[P − 1]) − (A\[P] + A\[P + 1] + … + A\[N − 1])|| It is the total difference, in other words, between the sum of the first part and the sum of the second part.

For example, in array A such that:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

We can split this tape in four places:

*P = 1, difference = |3 − 10| = 7

*P = 2, difference = |4 − 9| = 5

*P = 3, difference = |6 − 7| = 1

*P = 4, difference = |10 − 3| = 7

Write a function:

int solution(int A[], int N);

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

the function should return 1, as explained above.

Let’s write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].

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
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
    }
}

TapeEquilibrium

Tags :

Related Posts

Binary Gap

Find the missing element in a given permutation

Rotate Array

TapeEquilibrium

Tags :

Share :

Related Posts

Binary Gap

Find the missing element in a given permutation

Rotate Array