Dada una array A[] de tamaño N. La tarea es encontrar cuántos pares (i, j) existen de modo que A[i] O A[j] sea impar.
Ejemplos :
Input : N = 4 A[] = { 5, 6, 2, 8 } Output : 3 Explanation : Since pair of A[] = ( 5, 6 ), ( 5, 2 ), ( 5, 8 ), ( 6, 2 ), ( 6, 8 ), ( 2, 8 ) 5 OR 6 = 7, 5 OR 2 = 7, 5 OR 8 = 13 6 OR 2 = 6, 6 OR 8 = 14, 2 OR 8 = 10 Total pair A( i, j ) = 6 and Odd = 3 Input : N = 7 A[] = {8, 6, 2, 7, 3, 4, 9} Output :15
Una solución simple es verificar cada par y encontrar el OR bit a bit y contar todos esos pares con OR bit a bit como impares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count pairs with odd OR #include <iostream> using namespace std; // Function to count pairs with odd OR int findOddPair(int A[], int N) { int oddPair = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // find OR operation // check odd or odd if ((A[i] | A[j]) % 2 != 0) oddPair++; } } // return count of odd pair return oddPair; } // Driver Code int main() { int A[] = { 5, 6, 2, 8 }; int N = sizeof(A) / sizeof(A[0]); cout << findOddPair(A, N) << endl; return 0; }
C
// C program to count pairs with odd OR #include <stdio.h> // Function to count pairs with odd OR int findOddPair(int A[], int N) { int oddPair = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // find OR operation // check odd or odd if ((A[i] | A[j]) % 2 != 0) oddPair++; } } // return count of odd pair return oddPair; } // Driver Code int main() { int A[] = { 5, 6, 2, 8 }; int N = sizeof(A) / sizeof(A[0]); printf("%d\n",findOddPair(A, N)); return 0; } // This code is contributed by kothavvsaakash.
Java
// Java program to count pairs // with odd OR class GFG { // Function to count pairs with odd OR static int findOddPair(int A[], int N) { int oddPair = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // find OR operation // check odd or odd if ((A[i] | A[j]) % 2 != 0) oddPair++; } } // return count of odd pair return oddPair; } // Driver Code public static void main(String []args) { int A[] = { 5, 6, 2, 8 }; int N = A.length; System.out.println(findOddPair(A, N)); } } // This code is contributed by ANKITRAI1
Python3
# Python3 program to count pairs with odd OR # Function to count pairs with odd OR def findOddPair(A, N): oddPair = 0 for i in range(0, N): for j in range(i+1, N): # find OR operation # check odd or odd if ((A[i] | A[j]) % 2 != 0): oddPair+=1 # return count of odd pair return oddPair # Driver Code def main(): A = [ 5, 6, 2, 8 ] N = len(A) print(findOddPair(A, N)) if __name__ == '__main__': main() # This code is contributed by PrinciRaj1992
C#
// C# program to count pairs // with odd OR using System; public class GFG{ // Function to count pairs with odd OR static int findOddPair(int[] A, int N) { int oddPair = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // find OR operation // check odd or odd if ((A[i] | A[j]) % 2 != 0) oddPair++; } } // return count of odd pair return oddPair; } // Driver Code static public void Main (){ int []A = { 5, 6, 2, 8 }; int N = A.Length; Console.WriteLine(findOddPair(A, N)); } } //This code is contributed by ajit
PHP
<?php //PHP program to count pairs with odd OR // Function to count pairs with odd OR function findOddPair($A, $N) { $oddPair = 0; for ($i = 0; $i < $N; $i++) { for ($j = $i + 1; $j < $N; $j++) { // find OR operation // check odd or odd if (($A[$i] | $A[$j]) % 2 != 0) $oddPair++; } } // return count of odd pair return $oddPair; } // Driver Code $A = array (5, 6, 2, 8 ); $N = sizeof($A) / sizeof($A[0]); echo findOddPair($A, $N),"\n"; #This code is contributed by ajit ?>
Javascript
<script> // Javascript program to count pairs with odd OR // Function to count pairs with odd OR function findOddPair(A, N) { let oddPair = 0; for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { // find OR operation // check odd or odd if ((A[i] | A[j]) % 2 != 0) oddPair++; } } // return count of odd pair return oddPair; } // Driver Code let A = [ 5, 6, 2, 8 ]; let N = A.length; document.write(findOddPair(A, N)); // This code is contributed by souravmahato348. </script>
3
Complejidad de tiempo : O(N 2 )
Una solución eficiente es contar pares con OR par y restarlos con un número total de pares para obtener pares con OR bit a bit impar. Para hacer esto, cuente los números con el último bit como 0. Luego, un número de pares con Bitwise-OR par = count * (count – 1)/2 y el número total de pares será N*(N-1)/2.
Por tanto, los pares con ODD Bitwise-OR serán:
Total Pairs - Pairs with EVEN Bitwise-OR
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count pairs with odd OR #include <iostream> using namespace std; // Function to count pairs with odd OR int countOddPair(int A[], int N) { // Count total even numbers in // array int count = 0; for (int i = 0; i < N; i++) if (!(A[i] & 1)) count++; // Even pair count int evenPairCount = count * (count - 1) / 2; // Total pairs int totPairs = N * (N - 1) / 2; // Return Odd pair count return totPairs - evenPairCount; } // Driver main int main() { int A[] = { 5, 6, 2, 8 }; int N = sizeof(A) / sizeof(A[0]); cout << countOddPair(A, N) << endl; return 0; }
Java
// Java program to count pairs with odd OR public class GFG { // Function to count pairs with odd OR static int countOddPair(int A[], int N) { // Count total even numbers in // array int count = 0; for (int i = 0; i < N; i++) { if ((A[i] % 2 != 1)) { count++; } } // Even pair count int evenPairCount = count * (count - 1) / 2; // Total pairs int totPairs = N * (N - 1) / 2; // Return Odd pair count return totPairs - evenPairCount; } // Driver main public static void main(String[] args) { int A[] = {5, 6, 2, 8}; int N = A.length; System.out.println(countOddPair(A, N)); } }
Python3
# Python 3program to count pairs with odd OR # Function to count pairs with odd OR def countOddPair(A, N): # Count total even numbers in # array count = 0 for i in range(0, N): if (A[i] % 2 != 1): count+=1 # Even pair count evenPairCount = count * (count - 1) / 2 # Total pairs totPairs = N * (N - 1) / 2 # Return Odd pair count return (int)(totPairs - evenPairCount) # Driver Code A = [ 5, 6, 2, 8 ] N = len(A) print(countOddPair(A, N)) # This code is contributed by PrinciRaj1992
C#
// C# program to count pairs with odd OR using System; public class GFG { // Function to count pairs with odd OR static int countOddPair(int []A, int N) { // Count total even numbers in // array int count = 0; for (int i = 0; i < N; i++) { if ((A[i] % 2 != 1)) { count++; } } // Even pair count int evenPairCount = count * (count - 1) / 2; // Total pairs int totPairs = N * (N - 1) / 2; // Return Odd pair count return totPairs - evenPairCount; } // Driver main public static void Main() { int []A = {5, 6, 2, 8}; int N = A.Length; Console.WriteLine(countOddPair(A, N)); } } /*This code is contributed by PrinciRaj1992*/
PHP
<?php // PHP program to count pairs with odd OR // Function to count pairs with odd OR function countOddPair( $A, $N) { // Count total even numbers // in array $count = 0; for ($i = 0; $i < $N; $i++) if (!($A[$i] & 1)) $count++; // Even pair count $evenPairCount = $count * ($count - 1) / 2; // Total pairs $totPairs = $N * ($N - 1) / 2; // Return Odd pair count return ($totPairs - $evenPairCount); } // Driver main $A = array( 5, 6, 2, 8 ); $N = sizeof($A); echo countOddPair($A, $N),"\n"; // This code is contributed by Sach_Code ?>
Javascript
<script> // Javascript program to count // pairs with odd OR // Function to count pairs with odd OR function countOddPair(A, N) { // Count total even numbers in // array let count = 0; for (let i = 0; i < N; i++) if (!(A[i] & 1)) count++; // Even pair count let evenPairCount = parseInt(count * (count - 1) / 2); // Total pairs let totPairs = parseInt(N * (N - 1) / 2); // Return Odd pair count return totPairs - evenPairCount; } // Driver main let A = [ 5, 6, 2, 8 ]; let N = A.length; document.write(countOddPair(A, N)); </script>
3
Complejidad de tiempo : O(N)
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA