Given two unsorted arrays of same size where arr[i] >= 0 for all i, the task is to check if two arrays are permutations of each other or not.
Examples:
Input: arr1[] = {2, 1, 3, 5, 4, 3, 2}
arr2[] = {3, 2, 2, 4, 5, 3, 1}
Output: Yes
Input: arr1[] = {2, 1, 3, 5}
arr2[] = {3, 2, 2, 4}
Output: No
It has been already discussed in Check if two arrays are permutations of each other using Sorting and Hashing. But in this post, a different approach is discussed.
Approach:
- Traverse the first array A, add and multiply all the elements and store them in variables as Sum1 and Mul1 respectively.
- Similarly, traverse the second array B, add and multiply all the elements and store them in variables as Sum2 and Mul2 respectively.
- Now, compare both sum1, sum2 and mul1, mul2. If Sum1 == Sum2 and Mul1 == Mul2, then both arrays are permutations of each other, else not.
Implementation:
C++
// CPP code to check if arrays// are permutations of each other#include <iostream>using namespace std;// Function to check if arrays// are permutations of each other.bool arePermutations(int a[], int b[], int n, int m){ int sum1 = 0, sum2 = 0, mul1 = 1, mul2 = 1; // Calculating sum and multiply of first array for (int i = 0; i < n; i++) { sum1 += a[i]; mul1 *= a[i]; } // Calculating sum and multiply of second array for (int i = 0; i < m; i++) { sum2 += b[i]; mul2 *= b[i]; } // If sum and mul of both arrays are equal, // return true, else return false. return ((sum1 == sum2) && (mul1 == mul2));}// Driver codeint main(){ int a[] = { 1, 3, 2 }; int b[] = { 3, 1, 2 }; int n = sizeof(a) / sizeof(int); int m = sizeof(b) / sizeof(int); if (arePermutations(a, b, n, m)) cout << "Yes" << endl; else cout << "No" << endl; return 0;} |
Java
// Java code to check if arrays// are permutations of each otherimport java.io.*;class GFG {// Function to check if arrays// are permutations of each other.static boolean arePermutations(int a[], int b[], int n, int m){ int sum1 = 0, sum2 = 0, mul1 = 1, mul2 = 1; // Calculating sum and multiply of first array for (int i = 0; i < n; i++) { sum1 += a[i]; mul1 *= a[i]; } // Calculating sum and multiply of second array for (int i = 0; i < m; i++) { sum2 += b[i]; mul2 *= b[i]; } // If sum and mul of both arrays are equal, // return true, else return false. return ((sum1 == sum2) && (mul1 == mul2));}// Driver code public static void main (String[] args) { int a[] = { 1, 3, 2 }; int b[] = { 3, 1, 2 }; int n = a.length; int m = b.length; if (arePermutations(a, b, n, m)==true) System.out.println( "Yes"); else System.out.println( "No"); }}// This code is contributed by inder_verma.. |
Python3
# Python 3 program to check if arrays # are permutations of each other # Function to check if arrays # are permutations of each otherdef arePermutations(a, b, n, m) : sum1, sum2, mul1, mul2 = 0, 0, 1, 1 # Calculating sum and multiply of first array for i in range(n) : sum1 += a[i] mul1 *= a[i] # Calculating sum and multiply of second array for i in range(m) : sum2 += b[i] mul2 *= b[i] # If sum and mul of both arrays are equal, # return true, else return false. return((sum1 == sum2) and (mul1 == mul2))# Driver code if __name__ == "__main__" : a = [ 1, 3, 2] b = [ 3, 1, 2] n = len(a) m = len(b) if arePermutations(a, b, n, m) : print("Yes") else : print("No") # This code is contributed by ANKITRAI1 |
C#
// C# code to check if arrays// are permutations of each otherusing System;class GFG {// Function to check if arrays// are permutations of each other.static bool arePermutations(int[] a, int[] b, int n, int m){ int sum1 = 0, sum2 = 0, mul1 = 1, mul2 = 1; // Calculating sum and multiply // of first array for (int i = 0; i < n; i++) { sum1 += a[i]; mul1 *= a[i]; } // Calculating sum and multiply // of second array for (int i = 0; i < m; i++) { sum2 += b[i]; mul2 *= b[i]; } // If sum and mul of both arrays // are equal, return true, else // return false. return ((sum1 == sum2) && (mul1 == mul2));}// Driver codepublic static void Main (){ int[] a = { 1, 3, 2 }; int[] b = { 3, 1, 2 }; int n = a.Length; int m = b.Length; if (arePermutations(a, b, n, m) == true) Console.Write( "Yes"); else Console.Write( "No");}}// This code is contributed // by ChitraNayal |
Javascript
<script>// JavaScript code to check if arrays// are permutations of each other // Function to check if arrays // are permutations of each other. function arePermutations(a,b,n,m) { let sum1 = 0, sum2 = 0, mul1 = 1, mul2 = 1; // Calculating sum and multiply of first array for (let i = 0; i < n; i++) { sum1 += a[i]; mul1 *= a[i]; } // Calculating sum and multiply of second array for (let i = 0; i < m; i++) { sum2 += b[i]; mul2 *= b[i]; } // If sum and mul of both arrays are equal, // return true, else return false. return ((sum1 == sum2) && (mul1 == mul2)); } // Driver code let a=[1, 3, 2 ]; let b=[3, 1, 2]; let n = a.length; let m = b.length; if (arePermutations(a, b, n, m)==true) document.write( "Yes"); else document.write( "No"); // This code is contributed by rag2127</script> |
PHP
<?php// PHP code to check if arrays// are permutations of each other// Function to check if arrays// are permutations of each other.function arePermutations($a, $b, $n, $m){ $sum1 = 0; $sum2 = 0; $mul1 = 1; $mul2 = 1; // Calculating sum and multiply // of first array for ($i = 0; $i < $n; $i++) { $sum1 += $a[$i]; $mul1 *= $a[$i]; } // Calculating sum and multiply // of second array for ($i = 0; $i < $m; $i++) { $sum2 += $b[$i]; $mul2 *= $b[$i]; } // If sum and mul of both arrays // are equal, return true, else // return false. return (($sum1 == $sum2) && ($mul1 == $mul2));}// Driver code$a = array( 1, 3, 2 );$b = array( 3, 1, 2 );$n = sizeof($a);$m = sizeof($b);if (arePermutations($a, $b, $n, $m)) echo "Yes" . "\n";else echo "No" . "\n";// This code is contributed // by Akanksha Rai(Abby_akku) |
Output
Yes
Complexity Analysis:
- Time Complexity: O(n) where n is size of given array
- Auxiliary space: O(1) as it is using constant space
Efficient Approach:
To determine if two arrays are permutations of each other, we can use the following approach with O(1) time complexity:
- Check if the sizes of both arrays are equal. If not, return false.
- Calculate the XOR of all elements in both arrays.
- If the XOR result is 0, it means the arrays have the same elements (although the order may be different) and are permutations of each other. Return true.
- If the XOR result is not 0, return false.
Here’s the modified code using this approach:
C++
#include <iostream>using namespace std;// Function to check if arrays are permutations of each other.bool arePermutations(int a[], int b[], int n, int m) { if (n != m) { return false; } int xorResult = 0; // Calculate XOR of all elements in both arrays for (int i = 0; i < n; i++) { xorResult ^= a[i]; xorResult ^= b[i]; } // If XOR result is 0, arrays are permutations of each other return (xorResult == 0);}// Driver codeint main() { int a[] = {2,1,3,5,4,3,2}; int b[] = {3, 2,2,4,5,3,1}; int n = sizeof(a) / sizeof(int); int m = sizeof(b) / sizeof(int); if (arePermutations(a, b, n, m)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0;} |
Java
import java.util.Arrays;public class PermutationCheck { // Function to check if arrays are permutations of each other. public static boolean arePermutations(int[] a, int[] b, int n, int m) { if (n != m) { return false; } int xorResult = 0; // Calculate XOR of all elements in both arrays for (int i = 0; i < n; i++) { xorResult ^= a[i]; xorResult ^= b[i]; } // If XOR result is 0, arrays are permutations of each other return (xorResult == 0); } // Driver code public static void main(String[] args) { int[] a = {2, 1, 3, 5, 4, 3, 2}; int[] b = {3, 2, 2, 4, 5, 3, 1}; int n = a.length; int m = b.length; if (arePermutations(a, b, n, m)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python3
# Function to check if arrays are permutations of each other.def are_permutations(a, b): n = len(a) m = len(b) if n != m: return False xor_result = 0 # Calculate XOR of all elements in both arrays for i in range(n): xor_result ^= a[i] xor_result ^= b[i] # If XOR result is 0, arrays are permutations of each other return (xor_result == 0)# Driver codea = [2, 1, 3, 5, 4, 3, 2]b = [3, 2, 2, 4, 5, 3, 1]if are_permutations(a, b): print("Yes")else: print("No")# This code is contributed by akshitaguprzj3 |
C#
using System;class Program{ // Function to check if arrays are permutations of each other. static bool ArePermutations(int[] a, int[] b, int n, int m) { if (n != m) { return false; } int xorResult = 0; // Calculate XOR of all elements in both arrays for (int i = 0; i < n; i++) { xorResult ^= a[i]; xorResult ^= b[i]; } // If XOR result is 0, arrays are permutations of each other return (xorResult == 0); } static void Main(string[] args) { int[] a = { 2, 1, 3, 5, 4, 3, 2 }; int[] b = { 3, 2, 2, 4, 5, 3, 1 }; int n = a.Length; int m = b.Length; if (ArePermutations(a, b, n, m)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }}// This code is contributed by shivamgupta310570 |
Javascript
// Function to check if arrays are permutations of each other.function arePermutations(a, b, n, m) { // If the arrays have different lengths, they can't be permutations. if (n !== m) { return false; } let xorResult = 0; // Calculate XOR of all elements in both arrays. for (let i = 0; i < n; i++) { xorResult ^= a[i]; xorResult ^= b[i]; } // If XOR result is 0, arrays are permutations of each other. return xorResult === 0;}// Driver codefunction main() { const a = [2, 1, 3, 5, 4, 3, 2]; const b = [3, 2, 2, 4, 5, 3, 1]; const n = a.length; const m = b.length; if (arePermutations(a, b, n, m)) { console.log("Yes"); } else { console.log("No"); }}main(); |
Output
Yes
Complexity Analysis:
Time Complexity: O(n) where n is size of given array.
Auxiliary space: O(1) as it is using constant space
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!
