Untitled

 avatar
unknown
java
2 years ago
1.8 kB
3
Indexable
package training.algorithms;

import java.util.Arrays;

public class WeightPointWithIgor {

    // Mamy na wejściu tablicę liczb i musimy zwrócić indeks elementu, który jest środkiem ciężkości
    // (suma elementów z lewej równa jest sumie elementów z prawej)

    // czy środek ciężkości jest wliczany do sum? -> tak, ale do obu
    // czy środek ciężkości ma być wliczany do lewej czy do prawej strony? -> doliczane do prawej

    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 2, 3, 3, 2, 1};
        int[] arr2 = new int[]{1, 2, 100, 3, 2, 1};
        int[] arr3 = new int[]{1, 6, 1, 2, 4};
        int[] arr4 = new int[]{1, 1};
        int[] arr5 = new int[]{20};

        System.out.println("arr1: " + weightPoint(arr1));
        System.out.println("arr2: " + weightPoint(arr2));
        System.out.println("arr3: " + weightPoint(arr3));
        System.out.println("arr4: " + weightPoint(arr4));
        System.out.println("arr5: " + weightPoint(arr5));
    }

    private static int weightPoint(int[] array) {
        return weightPoint(array, 0, array.length - 1);
    }

    private static int weightPoint(int[] array, int low, int high) {
        if (low > high) {
            return -1;
        }

        if (array.length == 1) return 0;

        int mid = (high - low) / 2 + low;
        int leftSum = Arrays.stream(array, 0, mid).sum();
        int rightSum = Arrays.stream(array, mid, array.length).sum();

        if (leftSum == rightSum) {
            return mid;
        } else if (leftSum > rightSum) {
            return weightPoint(array, low, mid - 1);
        } else {
            return weightPoint(array, mid + 1, high);
        }
    }
}
Editor is loading...