FilesExpand file tree

 master

/

Partitionnarray.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (36 loc) · 1 KB

 master

/

Partitionnarray.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

49 lines (36 loc) · 1 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/*

Given an array with integers, find the index to minimize the difference between

left part sum and right part sum, not including the index number itself, return the position of the integer.

*/

/*

solution: Calculate the sum of array. Scan the array, maintain a left sum and right sum, and record the minimal difference.

O(n) time, O(1) space

*/

#include<iostream>

#include<cassert>

using namespace std;

int Partition(int arr[], int len) {

assert(arr && len >0);

int sum = 0;

for (int i = 0; i < len; ++i) {

sum += arr[i];

}

int pos = -1;

int diff = INT_MAX;

int left = 0;

for (int i = 0; i < len; ++i) {

int right = sum - left - arr[i];

if (abs(right - left) < diff) {

pos = i;

diff = abs(right - left);

}

left += arr[i];

}

return pos;

}

int main(){

int arr[]= {1, 5, 7, 12, 10, 11, 7, 5, 1};

int len = sizeof(arr)/sizeof(arr[0]);

cout<<Partition(arr, len)<<endl;

return 0;

}