Advertisement
saurav_kalsoor

Find Partition Point - JAVA

Aug 6th, 2021
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.97 KB | None | 0 0
  1. package com.company;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Scanner;
  5.  
  6.  
  7. public class Problem {
  8.  
  9.     public static void main(String[] args){
  10.         Scanner sc = new Scanner(System.in);
  11.         int n = sc.nextInt();
  12.  
  13.         ArrayList<Integer> list = new ArrayList<>();
  14.  
  15.         for(int i=0; i<n; i++){
  16.             int num = sc.nextInt();
  17.             list.add(num);
  18.         }
  19.         System.out.println(findPartitionPoint(list, n));
  20.  
  21.     }
  22.  
  23.     public static int findPartitionPoint(ArrayList<Integer> list, int n){
  24.         int[] prefixSum = new int[n];
  25.         prefixSum[0] = list.get(0);
  26.  
  27.         for(int i=1; i < n; i++)
  28.             prefixSum[i] = prefixSum[i-1] + list.get(i);
  29.  
  30.         for(int i=0; i < n; i++){
  31.             int leftSum = i > 0 ? prefixSum[i-1] : 0;
  32.             int rightSum = prefixSum[n-1] - prefixSum[i];
  33.  
  34.             if(leftSum == rightSum){
  35.                 return i;
  36.             }
  37.         }
  38.  
  39.         return -1;
  40.     }
  41. }
  42.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement