« Split array

Problem

Given an integer array A of size N, check if the input array can be splitted in two parts such that -

• Sum of both parts is equal
• All elements in the input, which are divisible by 5 should be in same group.
• All elements in the input, which are divisible by 3 (but not divisible by 5) should be in other group.
• Elements which are neither divisible by 5 nor by 3, can be put in any group. Groups can be made with any set of elements, i.e. elements need not to be continuous. And you need to consider each and every element of input array in some group. Return true, if array can be split according to the above rules, else return false.

Input Format :

Line 1 : Integer N (size of array)

Line 2 : Array A elements (separated by space)

Output Format :

true or false

Constraints :

1 <= N <= 50

Sample Input 1 :

2

1 2

Sample Output 1 :

false

Sample Input 2 :

3

1 4 3

Sample Output 2 :

true

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14bool helper(int *arr, int n, int start, int lsum, int rsum)
15{
16    if (start == n)
17    {
18        return lsum == rsum;
19    }
20
21    if (arr[start] % 5 == 0)
22    {
23        lsum += arr[start];
24    }
25    else if (arr[start] % 3 == 0)
26    {
27        rsum += arr[start];
28    }
29    else
30    {
31        return helper(arr, n, start + 1, lsum + arr[start], rsum) || helper(arr, n, start + 1, lsum, rsum + arr[start]);
32    }
33    return helper(arr, n, start + 1, lsum, rsum);
34}
35
36bool splitArray(int *input, int size)
37{
38    return helper(input, size, 0, 0, 0);
39}
40
41int main()
42{
43    int size;
44    cin >> size;
45
46    int *input = new int[size];
47    for (int i = 0; i < size; i++)
48    {
49        cin >> input[i];
50    }
51
52    if (splitArray(input, size))
53    {
54        cout << "true" << endl;
55    }
56    else
57    {
58        cout << "false" << endl;
59    }
60    return 0;
61}