Finden Sie Tripel in einem Array, dessen AND maximal ist
Gegeben sei ein Array positiver Ganzzahlen der Größe n. Finden Sie die Anzahl der Tripletts, deren AND maximal ist, und finden Sie auch dieses Maximum unter der Voraussetzung, dass i < j < k ist, wobei i, j, k die Indizes der Zahlen sind.
Angenommen, die Zahlen sind nicht größer als 10^9 .
Beispiele:
Eingabe : a[] = {1, 2, 3, 4, 5, 6}
Ausgabe : 1 4
Erläuterung: Die maximale Anzahl, die gebildet werden kann, ist 4 ( 4 & 5 & 6 ) und nur 1 Triplett ist möglich.
Eingabe : a[] = {4, 11, 10, 15, 26}
Ausgabe : 4 10
Erklärung: Die maximale Anzahl, die gebildet werden kann, ist 10. Es sind 4 Tripel möglich – {11, 10, 15}, {11, 10, 26}, {11, 15, 26}, {10, 15, 26}
Ein naiver Ansatz besteht darin, 3 Schleifen zu verwenden und alle Tripletts zu erzeugen und die maximale Anzahl, die gebildet werden kann, und die Anzahl solcher Tripletts zu berechnen.
Zeitkomplexität: O(N^3)
Ein besserer Ansatz besteht darin, die Zahl zuerst in ihrer binären Darstellung darzustellen und sie in einem 2D-Array zu speichern. Da die Zahl nicht größer als 2^32 sein kann (aufgrund der in der Frage angegebenen Einschränkungen), werden für jede Zahl maximal 32 Iterationen benötigt. Wir nehmen auch ein boolesches Flag-Array, das darstellt, welche Zahlen verwendet werden können, um das maximale Triplett zu erstellen. Zunächst setzen wir das Array auf true, da jede Zahl verwendet werden kann.
Die maximale UND-Zahl sei X anfänglich Null.
Jetzt wollen wir X maximieren, also beginnen wir mit dem Durchlaufen der 2D-Tabelle ab dem Index, der das 32. Bit der Zahl darstellt, und wir zählen die Anzahl der Einsen, die am 32. Bit der Zahlen vorhanden sind, die für die Tripletts verfügbar sind, dh deren Flags sind wahr. Wenn die Anzahl der Einsen größer als gleich 3 ist, was bedeutet, dass Tripletts möglich sind, um das i-te Bit von X zu setzen, dann setzen wir das Flag aller Zahlen, deren i-tes Bit nicht gesetzt ist, und addieren auch die Potenz i zur Basis 2 zu X. Sonst, wenn die Zählung kleiner als 3 ist, dann wird i-it von X nicht gesetzt und wir brauchen die Flags der Zahlen nicht zu ändern, da es Kombinationen von 1 und 0 für dieses Bit geben kann.
Wir werden den obigen Vorgang für jedes Bit in umgekehrter Reihenfolge wiederholen, das heißt von 32 bis 0.
Bei der werden wir die Anzahl der Zahlen zählen, deren Flags gesetzt sind, sei das r. Dann müssen wir für die Anzahl der Tripel nur rC3 { r*(r-1)*(r-2)/6 } berechnen.
C++
// CPP program to find triplet with maximum
// bitwise AND.
#include "cmath"
#include "cstring"
#include "iostream"
using namespace std;
int maxTriplet(int a[], int n)
{
// Flag Array initially set to true
// for all numbers
bool f[n];
memset(f, true, sizeof(f));
// 2D array for bit representation
// of all the numbers.
// Initially all bits are set to 0.
int bits[n][33];
memset(bits, 0, sizeof(bits));
for (int i = 0; i < n; ++i) {
int num = a[i];
int j = 32;
// Finding bit representation
// of every number and
// storing it in bits array.
while (num) {
// Checking last bit of the number
if (num & 1) {
bits[i][j] = 1;
}
j--;
// Dividing number by 2.
num >>= 1;
}
}
// maximum And number initially 0.
long long ans = 0;
// Traversing the 2d binary representation.
// 0th index represents 32th bits
// while 32th index represents 0th bit.
for (long long i = 0; i <= 32; ++i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
if (bits[j][i] and f[j]) {
cnt++;
}
}
// If cnt greater than 3 then (32-i)th bits
// of the number will be set.
if (cnt >= 3) {
ans += pow(2LL, 32 - i);
// Setting flags of the numbers
// whose ith bit is not set.
for (int j = 0; j < n; ++j) {
if (!bits[j][i]) {
f[j] = false;
}
}
}
}
// Counting the numbers whose flag are true.
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (f[i]) {
cnt++;
}
}
long long NumberOfTriplets =
(cnt * (cnt - 1) * (cnt - 2)) / 6;
cout << NumberOfTriplets << " " << ans;
}
int main(int argc, char const* argv[])
{
int a[] = { 4, 11, 10, 15, 26 };
int n = sizeof(a) / sizeof(a[0]);
maxTriplet(a, n);
return 0;
}
Java
// Java program to find triplet with maximum
// bitwise AND.
import java.util.Arrays;
class GFG {
static void maxTriplet(int a[], int n)
{
// Flag Array initially set to true
// for all numbers
boolean []f = new boolean[n];
Arrays.fill(f, true);
// 2D array for bit representation
// of all the numbers.
// Initially all bits are set to 0.
int bits[][] = new int[n][33];
for (int i = 0; i < n; ++i)
{
int num = a[i];
int j = 32;
// Finding bit representation
// of every number and
// storing it in bits array.
while (num > 0)
{
// Checking last bit of the number
if (num % 2 == 1)
{
bits[i][j] = 1;
}
j--;
// Dividing number by 2.
num >>= 1;
}
}
// maximum And number initially 0.
long ans = 0;
// Traversing the 2d binary representation.
// 0th index represents 32th bits
// while 32th index represents 0th bit.
for (int i = 0; i <= 32; ++i)
{
int cnt = 0;
for (int j = 0; j < n; ++j)
{
if (bits[j][i] == 1 & f[j])
{
cnt++;
}
}
// If cnt greater than 3 then (32-i)th bits
// of the number will be set.
if (cnt >= 3) {
ans += Math.pow(2, 32 - i);
// Setting flags of the numbers
// whose ith bit is not set.
for (int j = 0; j < n; ++j) {
if (bits[j][i] != 1) {
f[j] = false;
}
}
}
}
// Counting the numbers whose flag are true.
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (f[i]) {
cnt++;
}
}
long NumberOfTriplets = (cnt * (cnt - 1) * (cnt - 2)) / 6;
System.out.print(NumberOfTriplets + " " + ans);
}
// Driver code
public static void main(String[] args) {
int a[] = { 4, 11, 10, 15, 26 };
int n = a.length;
maxTriplet(a, n);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find triplet with # maximum bitwise AND. def maxTriplet(a, n): # Flag Array initially set to true # for all numbers f = [True for i in range(n)] # 2D array for bit representation # of all the numbers. # Initially all bits are set to 0. bits = [[0 for i in range(33)] for i in range(n)] for i in range(n): num = a[i] j = 32 # Finding bit representation # of every number and # storing it in bits array. while (num): # Checking last bit of the number if (num & 1) : bits[i][j] = 1 j -= 1 # Dividing number by 2. num >>= 1 # maximum And number initially 0. ans = 0 # Traversing the 2d binary representation. # 0th index represents 32th bits # while 32th index represents 0th bit. for i in range(33): cnt = 0 for j in range(n): if (bits[j][i] and f[j]): cnt += 1 # If cnt greater than 3 then (32-i)th # bits of the number will be set. if (cnt >= 3): ans += pow(2, 32 - i) # Setting flags of the numbers # whose ith bit is not set. for j in range(n): if (bits[j][i] == False) : f[j] = False # Counting the numbers whose # flag are true. cnt = 0 for i in range(n): if (f[i]): cnt += 1 NumberOfTriplets = (cnt * (cnt - 1) * (cnt - 2)) // 6 print(NumberOfTriplets, ans) # Driver Code a = [ 4, 11, 10, 15, 26] n = len(a) maxTriplet(a, n) # This code is contributed by Mohit Kumar29
C#
// C# program to find triplet with maximum
// bitwise AND.
using System;
class GFG
{
static void maxTriplet(int []a, int n)
{
// Flag Array initially set to true
// for all numbers
Boolean []f = new Boolean[n];
for (int i = 0; i < n; ++i)
f[i] = true;
// 2D array for bit representation
// of all the numbers.
// Initially all bits are set to 0.
int [,]bits = new int[n, 33];
for (int i = 0; i < n; ++i)
{
int num = a[i];
int j = 32;
// Finding bit representation
// of every number and
// storing it in bits array.
while (num > 0)
{
// Checking last bit of the number
if (num % 2 == 1)
{
bits[i, j] = 1;
}
j--;
// Dividing number by 2.
num >>= 1;
}
}
// maximum And number initially 0.
long ans = 0;
int cnt;
// Traversing the 2d binary representation.
// 0th index represents 32th bits
// while 32th index represents 0th bit.
for (int i = 0; i <= 32; ++i)
{
cnt = 0;
for (int j = 0; j < n; ++j)
{
if (bits[j, i] == 1 & f[j])
{
cnt++;
}
}
// If cnt greater than 3 then (32-i)th bits
// of the number will be set.
if (cnt >= 3)
{
ans += (long)Math.Pow(2, 32 - i);
// Setting flags of the numbers
// whose ith bit is not set.
for (int j = 0; j < n; ++j)
{
if (bits[j, i] != 1)
{
f[j] = false;
}
}
}
}
// Counting the numbers whose flag are true.
cnt = 0;
for (int i = 0; i < n; ++i)
{
if (f[i])
{
cnt++;
}
}
long NumberOfTriplets = (cnt * (cnt - 1) *
(cnt - 2)) / 6;
Console.Write(NumberOfTriplets + " " + ans);
}
// Driver code
public static void Main(String[] args)
{
int []a = { 4, 11, 10, 15, 26 };
int n = a.Length;
maxTriplet(a, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find triplet with maximum
// bitwise AND.
function maxTriplet(a,n)
{
// Flag Array initially set to true
// for all numbers
let f = new Array(n);
for(let i=0;i<n;i++)
{
f[i]=true;
}
// 2D array for bit representation
// of all the numbers.
// Initially all bits are set to 0.
let bits = new Array(n);
for(let i=0;i<n;i++)
{
bits[i]=new Array(33);
for(let j=0;j<33;j++)
{
bits[i][j]=0;
}
}
for (let i = 0; i < n; ++i)
{
let num = a[i];
let j = 32;
// Finding bit representation
// of every number and
// storing it in bits array.
while (num > 0)
{
// Checking last bit of the number
if (num % 2 == 1)
{
bits[i][j] = 1;
}
j--;
// Dividing number by 2.
num >>= 1;
}
}
// maximum And number initially 0.
let ans = 0;
// Traversing the 2d binary representation.
// 0th index represents 32th bits
// while 32th index represents 0th bit.
for (let i = 0; i <= 32; ++i)
{
let cnt = 0;
for (let j = 0; j < n; ++j)
{
if (bits[j][i] == 1 & f[j])
{
cnt++;
}
}
// If cnt greater than 3 then (32-i)th bits
// of the number will be set.
if (cnt >= 3) {
ans += Math.pow(2, 32 - i);
// Setting flags of the numbers
// whose ith bit is not set.
for (let j = 0; j < n; ++j) {
if (bits[j][i] != 1) {
f[j] = false;
}
}
}
}
// Counting the numbers whose flag are true.
let cnt = 0;
for (let i = 0; i < n; ++i) {
if (f[i]) {
cnt++;
}
}
let NumberOfTriplets = (cnt * (cnt - 1) * (cnt - 2)) / 6;
document.write(NumberOfTriplets + " " + ans);
}
// Driver code
let a=[4, 11, 10, 15, 26];
let n = a.length;
maxTriplet(a, n);
// This code is contributed by patel2127
</script>
4 10
Zeitkomplexität: O(NlogN)
Da jede Zahl in logN in ihre Binärzahl umgewandelt werden kann.
