Given a singly linked list, the task is to Count the pairs of nodes with greater Bitwise AND than Bitwise XOR.
Examples:
Input: list: 1->4->2->6->3
Output: 2
Explanation: 1st List Node Pair: (4, 6 ), Bitwise AND = 4, Bitwise XOR = 2
2nd List Node Pair: (2, 3), Bitwise AND = 2, Bitwise XOR = 1Input: list: 17->34->62->46->30->51
Output: 7
Explanation: Valid List Node Pairs are (17, 30 ), (34, 62), (34, 46), (34, 51), (62, 46), (62, 51), (46, 51).
Naive Approach: The naive approach is to iterate the linked list and for each node find all other possible nodes forming a pair such that the bitwise AND is greater than bitwise XOR.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include<bits/stdc++.h>using namespace std;// Structure of node of singly linked liststruct Node { int data; Node *next; Node(int x) { data = x; }};Node *head;// Inserting new node at the beginning of the linked listvoid push(int new_data){ // Create a new node with the given data. Node *new_node = new Node(new_data); // Make the new node point to the head. if (head == NULL) { head = new_node; return; } new_node->next = head; // Make the new node as the head node. head = new_node;}// Function to find the count of all possible pairsstatic int PerfectPair(){ int ans = 0; while (head != NULL) { Node *temp = head->next; while (temp != NULL) { if ((head->data & temp->data) > (head->data ^ temp->data)) { ans++; } temp = temp->next; } head = head->next; } return ans;}// Driver codeint main(){ // Create an empty singly linked list head = NULL; // Insert values in Linked List push(51); push(30); push(46); push(62); push(34); push(17); // Call PerfectPair function cout << PerfectPair();}// This code is contributed by ajaymakvana. |
Java
// Java program for above approachimport java.util.ArrayList;import java.util.HashMap;public class GFG { // Structure of node of singly linked list static class Node { int data; Node next; Node(int x) { data = x; } }; // Inserting new node // at the beginning of the linked list static void push(int new_data) { // Create a new node with the given data. Node new_node = new Node(new_data); // Make the new node point to the head. if (head == null) { head = new_node; return; } new_node.next = head; // Make the new node as the head node. head = new_node; } static Node head; // Function to find the // count of all possible pairs static int PerfectPair() { int ans = 0; while(head!=null){ Node temp = head.next; while(temp!=null){ if((head.data & temp.data) > (head.data ^ temp.data)){ ans++; } temp = temp.next; } head = head.next; } return ans; } // Driver code public static void main(String[] args) { // Create an empty singly linked list head = null; // Insert values in Linked List push(51); push(30); push(46); push(62); push(34); push(17); // Call PerfectPair function System.out.println(PerfectPair()); }} |
Python3
# Python program for above approach# Structure of node of singly linked listclass Node: def __init__(self, data): self.data = data self.next = Noneclass LinkedList: def __init__(self): self.head = None # Inserting new node # at the beginning of the linked list def push(self, new_data): # Create a new node with the given data. new_node = Node(new_data) # Make the new node point to the head. if self.head == None: self.head = new_node return new_node.next = self.head self.head = new_node # Function to find the # count of all possible pairs def PerfectPair(self): ans = 0 current = self.head while current: temp = current.next while temp: if (current.data & temp.data) > (current.data ^ temp.data): ans += 1 temp = temp.next current = current.next return ans# Driver codeif __name__ == "__main__": llist = LinkedList() # Insert values in Linked List llist.push(51) llist.push(30) llist.push(46) llist.push(62) llist.push(34) llist.push(17) print(llist.PerfectPair()) # This code is contributed by divya_p123. |
C#
// C# program for above approachusing System;public class GFG { // Structure of node of singly linked list class Node { public int data; public Node next; public Node(int x) { data = x; } } // Inserting new node // at the beginning of the linked list static void push(int new_data) { // Create a new node with the given data. Node new_node = new Node(new_data); // Make the new node point to the head. if (head == null) { head = new_node; return; } new_node.next = head; // Make the new node as the head node. head = new_node; } static Node head; // Function to find the // count of all possible pairs static int PerfectPair() { int ans = 0; while (head != null) { Node temp = head.next; while (temp != null) { if ((head.data & temp.data) > (head.data ^ temp.data)) { ans++; } temp = temp.next; } head = head.next; } return ans; } static public void Main() { // Create an empty singly linked list head = null; // Insert values in Linked List push(51); push(30); push(46); push(62); push(34); push(17); // Call PerfectPair function Console.WriteLine(PerfectPair()); }}// This code is contributed by lokeshmvs21. |
Javascript
<script>// Structure of node of singly linked listclass Node { constructor(data) { this.data = data; this.next = null; }}let head;// Inserting new node at the beginning of the linked listfunction push(newData) { // Create a new node with the given data. let newNode = new Node(newData); // Make the new node point to the head. if (head === null) { head = newNode; return; } newNode.next = head; // Make the new node as the head node. head = newNode;}// Function to find the count of all possible pairsfunction PerfectPair() { let ans = 0; while (head !== null) { let temp = head.next; while (temp !== null) { if ((head.data & temp.data) > (head.data ^ temp.data)) { ans++; } temp = temp.next; } head = head.next; } return ans;}// Create an empty singly linked listhead = null;// Insert values in Linked Listpush(51);push(30);push(46);push(62);push(34);push(17);// Call PerfectPair functionconsole.log(PerfectPair());</script> |
Output
7
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The problem can be solved efficiently by using the below observation:
If First Set bit (Most significant bit) of two number is at same position, then the Bitwise AND or that numbers is always greater than the XOR because the XOR of two 1 is 0 and AND of two 1s is 1.
For any other cases, XOR will be always greater than the AND
Follow the below steps to solve the problem:
- Traverse the linked list and Store the MSB position for each Node value in an array.
- Initialize a variable ans to store the total possible pairs.
- Create a hash map to store the count of nodes that have the same value of MSB (Most significant bit).
- Traverse the array containing the MSB position and in each iteration:
- Get the count of nodes that have the same position of MSB.
- Add the count of possible pairs from these nodes into ans.
- Return the answer variable.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Structure of node of singly linked liststruct Node { int data; Node* next; Node(int x) { data = x; next = NULL; }};// Inserting new node// at the beginning of the linked listvoid push(struct Node** head_ref, int new_data){ // Create a new node with the given data. struct Node* new_node = new Node(new_data); // Make the new node point to the head. new_node->next = (*head_ref); // Make the new node as the head node. (*head_ref) = new_node;}// Function to find the// count of all possible pairsint PerfectPair(Node* head){ int ans = 0, size = 0; unordered_map<int, int> mp; vector<int> firstSetBit; // Iterate Linked List and store the // firstSetBit position // for each Node Data while (head != NULL) { firstSetBit.push_back( log2(head->data)); size++; head = head->next; } // Check all previous node // which can make // pair with current node for (int i = 0; i < size; i++) { ans += mp[firstSetBit[i]]; mp[firstSetBit[i]]++; } return ans;}// Driver codeint main(){ // Create an empty singly linked list struct Node* head = NULL; // Insert values in Linked List push(&head, 51); push(&head, 30); push(&head, 46); push(&head, 62); push(&head, 34); push(&head, 17); // Call PerfectPair function cout << PerfectPair(head); return 0;} |
Java
// Java program for above approachimport java.util.ArrayList;import java.util.HashMap;public class GFG { // Structure of node of singly linked list static class Node { int data; Node next; Node(int x) { data = x; } }; // Inserting new node // at the beginning of the linked list static void push(int new_data) { // Create a new node with the given data. Node new_node = new Node(new_data); // Make the new node point to the head. if (head == null) { head = new_node; return; } new_node.next = head; // Make the new node as the head node. head = new_node; } static Node head; // Function to find the // count of all possible pairs static int PerfectPair() { int ans = 0, size = 0; HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); ArrayList<Integer> firstSetBit = new ArrayList<Integer>(); // Iterate Linked List and store the // firstSetBit position // for each Node Data while (head != null) { firstSetBit.add(log2(head.data)); size++; head = head.next; } // Check all previous node // which can make // pair with current node for (int i = 0; i < size; i++) { int val = mp.getOrDefault(firstSetBit.get(i), 0); ans += val; mp.put(firstSetBit.get(i), val + 1); } return ans; } // Function to calculate the // log base 2 of an integer public static int log2(int N) { // calculate log2 N indirectly // using log() method int result = (int)(Math.log(N) / Math.log(2)); return result; } // Driver code public static void main(String[] args) { // Create an empty singly linked list head = null; // Insert values in Linked List push(51); push(30); push(46); push(62); push(34); push(17); // Call PerfectPair function System.out.println(PerfectPair()); }}// This code is contributed by jainlovely450 |
Python3
# Python program for above approachimport mathclass GFG: # Structure of node of singly linked list class Node: data = 0 next = None def __init__(self, x): self.data = x # Inserting new node # at the beginning of the linked list @staticmethod def push(new_data): # Create a new node with the given data. new_node = GFG.Node(new_data) # Make the new node point to the head. if (GFG.head == None): GFG.head = new_node return new_node.next = GFG.head # Make the new node as the head node. GFG.head = new_node head = None # Function to find the # count of all possible pairs @staticmethod def PerfectPair(K): ans = 0 size = 0 mp = dict() firstSetBit = [] # Iterate Linked List and store the # firstSetBit position # for each Node Data while (GFG.head != None): firstSetBit.append(GFG.log2(GFG.head.data)) size += 1 GFG.head = GFG.head.next # Check all previous node # which can make # pair with current node i = 0 while (i < size): try: val = mp[firstSetBit[i]] except: val = 0 ans += val mp[firstSetBit[i]] = val + 1 i += 1 return ans # Function to calculate the # log base 2 of an integer @staticmethod def log2(N): # calculate log2 N indirectly # using log() method result = int((math.log(N) / math.log(2))) return result # Driver code @staticmethod def main(args): K = 4 # Create an empty singly linked list GFG.head = None # Insert values in Linked List GFG.push(51) GFG.push(30) GFG.push(46) GFG.push(62) GFG.push(34) GFG.push(17) # Call PerfectPair function print(GFG.PerfectPair(K))if __name__ == "__main__": GFG.main([]) '''This Code is written by Rajat Kumar''' |
C#
// C# program for above approachusing System;using System.Collections.Generic;using System.Collections;static class GFG{ public class Node { public int data; public Node next; public Node(int x) { data = x; } }; // Structure of node of singly linked list // Inserting new node // at the beginning of the linked list static void push(int new_data) { // Create a new node with the given data. Node new_node = new Node(new_data); // Make the new node point to the head. if (head == null) { head = new_node; return; } new_node.next = head; // Make the new node as the head node. head = new_node; } static Node head; // Function to find the // count of all possible pairs static int PerfectPair() { int ans = 0, size = 0; Dictionary<int, int> mp = new Dictionary<int, int>(); ArrayList firstSetBit = new ArrayList(); // Iterate Linked List and store the // firstSetBit position // for each Node Data while (head != null) { firstSetBit.Add(log2(head.data)); size++; head = head.next; } // Check all previous node // which can make // pair with current node for (int i = 0; i < size; i++) { int val = mp.GetValueOrDefault((int)firstSetBit[i], 0); ans += val; mp[(int)firstSetBit[i]] = val + 1; } return ans; } // Function to calculate the // log base 2 of an integer public static int log2(int N) { // calculate log2 N indirectly // using log() method int result = (int)(Math.Log(N) / Math.Log(2)); return result; } // Driver code public static void Main() { // Create an empty singly linked list head = null; // Insert values in Linked List push(51); push(30); push(46); push(62); push(34); push(17); // Call PerfectPair function Console.Write(PerfectPair()); }}// This code is contributed by Saurabh Jaiswal |
Javascript
// Class for node of singly linked listclass Node { constructor(data) { // Store the data of node this.data = data; // Point to the next node in the linked list this.next = null; }}// Class for the GFG programclass GFG { // static variable to store the head node of linked list static head = null; // Function to insert new node at the beginning of linked list static push(newData) { // Create a new node with the given let newNode = new Node(newData); // If linked list is empty, make the new node as head if (!GFG.head) { GFG.head = newNode; return; } // Make the new node point to the current head newNode.next = GFG.head; GFG.head = newNode; } static log2(N) { return Math.floor(Math.log2(N)); }// Function to find the count of all possible pairsstatic PerfectPair(K) { let ans = 0; let size = 0; const mp = {}; const firstSetBit = []; // Iterate linked list and store the first set bit position for each node data let currentNode = GFG.head; while (currentNode) { firstSetBit.push(GFG.log2(currentNode.data)); size++; currentNode = currentNode.next; } // Check all previous node which can make pair with current node for (let i = 0; i < size; i++) { const val = mp[firstSetBit[i]] || 0; ans += val; mp[firstSetBit[i]] = val + 1; } return ans;}// Main function to run the programstatic main() { const K = 4; // Insert values in linked list GFG.push(51); GFG.push(30); GFG.push(46); GFG.push(62); GFG.push(34); GFG.push(17); // Call PerfectPair function console.log(GFG.PerfectPair(K));}}// Call the main functionGFG.main(); |
Output
7
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
