Partition an array into two subarrays with the same sum

Posted in

Partition an array into two subarrays with the same sum
vinaykhatri

Vinay Khatri
Last updated on May 30, 2024

    Problem

    Given an array of integers greater than zero, find if it is possible to split it into two subarrays such that the sum of the two subarrays is the same.

    Sample Input

    [1,2,3,6]

    Sample Output

    [1,2,3]
    [6]

    Approach

    An optimal solution is to first compute the sum of the entire array. Now we traverse the array from the right and keep track of the right sum, left sum can be computed by subtracting the current element from the whole sum. This approach takes O(N) time.

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    
    int findPoint(int arr[], int n)
    {
    
        int prefixSum = 0;
        for (int i = 0 ; i < n ; i++)
            prefixSum += arr[i];
        int suffixSum = 0;
        for (int i=n-1; i >= 0; i--)
        {
            suffixSum += arr[i];
    
            prefixSum -= arr[i] ;
    
            if (suffixSum == prefixSum)
                return i ;
        }
        return -1;
    }
    
    void solve(int arr[], int n)
    {
        int splitPoint = findPoint(arr, n);
    
        if (splitPoint == -1 || splitPoint == n )
        {
            cout << "Cannot split" <<endl;
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if(splitPoint == i)
                cout << endl;
            cout << arr[i] << " " ;
        }
    }
    
    int main()
    {
        int arr[] = {1 , 2 , 3 , 6 };
        int n = sizeof(arr)/sizeof(arr[0]);
        solve(arr, n);
        return 0;
    }

    Output

    1 2 3 
    6

    C Programming

    #include<stdio.h>
    
    int findPoint(int arr[], int n)
    {
        int prefixSum = 0;
        for (int i = 0 ; i < n ; i++)
            prefixSum += arr[i];
        int suffixSum = 0;
        for (int i=n-1; i >= 0; i--)
        {
            suffixSum += arr[i];
    
            prefixSum -= arr[i] ;
    
            if (suffixSum == prefixSum)
                return i ;
        }
        return -1;
    }
    
    void solve(int arr[], int n)
    {
        int splitPoint = findPoint(arr, n);
    
        if (splitPoint == -1 || splitPoint == n )
        {
            printf("Cannot split");
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if(splitPoint == i)
                printf("\n");
            printf("%d ",arr[i]);
        }
    }
    
    int main()
    {
        int arr[] = {1 , 2 , 3 , 6 };
        int n = sizeof(arr)/sizeof(arr[0]);
        solve(arr, n);
        return 0;
    }

    Output

    1 2 3 
    6

    Python Programming

    def findPoint(arr, n) :    
        prefixSum = 0
        for i in range(0, n) :
            prefixSum += arr[i]
        suffixSum = 0
        for i in range(n-1, -1, -1) :
    
            suffixSum += arr[i]
    
            prefixSum -= arr[i]
    
            if (suffixSum == prefixSum) :
                return i
        return -1
    
    def solve(arr, n) :
        splitPoint = findPoint(arr, n)
    
        if (splitPoint == -1 or splitPoint == n ) :
            print ("cannot Split")
            return
    
        for i in range (0, n) :
            if(splitPoint == i) :
                print ("")
           print (arr[i], end = " ")       
    
    
    arr = [1, 2, 3, 6]
    n = len(arr)
    solve(arr, n)

    Output

    1 2 3 
    6

    People are also reading:

    Leave a Comment on this Post

    0 Comments