Счетчик четных и нечетных битов с элементом массива после XOR с K

Опубликовано: 1 Декабря, 2021

Дан массив arr [] и число K. Задача состоит в том, чтобы найти количество элементов, имеющих нечетное и четное число установленного бита после выполнения XOR of K с каждым элементом данного arr [] .

Примеры:

Input: arr[] = {4, 2, 15, 9, 8, 8}, K = 3
Output: Even = 2, Odd = 4
Explanation:
The binary representation of the element after taking XOR with K are:
4 ^ 3 = 7 (111)
2 ^ 3 = 1 (1)
15 ^ 3 = 12 (1100)
9 ^ 3 = 10 (1010)
8 ^ 3 = 11 (1011)
8 ^ 3 = 11 (1011)
No of elements with even no of 1’s in binary representation : 2 (12, 10)
No of elements with odd no of 1’s in binary representation : 4 (7, 1, 11, 11)
Input: arr[] = {4, 2, 15, 9, 8, 8}, K = 6
Output: Even = 4, Odd = 2

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: наивный подход состоит в том, чтобы выполнить побитовое исключающее ИЛИ для K с каждым элементом данного массива arr [], а затем подсчитать установленный бит для каждого элемента в массиве после выполнения XOR с K.

Сложность времени: O (N * K)

Эффективный подход:
С помощью следующего наблюдения мы имеем:

For Example:
If A = 4 and K = 3
Binary Representation:
A = 100
K = 011
A^K = 111
Therefore, the XOR of number A(which has an odd number of set-bit) with the number K(which has an even number of set-bit) results in an odd number of set-bit.
And If A = 4 and K = 7
Binary Representation:
A = 100
K = 111
A^K = 011
Therefore, the XOR of number A(which has an odd number of set-bit) with the number K(which has an odd number of set-bit) results in an even number of set-bit.

Из приведенных выше наблюдений:

Если K имеет нечетное количество установочных битов, то количество элементов массива arr [] с четным установленным битом и нечетным установленным битом после выполнения XOR с K будет таким же, как количество четных установочных битов и нечетных set-bit int массив перед XOR.
Если K имеет четное количество битов установки, то счетчик элементов массива arr [] с четным битом установки и нечетным битом установки после выполнения XOR с K будет обратным, как количество четных битов установки и нечетных наборов -бит в массиве перед XOR.

Шаги :

Сохраните количество элементов, имеющих четный установленный бит и нечетный установленный бит из данного массива arr [] .
Если K имеет нечетный установленный бит, то количество четных и нечетных установленных битов после XOR с K будет таким же, как количество четных и нечетных установленных битов, вычисленное выше.
Если K имеет четный установленный бит, то количество четных и нечетных установленных битов после XOR с K будет подсчетом нечетных и четных установленных битов, вычисленных выше.

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ program to count the set
 // bits after taking XOR with a
 // number K
 #include <bits/stdc++.h>
 using namespace std;
 
// Function to store EVEN and odd variable
 void countEvenOdd( int arr[], int n, int K)
 {
    int even = 0, odd = 0;
 
    // Store the count of even and
    // odd set bit
    for ( int i = 0; i < n; i++) {
 
        // Count the set bit using
        // in built function
        int x = __builtin_popcount(arr[i]);
        if (x % 2 == 0)
            even++;
        else
            odd++;
    }
 
    int y;
 
    // Count of set-bit of K
    y = __builtin_popcount(K);
 
    // If y is odd then, count of
    // even and odd set bit will
    // be interchanged
    if (y & 1) {
        cout << "Even = " << odd
             << ", Odd = " << even;
    }
 
    // Else it will remain same as
    // the original array
    else {
        cout << "Even = " << even
             << ", Odd = " << odd;
    }
 }
 
// Driver's Code
 int main( void )
 {
    int arr[] = { 4, 2, 15, 9, 8, 8 };
    int K = 3;
    int n = sizeof (arr) / sizeof (arr[0]);
 
    // Function call to count even
    // and odd
    countEvenOdd(arr, n, K);
    return 0;
 }

