Given an array of integers arr[], the task is to find all the values for sum such that for a value sum[i] the array can be divided into sub-arrays of sum equal to sum[i]. If array cannot be divided into sub-arrays of equal sum then print -1.
Examples:
Input: arr[] = {2, 2, 2, 1, 1, 2, 2}
Output: 2 4 6
The array can be divided into sub-arrays of sum 2, 4 and 6.
{2}, {2}, {2}, {1, 1}, {2} and {2}
{2, 2}, {2, 1, 1} and {2, 2}
{2, 2, 2} and {1, 1, 2, 2}Input: arr[] = {1, 1, 2}
Output: 2
The array can be divided into sub-arrays of sum 2.
{1, 1} and {2}
Approach: Make a Prefix Sum Array P[] where P[i] stores the sum of elements from index 0 to i. The divisors of the total sum S can only be the possible sub-array sum. So for every divisor, if all the multiples of the divisor upto total sum S are present in the array P[], then that would be a possible sub-array sum. Mark all the elements of P[] into a Map as 1 so that look-up would be easy. All the divisors can be checked in sqrt(S) time.
Below is the implementation of the above approach:
C++
// C++ program to find the sums for which an array// can be divided into subarrays of equal sum.#include <bits/stdc++.h>using namespace std;// Function to find the sums for which an array// can be divided into subarrays of equal sumvoid getSum(int a[], int n){ int P[n]; // Creating prefix sum array P[0] = a[0]; for (int i = 1; i < n; i++) P[i] = a[i] + P[i - 1]; // Total Sum int S = P[n - 1]; // Initializing a Map for look-up map<int, int> hash; // Setting all the present sum as 1 for (int i = 0; i < n; i++) hash[P[i]] = 1; // Set to store the subarray sum set<int> res; // Check the divisors of S for (int i = 1; i * i <= S; i++) { if (S % i == 0) { bool pres = true; int div1 = i, div2 = S / i; // Check if all multiples of div1 present or not for (int j = div1; j <= S; j += div1) { if (hash[j] != 1) { pres = false; break; } } // If all multiples are present if (pres and div1 != S) res.insert(div1); pres = true; // Check if all multiples of div2 present or not for (int j = S / i; j <= S; j += S / i) { if (hash[j] != 1) { pres = false; break; } } // If all multiples are present if (pres and div2 != S) res.insert(div2); } } // If array cannot be divided into // sub-arrays of equal sum if(res.size() == 0) { cout << "-1"; return; } // Printing the results for (auto i : res) cout << i << " ";}// Driver codeint main(){ int a[] = { 1, 2, 1, 1, 1, 2, 1, 3 }; int n = sizeof(a) / sizeof(a[0]); getSum(a, n); return 0;} |
Java
// Java program to find the sums for which an array // can be divided into subarrays of equal sum. import java.util.HashMap;import java.util.HashSet;class GFG { // Function to find the sums for which an array // can be divided into subarrays of equal sum public static void getSum(int[] a, int n) { int[] P = new int[n]; // Creating prefix sum array P[0] = a[0]; for (int i = 1; i < n; i++) P[i] = a[i] + P[i - 1]; // Total Sum int S = P[n - 1]; HashMap<Integer, Integer> hash = new HashMap<>(); // Setting all the present sum as 1 for (int i = 0; i < n; i++) hash.put(P[i], 1); // Set to store the subarray sum HashSet<Integer> res = new HashSet<>(); // Check the divisors of S for (int i = 1; i * i <= S; i++) { if (S % i == 0) { boolean pres = true; int div1 = i, div2 = S / i; // Check if all multiples of div1 present or not for (int j = div1; j <= S; j += div1) { if (hash.get(j) == null || hash.get(j) != 1) { pres = false; break; } } // If all multiples are present if (pres && div1 != S) res.add(div1); pres = true; // Check if all multiples of div2 present or not for (int j = S / i; j <= S; j += S / i) { if (hash.get(j) == null || hash.get(j) != 1) { pres = false; break; } } // If all multiples are present if (pres && div2 != S) res.add(div2); } } // If array cannot be divided into // sub-arrays of equal sum if (res.size() == 0) { System.out.println("-1"); return; } // Printing the results for (int i : res) System.out.print(i + " "); } // Driver code public static void main(String[] args) { int[] a = { 1, 2, 1, 1, 1, 2, 1, 3 }; int n = a.length; getSum(a, n); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 program to find the sums for # which an array can be divided into # subarrays of equal sum. # from math lib import sqrt functionfrom math import sqrt# Function to find the sums for which # an array can be divided into subarrays # of equal sum def getSum(a, n) : P = [0] * n # Creating prefix sum array P[0] = a[0] for i in range(1, n) : P[i] = a[i] + P[i - 1] # Total Sum S = P[n - 1] # Initializing a Map for look-up hash = {} # Setting all the present sum as 1 for i in range(n) : hash[P[i]] = 1 # Set to store the subarray sum res = set() # Check the divisors of S for i in range(1, int(sqrt(S)) + 1) : if (S % i == 0) : pres = True; div1 = i div2 = S // i # Check if all multiples of # div1 present or not for j in range(div1 , S + 1, div1) : if j not in hash.keys() : pres = False break # If all multiples are present if (pres and div1 != S) : res.add(div1) pres = True # Check if all multiples of div2 # present or not for j in range(S // i , S + 1 , S // i) : if j not in hash.keys(): pres = False; break # If all multiples are present if (pres and div2 != S) : res.add(div2) # If array cannot be divided into # sub-arrays of equal sum if(len(res) == 0) : print("-1") return # Printing the results for i in res : print(i, end = " ")# Driver code if __name__ == "__main__" : a = [ 1, 2, 1, 1, 1, 2, 1, 3 ] n = len(a) getSum(a, n)# This code is contributed by Ryuga |
C#
// C# program to find the sums for which// an array can be divided into subarrays// of equal sum. using System;using System.Collections.Generic;class GFG {// Function to find the sums for which // an array can be divided into subarrays// of equal sumpublic static void getSum(int[] a, int n) { int[] P = new int[n]; // Creating prefix sum array P[0] = a[0]; for (int i = 1; i < n; i++) P[i] = a[i] + P[i - 1]; // Total Sum int S = P[n - 1]; Dictionary<int, int> hash = new Dictionary<int, int>(); // Setting all the present sum as 1 for (int i = 0; i < n; i++) if(!hash.ContainsKey(P[i])) hash.Add(P[i], 1); // Set to store the subarray sum HashSet<int> res = new HashSet<int>(); // Check the divisors of S for (int i = 1; i * i <= S; i++) { if (S % i == 0) { Boolean pres = true; int div1 = i, div2 = S / i; // Check if all multiples of // div1 present or not for (int j = div1; j <= S; j += div1) { if (!hash.ContainsKey(j) || hash[j] != 1) { pres = false; break; } } // If all multiples are present if (pres && div1 != S) res.Add(div1); pres = true; // Check if all multiples of // div2 present or not for (int j = S / i; j <= S; j += S / i) { if (hash[j] == 0 || hash[j] != 1) { pres = false; break; } } // If all multiples are present if (pres && div2 != S) res.Add(div2); } } // If array cannot be divided into // sub-arrays of equal sum if (res.Count == 0) { Console.WriteLine("-1"); return; } // Printing the results foreach (int i in res) Console.Write(i + " ");}// Driver codepublic static void Main(String[] args){ int[] a = { 1, 2, 1, 1, 1, 2, 1, 3 }; int n = a.Length; getSum(a, n);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to find the sums for which an array// can be divided into subarrays of equal sum.// Function to find the sums for which an array// can be divided into subarrays of equal sumfunction getSum(a, n) { let P = new Array(n); // Creating prefix sum array P[0] = a[0]; for (let i = 1; i < n; i++) P[i] = a[i] + P[i - 1]; // Total Sum let S = P[n - 1]; // Initializing a Map for look-up let hash = new Map(); // Setting all the present sum as 1 for (let i = 0; i < n; i++) hash.set(P[i], 1); // Set to store the subarray sum let res = new Set(); // Check the divisors of S for (let i = 1; i * i <= S; i++) { if (S % i == 0) { let pres = true; let div1 = i, div2 = Math.floor(S / i); // Check if all multiples of div1 present or not for (let j = div1; j <= S; j += div1) { if (hash.get(j) != 1) { pres = false; break; } } // If all multiples are present if (pres && div1 != S) res.add(div1); pres = true; // Check if all multiples of div2 present or not for (let j = Math.floor(S / i); j <= S; j += Math.floor(S / i)) { if (hash.get(j) != 1) { pres = false; break; } } // If all multiples are present if (pres && div2 != S) res.add(div2); } } // If array cannot be divided into // sub-arrays of equal sum if (res.size == 0) { document.write("-1"); return; } res = [...res].sort((a, b) => a - b) // Printing the results for (let i of res) document.write(i + " ");}// Driver codelet a = [1, 2, 1, 1, 1, 2, 1, 3];let n = a.length;getSum(a, n);// This code is contributed by gfgking.</script> |
Output
3 4 6
Complexity Analysis:
- Time Complexity: O(nlogn), to check for divisors and multiples
- Auxiliary Space: O(n), as extra space of size n is used
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
