XOR de elementos de array cuyo inverso modular con un número dado existe

Posted on by Rudeus Greyrat

Dada una array arr[] de longitud N y un entero positivo M , la tarea es encontrar el XOR bit a bit de todos los elementos de la array cuyo inverso modular con M existe.

Ejemplos:

Entrada: arr[] = {1, 2, 3}, M = 4
Salida: 2
Explicación:
Inicialice el valor xor con 0:
para el elemento indexado en 0, es decir, 1, su módulo inverso con 4 es 1 porque (1 * 1 ) % 4 = 1 es decir, existe. Por lo tanto, xor = (xor ^ 1) = 1.
Para el elemento indexado en 1, es decir, 2, su mod inverso no existe.
Para el elemento indexado en 2, es decir, 3, su módulo inverso con 4 es 3 porque (3 * 3) % 4 = 1, es decir, existe. Por lo tanto, xor = (xor ^ 3) = 2.
Por lo tanto, xor es 2.

Entrada: arr[] = {3, 6, 4, 5, 8}, M = 9
Salida: 9
Explicación:
Inicialice el valor xor con 0:
para el elemento indexado en 0, es decir, 3, su mod inverso no existe.
Para el elemento indexado en 1, es decir, 6, su mod inversa no existe.
Para el elemento indexado en 2, es decir, 4, su módulo inverso con 9 es 7 porque (4 * 7) % 9 = 1, es decir, existe. Por lo tanto, xor = (xor ^ 4) = 4.
Para el elemento indexado en 3, es decir, 5, su módulo inverso con 9 es 2 porque (5 * 2) % 9 = 1, es decir, existe. Por lo tanto, xor = (xor ^ 5) = 1.
Para el elemento indexado en 4, es decir, 8, su módulo inverso con 9 es 8 porque (8 * 8) % 9 = 1, es decir, existe. Por lo tanto, xor = (xor ^ 8) = 9.
Por lo tanto, xor es 9.

Enfoque ingenuo : el enfoque más simple es imprimir el XOR de todos los elementos de la array para los que existe cualquier j donde (1 <= j < M) tal que (arr[i] * j) % M = 1 donde 0 ≤ yo < N .

Complejidad temporal: O(N * M)
Espacio auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar la propiedad de que el inverso modular de cualquier número X bajo mod M existe si y solo si el GCD de M y X es 1 , es decir, mcd (M, X) es 1 . Siga los pasos a continuación para resolver el problema:

  1. Inicialice una variable xor con 0 , para almacenar el xor de todos los elementos cuyo inverso modular bajo M existe.
  2. Recorra la array sobre el rango [0, N – 1] .
  3. Si gcd(M, arr[i]) es 1 , actualice xor como xor = (xor^arr[i]) .
  4. Después de atravesar, imprima el valor xor como el resultado requerido.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the gcd of a & b
int gcd(int a, int b)
{
    // Base Case
    if (a == 0)
        return b;
     
     // Recursively calculate GCD
    return gcd(b % a, a);
}
 
// Function to print the Bitwise XOR of
// elements of arr[] if gcd(arr[i], M) is 1
void countInverse(int arr[], int N, int M)
{
    // Initialize xor
    int XOR = 0;
 
    // Traversing the array
    for (int i = 0; i < N; i++) {
 
        // GCD of M and arr[i]
        int gcdOfMandelement
          = gcd(M, arr[i]);
 
        // If GCD is 1, update xor
        if (gcdOfMandelement == 1) {
 
            XOR ^= arr[i];
        }
    }
 
    // Print xor
    cout << XOR << ' ';
}
 
// Drive Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 2, 3 };
 
    // Given number M
    int M = 4;
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    countInverse(arr, N, M);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to return the gcd of a & b
static int gcd(int a, int b)
{
     
    // Base Case
    if (a == 0)
        return b;
 
    // Recursively calculate GCD
    return gcd(b % a, a);
}
 