Ява

 // Java program to count the set
 // bits after taking XOR with a
 // number K
 class GFG {
 
     
    /* Function to get no of set
    bits in binary representation
    of positive integer n */
    static int __builtin_popcount( int n)
    {
        int count = 0 ;
        while (n > 0 ) {
            count += n & 1 ;
            n >>= 1 ;
        }
        count; return
    }
     
    // Function to store EVEN and odd variable
    static void countEvenOdd( int arr[], int n, int K)
    {
        int even = 0 , odd = 0 ;
     
        // Store the count of even and
        // odd set bit
        for ( int i = 0 ; i < n; i++) {
     
            // Count the set bit using
            // in built function
            int x = __builtin_popcount(arr[i]);
            if (x % 2 == 0 )
                even++;
            else
                odd++;
        }
     
        int y;
     
        // Count of set-bit of K
        y = __builtin_popcount(K);
     
        // If y is odd then, count of
        // even and odd set bit will
        // be interchanged
        if ((y & 1 ) != 0 ) {
            System.out.println( "Even = " + odd + ", Odd = " + even);
        }
     
        // Else it will remain same as
        // the original array
        else {
            System.out.println( "Even = " + even + ", Odd = " + odd);
        }
    }
     
    // Driver's Code
    public static void main (String[] args)
    {
        int arr[] = { 4 , 2 , 15 , 9 , 8 , 8 };
        int K = 3 ;
        int n = arr.length;
     
        // Function call to count even
        // and odd
        countEvenOdd(arr, n, K);
    }
  
}
 // This code is contributed by Yash_R

Python3

 # Python3 program to count the set
 # bits after taking XOR with a
 # number K
 
# Function to store EVEN and odd variable
 def countEvenOdd(arr, n, K) :
 
    even = 0 ; odd = 0 ;
 
    # Store the count of even and
    # odd set bit
    for i in range (n) :
 
        # Count the set bit using
        # in built function
        x = bin (arr[i]).count( '1' );
        if (x % 2 = = 0 ) :
            even + = 1 ;
        else :
            odd + = 1 ;
 
    # Count of set-bit of K
    y = bin (K).count( '1' );
 
    # If y is odd then, count of
    # even and odd set bit will
    # be interchanged
    if (y & 1 ) :
        print ( "Even =" ,odd , ", Odd =" , even);
 
    # Else it will remain same as
    # the original array
    else :
        print ( "Even =" , even , ", Odd =" , odd);
 
 
# Driver's Code
 if __name__ = = "__main__" :
     
    arr = [ 4 , 2 , 15 , 9 , 8 , 8 ];
    K = 3 ;
    n = len (arr);
 
    # Function call to count even
    # and odd
    countEvenOdd(arr, n, K);
     
# This code is contributed by Yash_R

C #

 // C# program to count the set
 // bits after taking XOR with a
 // number K
 using System;
 
public class GFG {
 
     
    /* Function to get no of set
    bits in binary representation
    of positive integer n */
    static int __builtin_popcount( int n)
    {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        count; return
    }
     
    // Function to store EVEN and odd variable
    static void countEvenOdd( int []arr, int n, int K)
    {
        int even = 0, odd = 0;
     
        // Store the count of even and
        // odd set bit
        for ( int i = 0; i < n; i++) {
     
            // Count the set bit using
            // in built function
            int x = __builtin_popcount(arr[i]);
            if (x % 2 == 0)
                even++;
            else
                odd++;
        }
     
        int y;
     
        // Count of set-bit of K
        y = __builtin_popcount(K);
     
        // If y is odd then, count of
        // even and odd set bit will
        // be interchanged
        if ((y & 1) != 0) {
            Console.WriteLine( "Even = " + odd + ", Odd = " + even);
        }
     
        // Else it will remain same as
        // the original array
        else {
            Console.WriteLine( "Even = " + even + ", Odd = " + odd);
        }
    }
     
    // Driver's Code
    public static void Main ( string [] args)
    {
        int []arr = { 4, 2, 15, 9, 8, 8 };
        int K = 3;
        int n = arr.Length;
     
        // Function call to count even
        // and odd
        countEvenOdd(arr, n, K);
    }
  
}
 // This code is contributed by Yash_R

Выход:

Четный = 2, Нечетный = 4

Сложность времени: O (N)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Алгоритмы

Счетчик четных и нечетных битов с элементом массива после XOR с K

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C ++

Ява

Python3

C #

РЕКОМЕНДУЕМЫЕ СТАТЬИ