Dada una array arr[] de N enteros, la tarea es contar los pares de índices (i, j) tales que 0 ≤ i < j ≤ N y arr[i] | arr[j] ≤ max(arr[i], arr[j]) donde | es el OR bit a bit.
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 2
(1, 3) y (2, 3) son los únicos pares válidos.
Entrada: arr[] = {11, 45, 12, 14, 5}
Salida: 3
Enfoque: ejecute dos bucles anidados y verifique todos los pares posibles. Si arr[i] | arr[j] <= max(arr[i], arr[j]) luego incremente el conteo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count of valid pairs int countPairs(int arr[], int n) { int cnt = 0; // Check all possible pairs for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) if ((arr[i] | arr[j]) <= max(arr[i], arr[j])) cnt++; return cnt; } // Driver code int main() { int arr[] = { 1, 2, 3 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countPairs(arr, n); return 0; }
Java
// Java implementation of the approach class GFG { // Function to return the count of valid pairs static int countPairs(int arr[], int n) { int cnt = 0; // Check all possible pairs for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) if ((arr[i] | arr[j]) <= Math.max(arr[i], arr[j])) cnt++; return cnt; } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 3 }; int n = arr.length; System.out.println(countPairs(arr, n)); } } // This code is Contributed by Code_Mech.
Python3
# Python 3 implementation of the approach # Function to return the count # of valid pairs def countPairs(arr, n): cnt = 0 # Check all possible pairs for i in range(n - 1): for j in range(i + 1, n, 1): if ((arr[i] | arr[j]) <= max(arr[i], arr[j])): cnt += 1 return cnt # Driver code if __name__ == '__main__': arr = [1, 2, 3] n = len(arr) print(countPairs(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach using System; class GFG { // Function to return the count of valid pairs static int countPairs(int []arr, int n) { int cnt = 0; // Check all possible pairs for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) if ((arr[i] | arr[j]) <= Math.Max(arr[i], arr[j])) cnt++; return cnt; } // Driver code static void Main() { int []arr = { 1, 2, 3 }; int n = arr.Length; Console.WriteLine(countPairs(arr, n)); } } // This code is Contributed by mits.
PHP
<?php // PHP implementation of the approach // Function to return the count of valid pairs function countPairs($arr, $n) { $cnt = 0; // Check all possible pairs for ($i = 0; $i < $n - 1; $i++) for ($j = $i + 1; $j < $n; $j++) if (($arr[$i] | $arr[$j]) <= max($arr[$i], $arr[$j])) $cnt++; return $cnt; } // Driver code $arr = array(1, 2, 3); $n = sizeof($arr); echo countPairs($arr, $n); // This code is contributed // by Akanksha Rai ?>
Javascript
<script> // JavaScript implementation of the approach // Function to return the count of valid pairs function countPairs(arr, n) { let cnt = 0; // Check all possible pairs for (let i = 0; i < n - 1; i++) for (let j = i + 1; j < n; j++) if ((arr[i] | arr[j]) <= Math.max(arr[i], arr[j])) cnt++; return cnt; } // Driver code let arr = [1, 2, 3]; let n = arr.length; document.write(countPairs(arr, n)); // This code is contributed by _saurabh_jaiswal </script>
Producción:
2