Counting Subarrays with elements repeated twice after swapping
Given an array A[] of N integers, the task is to find the number of subarrays of A[], which is the repetition of its’ elements twice, after having swapped the inside elements of this subarray any number of times.
Note: Each element of the array is between 0 and 9 (inclusive of both).
Examples:
Input: N = 8, A[] = {2, 0, 2, 3, 0, 3, 2, 2}
Output: 4
Explanation: First subarray -> {2, 0, 2, 3, 0, 3}.
In this subarray, swap indices 3 and 4. We get {2, 0, 3, 2, 0, 3} which is the repetition of {2, 0, 3} twice.
Second subarray -> {2, 0, 2, 3, 0, 3, 2, 2}.
Swap the following pairs of indices :
2 and 3 -> {2, 2, 0, 3, 0, 3, 2, 2}
5 and 7 -> {2, 2, 0, 3, 2, 3, 0, 2}
6 and 8 -> {2, 2, 0, 3, 2, 2, 0, 3}
The array becomes a repetition of {2, 2, 0, 3}.
Similarly, the rest of the subarrays are {0, 2, 3, 0, 3, 2} and {2, 2}.Input: N = 15, A[] = {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7}
Output: 29
Approach: To solve the problem follow the below idea:
This problem is observation-based. Subarray from index i+1 to j can be made a repetition of the same array twice if and only if, X{i} is equal to X{j} (for all num=0 to 9). This is because the parity of each digit at ith and jth indices are same. So, each digit will occur an even number of times from the i+1 to the jth index.
Below are the steps that were to follow the above approach:
- Initialize a map (say “mp”) of the key vector of int and value of type int. This map “mp” stores the number of times the parity of each integer (from 0 to 9) becomes the same.
- Also, initialize a vector of integers, say “cnt”. It stores the number of occurrences of each integer (from 0 to 9) modulo 2, till the current index.
- Iterate through the array A[] and update “mp” and “cnt” accordingly.
- Initialize a variable “ans” with 0 to store the answer to the required problem.
- Iterate through the map and add the temp*(temp-1)/2 to the answer at each iteration, where the temp is the value of each key of the map.
- Return the final answer.
Below is the code to implement the above steps:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; #define int long long // Function to find Number of subarrays // which are repetition of same array // twice on swapping any number // of elements int noOfSubarrays( int N, int A[]) { // Initializing "mp" and "cnt" map<vector< int >, int > mp; vector< int > cnt(10, 0); mp[cnt]++; // Iterating through the array and // updating "mp" and "cnt" for ( int i = 0; i < N; i++) { cnt[A[i]]++; cnt[A[i]] %= 2; mp[cnt]++; } // Initialize a variable "ans" // to store the answer int ans = 0; // Iterating through the map and // accordingly updating the "ans" for ( auto it : mp) { int temp = it.second; ans += (temp * (temp - 1)) / 2; } // Return final answer return ans; } // Driver's code int32_t main() { int N = 8; int A[] = { 2, 0, 2, 3, 0, 3, 2, 2 }; int answer = noOfSubarrays(N, A); // Function Call cout << answer << endl; return 0; } |
Java
import java.util.*; public class Main { public static int noOfSubarrays( int N, int [] A) { // Initializing "mp" and "cnt" Map<String, Integer> mp = new HashMap<>(); int [] cnt = new int [ 10 ]; Arrays.fill(cnt, 0 ); mp.put(Arrays.toString(cnt), 1 ); // Iterating through the array and // updating "mp" and "cnt" int ans = 0 ; for ( int i = 0 ; i < N; i++) { cnt[A[i]]++; cnt[A[i]] %= 2 ; String cntStr = Arrays.toString(cnt); ans += mp.getOrDefault(cntStr, 0 ); mp.put(cntStr, mp.getOrDefault(cntStr, 0 ) + 1 ); } // Return final answer return ans; } public static void main(String[] args) { int N = 8 ; int [] A = { 2 , 0 , 2 , 3 , 0 , 3 , 2 , 2 }; int answer = noOfSubarrays(N, A); // Function Call System.out.println(answer); } } |
Python3
# Python code for the above approach from collections import defaultdict # Function to find Number of subarrays # which are repetition of same array # twice on swapping any number # of elements def noOfSubarrays(N, A): # Initializing "mp" and "cnt" mp = defaultdict( int ) cnt = [ 0 ] * 10 mp[ tuple (cnt)] + = 1 # Iterating through the array and # updating "mp" and "cnt" for i in range (N): cnt[A[i]] + = 1 cnt[A[i]] % = 2 mp[ tuple (cnt)] + = 1 # Initialize a variable "ans" # to store the answer ans = 0 # Iterating through the map and # accordingly updating the "ans" for it in mp: temp = mp[it] ans + = (temp * (temp - 1 )) / / 2 # Return final answer return ans # Driver's code if __name__ = = '__main__' : N = 8 A = [ 2 , 0 , 2 , 3 , 0 , 3 , 2 , 2 ] answer = noOfSubarrays(N, A) # Function Call print (answer) # This code is contributed by Tapesh(tapeshdua420) |
C#
using System; using System.Collections.Generic; class GFG { public static int NoOfSubarrays( int N, int [] A) { // Initializing "mp" and "cnt" Dictionary< string , int > mp = new Dictionary< string , int >(); int [] cnt = new int [10]; Array.Fill(cnt, 0); mp[ArrayToString(cnt)] = 1; // Iterating through the array and // updating "mp" and "cnt" int ans = 0; for ( int i = 0; i < N; i++) { cnt[A[i]]++; cnt[A[i]] %= 2; string cntStr = ArrayToString(cnt); ans += mp.GetValueOrDefault(cntStr, 0); mp[cntStr] = mp.GetValueOrDefault(cntStr, 0) + 1; } // Return final answer return ans; } public static string ArrayToString( int [] arr) { return "[" + string .Join( "," , arr) + "]" ; } public static void Main( string [] args) { int N = 8; int [] A = { 2, 0, 2, 3, 0, 3, 2, 2 }; int answer = NoOfSubarrays(N, A); // Function Call Console.WriteLine(answer); } } |
Javascript
function noOfSubarrays(N, A) { // Initializing "mp" and "cnt" const mp = new Map(); const cnt = new Array(10).fill(0); mp.set(cnt.join( ',' ), 1); // Iterating through the array and // updating "mp" and "cnt" let ans = 0; for (let i = 0; i < N; i++) { cnt[A[i]]++; cnt[A[i]] %= 2; const cntStr = cnt.join( ',' ); ans += mp.get(cntStr) || 0; mp.set(cntStr, (mp.get(cntStr) || 0) + 1); } // Return final answer return ans; } // Driver's code const N = 8; const A = [2, 0, 2, 3, 0, 3, 2, 2]; const answer = noOfSubarrays(N, A); // Function Call console.log(answer); |
4
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Contact Us