Count number of ways array can be partitioned such that same numbers are present in same subarray
Given an array A[] of size N. The Task for this problem is to count several ways to partition the given array A[] into continuous subarrays such that the same integers are not present in different subarrays. Print the answer modulo 109 + 7.
Examples:
Input: A[] = {1, 2, 1, 3}
Output: 2
Explanation: There are two ways to break above array such that it follows above conditions:
- First way is {{1, 2, 1} + {3}}
- Second way is {{1, 2, 1, 3}}
{{1, 2} + {1, 3}} is not possible since 1 is present in different subarrays.
Input: A[] = {1, 1, 1, 1}
Output: 1
Explanation: There is only one way to break above array such that it follows above conditions:
- {1, 1, 1, 1} is the only way.
{{1, 1} + {1, 1}} is not possible since same element repeats in two different subarrays.
Approach: The problem can be solved using the below approach:
The problem can be solved by finding the first and last occurrence of every element. We will treat it as segment and merge all overlapping segments. Suppose we are left with M segments after merging the overlapping segments. Now, for every segment we have the choice to include it with the previous segment’s subarray or make a new subarray from it. This is same as Stars and Bars where we have (M-1) blanks between M partitions and we have 2 choices for each partition, that is either place a bar in the blank to start a new subarray or do not place a bar and continue with the previous subarray. So, if we have M segments after merging the overlapping segments, we have 2(M-1) ways to make valid partition of the array.
For eg: In the first example {1, 2, 1, 3}
- First and last occurrence of 1 : {first occurrence = 1, last occurrence = 3}
- First and last occurrence of 2: {first occurrence = 2, last occurrence = 2}
- First and last occurrence of 3: {first occurrence = 4, last occurrence = 4}
if it is represented as segments there are three segments currently {1, 3}, {2, 2} and {4, 4}
Let’s unite overlapping segments we will end up with {1, 3} and {4, 4}
now M = 2 so by above formula 2M – 1 = 2 (there will be two possible partitions which follows required conditions)
Step-by-step algorithm:
- Declare two Hash Maps firstOcc[] and lastOcc[] to record the first and last occurence of every element.
- Declare array of pairs segments[] for storing segments.
- Sort the array segments[] and merge all the overlapping segments.
- Count the number of segments left after merging the overlapping segments, say M.
- Return the answer as 2(M – 1) mod 1000000007 using binary exponentiation.
Implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // to avoid interger overflow #define int long long // mod const int mod = 1e9 + 7; /* Binary Exponentiation to calculate (x^y)%mod in O(logy) */ int power( int x, int y) { // Initialize result int res = 1; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % mod; // y must be even now y = y >> 1; x = (x * x) % mod; } return res; } // Function to Count number of ways array can be broken in // continuous subarray such that same number does not // present in any two subarrays int countOfPartitions( int A[], int N) { // HashMap unordered_map< int , int > firstOcc, lastOcc; // find first and last occurence of A[i] for ( int i = 0; i < N; i++) { if (!firstOcc[A[i]]) firstOcc[A[i]] = i + 1; lastOcc[A[i]] = i + 1; } // array of segments vector<pair< int , int > > segments; // turn first and last occurence in segments for ( auto & e : firstOcc) { segments.push_back( { firstOcc[e.first], lastOcc[e.first] }); } // sort all segments sort(segments.begin(), segments.end()); // Stores index of last element // number of unique segments - 1 int index = 0; // merging segments for ( int i = 1; i < segments.size(); i++) { // if current segment overlaps with previous segment // unite them if (segments[index].second >= segments[i].first) segments[index].second = max( segments[index].second, segments[i].second); else { // initiate new segment index++; segments[index] = segments[i]; } } // number of unique segments int M = index + 1; // finding answer by formula given int totalWays = power(2, M - 1); // number of total ways array can be partitioned // such that no two arrays contain same element return totalWays; } // Driver Code int32_t main() { // Input int N = 4; int A[] = { 1, 2, 1, 3 }; // Function Call cout << countOfPartitions(A, N) << endl; return 0; } |
Java
// Java program for the above approach import java.util.*; public class Main { // Function to calculate (x^y) % mod using binary // exponentiation static long power( long x, long y, long mod) { long res = 1 ; x = x % mod; while (y > 0 ) { if ((y & 1 ) == 1 ) res = (res * x) % mod; y = y >> 1 ; x = (x * x) % mod; } return res; } // Function to count the number of ways an array can be // broken into continuous subarrays such that no two // subarrays contain the same element static long countOfPartitions( int [] arr) { int N = arr.length; // HashMap to store first and last occurrences of // elements HashMap<Integer, Integer> firstOcc = new HashMap<>(); HashMap<Integer, Integer> lastOcc = new HashMap<>(); // Find first and last occurrence of arr[i] for ( int i = 0 ; i < N; i++) { if (!firstOcc.containsKey(arr[i])) firstOcc.put(arr[i], i + 1 ); lastOcc.put(arr[i], i + 1 ); } // Array to store segments ArrayList<Map.Entry<Integer, Integer> > segments = new ArrayList<>(); // Turn first and last occurrence into segments for (Map.Entry<Integer, Integer> entry : firstOcc.entrySet()) { int key = entry.getKey(); int value = entry.getValue(); segments.add( new AbstractMap.SimpleEntry<>( value, lastOcc.get(key))); } // Sort all segments segments.sort( Comparator.comparing(Map.Entry::getKey)); // Stores index of last element, i.e., number of // unique segments - 1 int index = 0 ; // Merging segments for ( int i = 1 ; i < segments.size(); i++) { // If current segment overlaps with the previous // segment, unite them if (segments.get(index).getValue() >= segments.get(i).getKey()) { segments.get(index).setValue( Math.max(segments.get(index).getValue(), segments.get(i).getValue())); } else { // Initiate a new segment index++; segments.set(index, segments.get(i)); } } // Number of unique segments int M = index + 1 ; // Finding answer using the given formula long totalWays = power( 2 , M - 1 , ( long )1e9 + 7 ); // Number of total ways array can be partitioned // such that no two arrays contain the same element return totalWays; } // Driver Code public static void main(String[] args) { // Input int [] A = { 1 , 2 , 1 , 3 }; // Function Call System.out.println(countOfPartitions(A)); } } // This code is contributed by Susobhan Akhuli |
Python3
# Python code to implement the approach # Function to calculate (x^y) % mod using binary exponentiation def power(x, y, mod): res = 1 x = x % mod while y > 0 : if y & 1 : res = (res * x) % mod y = y >> 1 x = (x * x) % mod return res # Function to count the number of ways an array can be broken into continuous subarrays # such that no two subarrays contain the same element def count_of_partitions(arr): N = len (arr) # HashMap to store first and last occurrences of elements first_occ = {} last_occ = {} # Find first and last occurrence of arr[i] for i in range (N): if arr[i] not in first_occ: first_occ[arr[i]] = i + 1 last_occ[arr[i]] = i + 1 # Array to store segments segments = [] # Turn first and last occurrence into segments for key, value in first_occ.items(): segments.append((value, last_occ[key])) # Sort all segments segments.sort() # Stores index of last element, i.e., number of unique segments - 1 index = 0 # Merging segments for i in range ( 1 , len (segments)): # If current segment overlaps with the previous segment, unite them if segments[index][ 1 ] > = segments[i][ 0 ]: segments[index] = (segments[index][ 0 ], max (segments[index][ 1 ], segments[i][ 1 ])) else : # Initiate a new segment index + = 1 segments[index] = segments[i] # Number of unique segments M = index + 1 # Finding answer using the given formula total_ways = power( 2 , M - 1 , int ( 1e9 ) + 7 ) # Number of total ways array can be partitioned # such that no two arrays contain the same element return total_ways # Driver Code if __name__ = = "__main__" : # Input A = [ 1 , 2 , 1 , 3 ] # Function Call print (count_of_partitions(A)) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { const long Mod = 1000000007; // Binary Exponentiation to calculate (x^y)%mod in O(logy) static long Power( long x, long y) { long res = 1; while (y > 0) { if ((y & 1) == 1) res = (res * x) % Mod; y >>= 1; x = (x * x) % Mod; } return res; } // Function to count the number of ways an array can be broken into // continuous subarrays such that the same number does not // appear in any two subarrays static long CountOfPartitions( int [] A, int N) { // HashMap Dictionary< int , int > firstOcc = new Dictionary< int , int >(); Dictionary< int , int > lastOcc = new Dictionary< int , int >(); // find first and last occurrence of A[i] for ( int i = 0; i < N; i++) { if (!firstOcc.ContainsKey(A[i])) firstOcc[A[i]] = i + 1; lastOcc[A[i]] = i + 1; } // array of segments List<Tuple< int , int >> segments = new List<Tuple< int , int >>(); // turn first and last occurrence into segments foreach ( var e in firstOcc) { segments.Add( new Tuple< int , int >(firstOcc[e.Key], lastOcc[e.Key])); } // sort all segments segments = segments.OrderBy(t => t.Item1).ToList(); // Stores index of last element int index = 0; // merging segments for ( int i = 1; i < segments.Count; i++) { // if current segment overlaps with the previous segment // unite them if (segments[index].Item2 >= segments[i].Item1) segments[index] = new Tuple< int , int >(segments[index].Item1, Math.Max(segments[index].Item2, segments[i].Item2)); else { // initiate a new segment index++; segments[index] = segments[i]; } } // number of unique segments int M = index + 1; // finding the answer using the given formula long totalWays = Power(2, M - 1); // number of total ways the array can be partitioned // such that no two arrays contain the same element return totalWays; } // Driver Code static void Main() { // Input int N = 4; int [] A = { 1, 2, 1, 3 }; // Function Call Console.WriteLine(CountOfPartitions(A, N)); } } |
Javascript
// JavaScript code to implement the approach // Function to Count number of ways array can be broken in // continuous subarray such that same number does not // present in any two subarrays function countOfPartitions(A, N) { // HashMap let firstOcc = new Map(); let lastOcc = new Map(); // find first and last occurence of A[i] for (let i = 0; i < N; i++) { if (!firstOcc.has(A[i])) { firstOcc.set(A[i], i + 1); } lastOcc.set(A[i], i + 1); } // array of segments let segments = []; // turn first and last occurence into segments firstOcc.forEach((value, key) => { segments.push([value, lastOcc.get(key)]); }); // sort all segments segments.sort((a, b) => a[0] - b[0]); // Stores index of last element // number of unique segments - 1 let index = 0; // merging segments for (let i = 1; i < segments.length; i++) { // if current segment overlaps with previous segment // unite them if (segments[index][1] >= segments[i][0]) { segments[index][1] = Math.max(segments[index][1], segments[i][1]); } else { // initiate new segment index++; segments[index] = segments[i]; } } // number of unique segments let M = index + 1; // finding answer by formula given let totalWays = power(2, M - 1); // number of total ways array can be partitioned // such that no two arrays contain the same element return totalWays; } // Binary Exponentiation to calculate (x^y)%mod in O(logy) function power(x, y) { // Initialize result let res = 1; while (y > 0) { // If y is odd, multiply x with result if (y & 1) { res = (res * x) % (1e9 + 7); } // y must be even now y = y >> 1; x = (x * x) % (1e9 + 7); } return res; } // Driver Code function main() { // Input let N = 4; let A = [1, 2, 1, 3]; // Function Call console.log(countOfPartitions(A, N)); } // Execute the main function main(); |
2
Time Complexity: O(N), where N is the size of input array A[].
Auxiliary Space: O(N)
Contact Us