Дан массив A [] размера N. Задача состоит в том, чтобы найти, сколько пар (i, j) существует таких, что A [i] OR A [j] нечетно.
Примеры :
Ввод : N = 4
A [] = {5, 6, 2, 8}
Выход : 3
Пояснение :
Поскольку пара A [] = (5, 6), (5, 2), (5, 8),
(6, 2), (6, 8), (2, 8)
5 ИЛИ 6 = 7, 5 ИЛИ 2 = 7, 5 ИЛИ 8 = 13
6 ИЛИ 2 = 6, 6 ИЛИ 8 = 14, 2 ИЛИ 8 = 10
Всего пара A (i, j) = 6 и Odd = 3
Ввод : N = 7
A [] = {8, 6, 2, 7, 3, 4, 9}
Выход : 15Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Простое решение - проверить каждую пару и найти побитовое ИЛИ и посчитать все такие пары с побитовым ИЛИ как нечетные.
Ниже представлена реализация описанного выше подхода:
C ++
#include <iostream> using namespace std; int findOddPair( int A[], int N) { int oddPair = 0;
for ( int i = 0; i < N; i++) {
for ( int j = i + 1; j < N; j++) {
if ((A[i] | A[j]) % 2 != 0)
oddPair++;
}
}
return oddPair;
} int main() { int A[] = { 5, 6, 2, 8 };
int N = sizeof (A) / sizeof (A[0]);
cout << findOddPair(A, N) << endl;
return 0;
} |
Джава
class GFG { 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++)
{
if ((A[i] | A[j]) % 2 != 0 )
oddPair++;
}
}
return oddPair;
} public static void main(String []args) { int A[] = { 5 , 6 , 2 , 8 };
int N = A.length;
System.out.println(findOddPair(A, N));
} } |
Python3
def findOddPair(A, N):
oddPair = 0
for i in range ( 0 , N):
for j in range (i + 1 , N):
if ((A[i] | A[j]) % 2 ! = 0 ):
oddPair + = 1
return oddPair
def main():
A = [ 5 , 6 , 2 , 8 ]
N = len (A)
print (findOddPair(A, N))
if __name__ = = '__main__' : main()
|
C #
using System; public class GFG{
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++)
{
if ((A[i] | A[j]) % 2 != 0)
oddPair++;
}
}
return oddPair;
} static public void Main (){
int []A = { 5, 6, 2, 8 };
int N = A.Length;
Console.WriteLine(findOddPair(A, N));
}
} |
PHP
<?php function findOddPair( $A , $N ) { $oddPair = 0;
for ( $i = 0; $i < $N ; $i ++) {
for ( $j = $i + 1; $j < $N ; $j ++) {
if (( $A [ $i ] | $A [ $j ]) % 2 != 0)
$oddPair ++;
}
}
return $oddPair ;
} $A = array (5, 6, 2, 8 );
$N = sizeof( $A ) / sizeof( $A [0]);
echo findOddPair( $A , $N ), "
" ;
#This code is contributed by ajit ?> |
Javascript
<script> function findOddPair(A, N) { let oddPair = 0;
for (let i = 0; i < N; i++)
{
for (let j = i + 1; j < N; j++)
{
if ((A[i] | A[j]) % 2 != 0)
oddPair++;
}
}
return oddPair;
} let A = [ 5, 6, 2, 8 ]; let N = A.length; document.write(findOddPair(A, N)); </script> |
Сложность времени : O (N 2 )
Эффективное решение - подсчитать пары с четным ИЛИ и вычесть их из общего количества пар, чтобы получить пары с нечетным побитовым ИЛИ. Для этого подсчитайте числа с последним битом как 0. Тогда количество пар с четным побитовым ИЛИ = count * (count - 1) / 2 и общее количество пар будет N * (N-1) / 2.
Следовательно, пары с ODD Bitwise-OR будут:
Total Pairs - Pairs with EVEN Bitwise-OR
Ниже представлена реализация описанного выше подхода:
C ++
#include <iostream> using namespace std; int countOddPair( int A[], int N) {
int count = 0;
for ( int i = 0; i < N; i++)
if (!(A[i] & 1))
count++;
int evenPairCount = count * (count - 1) / 2;
int totPairs = N * (N - 1) / 2;
return totPairs - evenPairCount;
} int main() { int A[] = { 5, 6, 2, 8 };
int N = sizeof (A) / sizeof (A[0]);
cout << countOddPair(A, N) << endl;
return 0;
} |
Джава
public class GFG { static int countOddPair( int A[], int N) {
int count = 0 ;
for ( int i = 0 ; i < N; i++) {
if ((A[i] % 2 != 1 )) {
count++;
}
}
int evenPairCount = count * (count - 1 ) / 2 ;
int totPairs = N * (N - 1 ) / 2 ;
return totPairs - evenPairCount;
}
public static void main(String[] args) {
int A[] = { 5 , 6 , 2 , 8 };
int N = A.length;
System.out.println(countOddPair(A, N));
}
} |
Python3
def countOddPair(A, N):
count = 0
for i in range ( 0 , N):
if (A[i] % 2 ! = 1 ):
count + = 1
evenPairCount = count * (count - 1 ) / 2
totPairs = N * (N - 1 ) / 2
return ( int )(totPairs - evenPairCount)
A = [ 5 , 6 , 2 , 8 ] N = len (A) print (countOddPair(A, N)) |
C #
using System; public class GFG { static int countOddPair( int []A, int N) {
int count = 0;
for ( int i = 0; i < N; i++) {
if ((A[i] % 2 != 1)) {
count++;
}
}
int evenPairCount = count * (count - 1) / 2;
int totPairs = N * (N - 1) / 2;
return totPairs - evenPairCount;
}
public static void Main() {
int []A = {5, 6, 2, 8};
int N = A.Length;
Console.WriteLine(countOddPair(A, N));
}
} |
PHP
<?php function countOddPair( $A , $N ) {
$count = 0;
for ( $i = 0; $i < $N ; $i ++)
if (!( $A [ $i ] & 1))
$count ++;
$evenPairCount = $count *
( $count - 1) / 2;
$totPairs = $N * ( $N - 1) / 2;
return ( $totPairs - $evenPairCount );
} $A = array ( 5, 6, 2, 8 ); $N = sizeof( $A ); echo countOddPair( $A , $N ), "
" ; ?> |
Javascript
<script> function countOddPair(A, N) {
let count = 0;
for (let i = 0; i < N; i++)
if (!(A[i] & 1))
count++;
let evenPairCount =
parseInt(count * (count - 1) / 2);
let totPairs = parseInt(N * (N - 1) / 2);
return totPairs - evenPairCount;
} let A = [ 5, 6, 2, 8 ];
let N = A.length;
document.write(countOddPair(A, N));
</script> |
Сложность времени : O (N)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.