# Circus Raju

Raju performs various Circus feats in his show. One of them is Magic Bar balancing act (Magic bar, assume it as a long rod). In this feat, he tries to balance the magic bar by placing different weights at equal distances. Balancing point need not be the center of the Bar. He can successfully balance the bar if left and right side weights differ by no more than x kgs(let’s calls this margin of error). Being a Magic bar, it automatically adds an additional 1 kg for each weight on the left side of balancing point.
Please write a program to determine the outcome of the feat. If he can perfectly balance the magic bar, print “Perfectly Balanced”. If he can balance within the margin of error(y) print “Balanced within (y)”, otherwise print “Not Balanced”. In case where Raju can balance the bar in multiple ways,  please select the one with minimum margin of error(y).
(Please note that Raju can place a given weight on the bar either on the right or left hand side depending upon his convenience. While solving the problem please ignore the effects of distance of the weights from the balancing point)

Input Format with explanation:
1. Number of elements in the array
2. All weights are given as an array of integers (Each weight is given in new line)
3. Margin of error (x)
Output Format with explanation:
1. Outcome of the feat

Input 1:
6
6

2

1

4

3

5
1
Output:
Perfectly Balanced (1,3,5 on left side; 2,4,6 on right side; 1+3+5+3(for 3 weights) = 2+4+6)

Input 2:
5
20

10

4

50

100
20
Output:
Balanced within 12 (20,10,4,50 on left side and 100 on right side; 20+10+4+50+4 (for 4 weights) on left side = 88, right side 100. so Balancing within 12)

### Solution

```
import java.util.Arrays;

/**
* Created by 611217002 on 8/8/2017.
*/
public class CircusRaju {

public static void main(String[] args) {

int[] array = {6, 2, 1, 4, 3, 5};
System.out.println(circusRaju(array, 1));

}

public static String circusRaju(int[] array, int marginOfError) {

Arrays.sort(array);
int leftSum = 0;
int rightSum = 0;
for (int i = array.length - 1; i >= 0; i--) {

if (rightSum <= leftSum) {
rightSum += array[i];
} else {
leftSum += array[i] + 1;
}

}

int margin;
if (leftSum > rightSum)
margin = leftSum - rightSum;
else
margin = rightSum - leftSum;

if (margin == 0)
return "Perfectly Balanced";
if (margin <= marginOfError)
return "Balanced within " + margin;
return "Not Balanced";

}

}

```