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>
Producción:
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>
Producción:
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