// Function to print the Bitwise XOR of
// elements of arr[] if gcd(arr[i], M) is 1
static void countInverse(int[] arr, int N, int M)
{
     
    // Initialize xor
    int XOR = 0;
 
    // Traversing the array
    for(int i = 0; i < N; i++)
    {
         
        // GCD of M and arr[i]
        int gcdOfMandelement = gcd(M, arr[i]);
 
        // If GCD is 1, update xor
        if (gcdOfMandelement == 1)
        {
            XOR ^= arr[i];
        }
    }
 
    // Print xor
    System.out.println(XOR);
}
 
// Drive Code
public static void main(String[] args)
{
 
    // Given array arr[]
    int[] arr = { 1, 2, 3 };
 
    // Given number M
    int M = 4;
 
    // Size of the array
    int N = arr.length;
 
    // Function Call
    countInverse(arr, N, M);
}
}
 
// This code is contributed by akhilsaini

Python3

# Python3 program for the above approach
 
# Function to return the gcd of a & b
def gcd(a, b):
     
    # Base Case
    if (a == 0):
        return b
 
    # Recursively calculate GCD
    return gcd(b % a, a)
 
# Function to print the Bitwise XOR of
# elements of arr[] if gcd(arr[i], M) is 1
def countInverse(arr, N, M):
 
    # Initialize xor
    XOR = 0
 
    # Traversing the array
    for i in range(0, N):
 
        # GCD of M and arr[i]
        gcdOfMandelement = gcd(M, arr[i])
 
        # If GCD is 1, update xor
        if (gcdOfMandelement == 1):
            XOR = XOR ^ arr[i]
 
    # Print xor
    print(XOR)
 
# Drive Code
if __name__ == '__main__':
 
    # Given array arr[]
    arr = [ 1, 2, 3 ]
 
    # Given number M
    M = 4
 
    # Size of the array
    N = len(arr)
 
    # Function Call
    countInverse(arr, N, M)
 
# This code is contributed by akhilsaini

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to return the gcd of a & b
static int gcd(int a, int b)
{
     
    // Base Case
    if (a == 0)
        return b;
 
    // Recursively calculate GCD
    return gcd(b % a, a);
}
 
// Function to print the Bitwise XOR of
// elements of arr[] if gcd(arr[i], M) is 1
static void countInverse(int[] arr, int N, int M)
{
     
    // Initialize xor
    int XOR = 0;
 
    // Traversing the array
    for(int i = 0; i < N; i++)
    {
         
        // GCD of M and arr[i]
        int gcdOfMandelement = gcd(M, arr[i]);
 
        // If GCD is 1, update xor
        if (gcdOfMandelement == 1)
        {
 
            XOR ^= arr[i];
        }
    }
 
    // Print xor
    Console.WriteLine(XOR);
}
 
// Drive Code
public static void Main()
{
 
    // Given array arr[]
    int[] arr = { 1, 2, 3 };
 
    // Given number M
    int M = 4;
 
    // Size of the array
    int N = arr.Length;
 
    // Function Call
    countInverse(arr, N, M);
}
}
 
// This code is contributed by akhilsaini

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to return the gcd of a & b
function gcd(a, b)
{
     
    // Base Case
    if (a == 0)
        return b;
 
    // Recursively calculate GCD
    return gcd(b % a, a);
}
 
// Function to print the Bitwise XOR of
// elements of arr[] if gcd(arr[i], M) is 1
function countInverse(arr, N, M)
{
     
    // Initialize xor
    var XOR = 0;
 
    // Traversing the array
    for(var i = 0; i < N; i++)
    {
         
        // GCD of M and arr[i]
        var gcdOfMandelement = gcd(M, arr[i]);
 
        // If GCD is 1, update xor
        if (gcdOfMandelement == 1)
        {
            XOR ^= arr[i];
        }
    }
 
    // Print xor
    document.write(XOR);
}
 
// Driver Code
 
// Given array arr[]
var arr = [ 1, 2, 3 ];
 
// Given number M
var M = 4;
 
// Size of the array
var N = arr.length;
 
// Function Call
countInverse(arr, N, M);
 
// This code is contributed by Kirti
 
</script>
Producción: 

2

 

Complejidad de tiempo: O(N*log M)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por doreamon_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *