Check if two arrays are permutations of each other using Mathematical Operation

0 0 8 minutes read

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 code
int 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 other
 
import 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 other
def 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 other
using 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 code
public 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 code
int 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 code
a = [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 code
function 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 zambiatek!