Find the index that divides an array into two non-empty subarrays with equal sum

Posted in

Find the index that divides an array into two non-empty subarrays with equal sum
maazbinasad

Maaz Bin Asad
Last updated on February 28, 2024

    Problem

    Given an integer array, find an index that divides it into two non-empty subarrays having an equal sum.

    Sample Input

    [9, 2, 4, 5, 6]

    Sample Output

    Index 2 (0-based-indexing) divides the array into [9,2] and [5,6] having equal sum.

    Approach

    The approach is to first store the sum of all the elements in a variable named sum . We then traverse through the array and keep track of the prefix sum of each element. The sum of the right subarray of the current element will be sum - prefix sum - current element . If this sum is equal to the prefix sum, then we found the index. The time complexity of this approach is O(N).

    C Programming

    #include <stdio.h>
    voidsolve(int arr[], int n)
    {
     int sum = 0;
     for (int i = 0; i < n; i++) {
     sum += arr[i];
     }
     int prefixSum = arr[0];
     for (int i = 1; i < n - 1; i++)
     {
     if (prefixSum == sum - (arr[i] + prefixSum)) {
     printf("%d", i);
     break;
     }
     prefixSum += arr[i];
     }
    }
    intmain(void)
    {
     int arr[] = {9, 2, 1, 5, 6 };
     int n = sizeof(arr)/sizeof(arr[0]);
     solve(arr, n);
     return0;
    }
    

    Output

    2

    C++ Programming

    #include <bits/stdc++.h>
    usingnamespacestd;
    voidsolve(int arr[], int n)
    {
     int sum = 0;
     for (int i = 0; i < n; i++) {
     sum += arr[i];
     }
     int prefixSum = arr[0];
     for (int i = 1; i < n - 1; i++)
     {
     if (prefixSum == sum - (arr[i] + prefixSum)) {
     cout<<i;
     break;
     }
     prefixSum += arr[i];
     }
    }
    intmain(void)
    {
     int arr[] = {9, 2, 1, 5, 6 };
     int n = sizeof(arr)/sizeof(arr[0]);
     solve(arr, n);
     return0;
    }

    Output

    2

    Python Programming

    defsolve(arr):
     sumArray = sum(arr)
     prefixSum = arr[0]
     for i in range(1, len(arr) - 1):
     if prefixSum == sumArray - (arr[i] + prefixSum):
     print(i)
     prefixSum += arr[i]
    arr = [2, 9, 1, 5, 6]
    solve(arr)

    Output

    2

    People are also reading:

    Leave a Comment on this Post

    0 Comments