Given an input integer array arr. The pivot point of the array is the element such that the sum of all array elements to the left of the pivot point is equal to sum of all elements to the right of the pivot point.
| Input Parameters |
Expected outputs |
| arr={ 1,2,3,4,9,-3}
|
Pivot point index is 3.
Pivot point element is 4.
|
| arr={4,5,4}
|
Pivot point index is 1.
Pivot point element is 5.
|
| arr={1,3,5,7,3,5,1}
|
Pivot point index is 3.
Pivot point element is 7.
|
| arr={1,-1,3}
|
Pivot point index is 2.
Pivot point element is 3.
Note: sum of all index > arr.length-1 is assumed to be 0. Similarly sum of all index <0 can also be assumed to be 0.
|
| arr={ 1,3,5,7,9,11,13}
|
The array does not have a pivot point.
|
| The java method should accept following input parameters: arr (int array).
|
| Using a for loop find the sum of all elements and store it in variable sumElements.
|
| Initialize int variable pivotPoint=0. We will find the value of pivotPoint in the next steps.
|
| Initialize int variable sumLeft=0. We will use this variable to store sum of elements to the left of pivotPoint.
|
| Initialize int variable sumRight= sumElements. We will use this variable to store sum of elements to the right of pivotPoint.
|
| Iterate the array using for loop starting from 0 up to (arr.length-1) using pivotPoint as loop variable:
Reduce rightSum by arr[pivotPoint], this is because we iterate from 0 onwards, value of rightSum will reduce at each index.
If rightSum==leftSum, we have found the pivot point, return pivotPoint and arr[pivotPoint] and exit the loop.
Else Increment leftSum by arr[pivotPoint], this is because as we iterate from 0 onwards the value of leftSum will increase at each index.
|
| If no pivotPoint is found by end of loop return null.
|
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
public class ArrayFindPivotPoint {
public int[] arrayFindPivotPoint(int[] arr) throws Exception{
int sumElements=0;
int[] retArr=new int[2];
for (int idx=0; idx< arr.length; idx++) {
sumElements+=arr[idx];
}
int pivotPoint=0;
int leftSum=0;
int rightSum=sumElements;
for (pivotPoint=0; pivotPoint< arr.length;pivotPoint++) {
rightSum-=arr[pivotPoint];
if (rightSum==leftSum) {
retArr[0]=pivotPoint; // pivot index
retArr[1]=arr[pivotPoint]; // pivot element
break;
}
leftSum+=arr[pivotPoint];
}
if (pivotPoint>=arr.length) {
return null; // no pivot point found
}
return retArr;
}
public static void main(String[] args) {
ArrayFindPivotPoint ap=new ArrayFindPivotPoint();
int[] retArr;
try {
int[] intArray1 = {1,2,3,4,9,-3};
printArraySummary(intArray1, "Original Array :");
retArr=ap.arrayFindPivotPoint(intArray1);
if (retArr !=null) {
System.out.println("\n\n Pivot point index is "+retArr[0]);
System.out.println("\n\n Pivot point element is "+retArr[1]+"\n");
}else {
System.out.println("\n\n The array does not have a pivot point. \n");
}
int[] intArray2 = {9,1,2,3,-1,-5};
printArraySummary(intArray2, "Original Array :");
retArr=ap.arrayFindPivotPoint(intArray2);
if (retArr !=null) {
System.out.println("\n\n Pivot point index is "+retArr[0]);
System.out.println("\n\n Pivot point element is "+retArr[1]+"\n");
}else {
System.out.println("\n\n The array does not have a pivot point. \n");
}
int[] intArray3 = {4,5,4};
printArraySummary(intArray3, "Original Array :");
retArr=ap.arrayFindPivotPoint(intArray3);
if (retArr !=null) {
System.out.println("\n\n Pivot point index is "+retArr[0]);
System.out.println("\n\n Pivot point element is "+retArr[1]+"\n");
}else {
System.out.println("\n\n The array does not have a pivot point. \n");
}
int[] intArray4 = {0,0,0,0,0};
printArraySummary(intArray4, "Original Array :");
retArr=ap.arrayFindPivotPoint(intArray4);
if (retArr !=null) {
System.out.println("\n\n Pivot point index is "+retArr[0]);
System.out.println("\n\n Pivot point element is "+retArr[1]+"\n");
}else {
System.out.println("\n\n The array does not have a pivot point. \n");
}
int[] intArray5 = {1};
printArraySummary(intArray5, "Original Array :");
retArr=ap.arrayFindPivotPoint(intArray5);
if (retArr !=null) {
System.out.println("\n\n Pivot point index is "+retArr[0]);
System.out.println("\n\n Pivot point element is "+retArr[1]+"\n");
}else {
System.out.println("\n\n The array does not have a pivot point. \n");
}
int[] intArray6 = {1,-1,3};
printArraySummary(intArray6, "Original Array :");
retArr=ap.arrayFindPivotPoint(intArray6);
if (retArr !=null) {
System.out.println("\n\n Pivot point index is "+retArr[0]);
System.out.println("\n\n Pivot point element is "+retArr[1]+"\n");
}else {
System.out.println("\n\n The array does not have a pivot point. \n");
}
int[] intArray7 = {1,3,5,7,3,5,1};
printArraySummary(intArray7, "Original Array :");
retArr=ap.arrayFindPivotPoint(intArray7);
if (retArr !=null) {
System.out.println("\n\n Pivot point index is "+retArr[0]);
System.out.println("\n\n Pivot point element is "+retArr[1]+"\n");
}else {
System.out.println("\n\n The array does not have a pivot point. \n");
}
int[] intArray8 = {1,3,5,7,9,11,13};
printArraySummary(intArray8, "Original Array :");
retArr=ap.arrayFindPivotPoint(intArray8);
if (retArr !=null) {
System.out.println("\n\n Pivot point index is "+retArr[0]);
System.out.println("\n\n Pivot point element is "+retArr[1]+"\n");
}else {
System.out.println("\n\n The array does not have a pivot point. \n");
}
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
}
}
public static void printArraySummary(int[] intArray, String label) throws Exception {
// Case 1: The input Array is null !!
if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
// Case 2: Print input Array by index (first to last)
System.out.println();
System.out.println("************************************************************************");
System.out.print(label+" : ");
int arrayIndex=0;
for (arrayIndex=0; arrayIndex< intArray.length; arrayIndex++) {
System.out.print(intArray[arrayIndex]);
if (arrayIndex< intArray.length-1) {System.out.print(",");}
}
System.out.println();
System.out.println("*************************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
}