Counting pairs with prime bitwise AND in a Singly Linked List

By Ann Roberts On Apr 25, 2023

Given a Singly linked list of integers, the task is to count the number of pairs of nodes whose bitwise AND is a prime number.

Examples:

Input: 4 -> 2 -> 3 -> 1 -> 5 -> 6
Output: 3
Explanation: The only pair with bitwise AND being a prime number is (2, 3), (2, 6), (3, 6).

Input: 10 -> 3 -> 5 -> 7 -> 2 -> 15
Output: 11
Explanation: The pairs with bitwise AND being a prime number are (10, 3), (10, 7), (10, 2), (3, 7), (3, 2), (3, 15), (5, 7), (5, 15), (7, 2), (7, 15), (2, 15).

Approach: This can be solved with the following idea:

To solve this problem, we can iterate through the linked list, and for each node, we can iterate over all nodes after it and check if the bitwise AND of their values is a prime number. If yes, we can increment the count. To check if a number is prime or not, we can write a helper function

Below are the steps to implement the above idea:

Define a helper function to check if a given number is prime or not.
Define a variable “count” to keep track of the number of pairs with bitwise AND being a prime number.
Traverse the linked list using two nested loops :
- For each node “curr”, traverse all nodes after it using another loop:
  - If the bitwise AND of the values of “curr” and “next” nodes is a prime number, increment the count.
Return the count.

Below is the code for the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

struct Node {

int val;

Node* next;

Node(int x)

: val(x), next(NULL)

{

}

};

bool isPrime(int n)

{

if (n <= 1)

return false;

for (int i = 2; i <= sqrt(n); i++) {

if (n % i == 0)

return false;

}

return true;

}

int countPairs(Node* head)

{

int count = 0;

Node* curr = head;

while (curr != NULL) {

Node* next = curr->next;

while (next != NULL) {

int and_val = curr->val & next->val;

if (isPrime(and_val))

count++;

next = next->next;

}

curr = curr->next;

}

return count;

}

int main()

{

Node* head1 = new Node(10);

head1->next = new Node(3);

head1->next->next = new Node(5);

head1->next->next->next = new Node(7);

head1->next->next->next->next = new Node(2);

head1->next->next->next->next->next = new Node(15);

cout << countPairs(head1) << endl;

return 0;

}

Time Complexity: O(n^2 * log(max_val))
Auxiliary Space: O(1)

Last Updated :
24 Apr, 2023

Like Article

Save Article

Given a Singly linked list of integers, the task is to count the number of pairs of nodes whose bitwise AND is a prime number.

Examples:

Input: 4 -> 2 -> 3 -> 1 -> 5 -> 6
Output: 3
Explanation: The only pair with bitwise AND being a prime number is (2, 3), (2, 6), (3, 6).

Input: 10 -> 3 -> 5 -> 7 -> 2 -> 15
Output: 11
Explanation: The pairs with bitwise AND being a prime number are (10, 3), (10, 7), (10, 2), (3, 7), (3, 2), (3, 15), (5, 7), (5, 15), (7, 2), (7, 15), (2, 15).

Approach: This can be solved with the following idea:

To solve this problem, we can iterate through the linked list, and for each node, we can iterate over all nodes after it and check if the bitwise AND of their values is a prime number. If yes, we can increment the count. To check if a number is prime or not, we can write a helper function

Below are the steps to implement the above idea:

Define a helper function to check if a given number is prime or not.
Define a variable “count” to keep track of the number of pairs with bitwise AND being a prime number.
Traverse the linked list using two nested loops :
- For each node “curr”, traverse all nodes after it using another loop:
  - If the bitwise AND of the values of “curr” and “next” nodes is a prime number, increment the count.
Return the count.

Below is the code for the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

struct Node {

int val;

Node* next;

Node(int x)

: val(x), next(NULL)

{

}

};

bool isPrime(int n)

{

if (n <= 1)

return false;

for (int i = 2; i <= sqrt(n); i++) {

if (n % i == 0)

return false;

}

return true;

}

int countPairs(Node* head)

{

int count = 0;

Node* curr = head;

while (curr != NULL) {

Node* next = curr->next;

while (next != NULL) {

int and_val = curr->val & next->val;

if (isPrime(and_val))

count++;

next = next->next;

}

curr = curr->next;

}

return count;

}

int main()

{

Node* head1 = new Node(10);

head1->next = new Node(3);

head1->next->next = new Node(5);

head1->next->next->next = new Node(7);

head1->next->next->next->next = new Node(2);

head1->next->next->next->next->next = new Node(15);

cout << countPairs(head1) << endl;

return 0;

}

Time Complexity: O(n^2 * log(max_val))
Auxiliary Space: O(1)

Last Updated :
24 Apr, 2023

Like Article

Save Article

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.