Maximum XOR sublist of length K in Linked list
Given a linked list of integers and an integer value K, the task is to find the maximum XOR value of a sublist of length K in the linked list.
Examples:
Input: 4 -> 6 -> 9 -> 7, K = 2
Output: 15
Explanation: All possible sublists of length K = 2 starting from each node.
4 -> 6, 6 -> 9, 9 -> 7
The XOR value of each sublist is:
4 -> 6: XOR(4, 6) = 2
6 -> 9: XOR(6, 9) = 15
9 -> 7: XOR(9, 7) = 14
Therefore, the maximum XOR value of any sublist of length 2 in the given linked list is 15, which is the XOR value of sublist 6 -> 9.Input: 1 -> 2 -> 3 -> 4 -> 5, K = 3
Output: 5
Explanation: All possible sublists of length K = 3 starting from each node.
1 -> 2 -> 3, 2 -> 3 -> 4, 3 -> 4 -> 5
The XOR value of each sublist is:
1 -> 2 -> 3: XOR(1, 2, 3) = 0
2 -> 3 -> 4: XOR(2, 3, 4) = 5
3 -> 4 -> 5: XOR(3, 4, 5) = 2
Therefore, the maximum XOR value of any sublist of length 3 in the given linked list is 5, which is the XOR value of sublist 2 -> 3 -> 4.
Approach: To solve the problem follow the below Intuition:
The intuition behind the approach is to iterate through each possible sublist of size K and compute its XOR value. We will maintain a variable max_xor to store the maximum XOR value found so far. The final answer will be the max_xor value after all the sublists have been considered.
Here are the step-by-step approach:
- Initialize a variable max_xor to 0.
- Iterate through each node of the linked list. This will be the starting point of the sublist.
- Initialize a variable curr_xor to 0 and a variable count to 0.
- Iterate through the next K nodes of the linked list or until the end of the list, whichever comes first. For each node encountered during this iteration, XOR its value with curr_xor and increment count.
- If count is equal to K, then a valid sublist has been found. Check if curr_xor is greater than max_xor. If so, update max_xor to curr_xor.
- Continue the outer iteration from the next node of the linked list.
- After all nodes have been considered, return max_xor.
Below is the implementation of the above approach:
C++
// C++ code for the above aprpoach: #include <bits/stdc++.h> using namespace std; // A linked list node class Node { public : int data; Node* next; Node( int data) { this ->data = data; next = nullptr; } }; // Function to find the maximum XOR value of // a sublist of length K in a linked list int max_xor_sublist(Node* head, int K) { int max_xor = 0; Node* curr = head; // Traverse the linked list while (curr != nullptr) { int curr_xor = 0; int count = 0; Node* temp = curr; // Calculate XOR of the next K nodes // (or less if the list ends) while (count < K && temp != nullptr) { curr_xor ^= temp->data; temp = temp->next; count++; } // Update max_xor if the current XOR is // greater and the sublist has // exactly K elements if (count == K && curr_xor > max_xor) { max_xor = curr_xor; } curr = curr->next; } return max_xor; } // Drivers code int main() { // Create a linked list and // initialize it with values Node* head = new Node(4); head->next = new Node(6); head->next->next = new Node(9); head->next->next->next = new Node(7); int K = 2; // Find and print the maximum XOR value // of a sublist of length K int result = max_xor_sublist(head, K); cout << "Maximum XOR value of a sublist of length " << K << " is: " << result << endl; // Create another linked list and // initialize it with values Node* head2 = new Node(1); head2->next = new Node(2); head2->next->next = new Node(3); head2->next->next->next = new Node(4); head2->next->next->next->next = new Node(5); K = 3; // Find and print the maximum XOR value // of a sublist of length K result = max_xor_sublist(head2, K); cout << "Maximum XOR value of a sublist of length " << K << " is: " << result << endl; } |
Java
// Java code for the above aprpoach: // A linked list node class Node { public int data; public Node next; public Node( int data) { this .data = data; this .next = null ; } } public class Main { // Function to find the maximum XOR value of // a sublist of length K in a linked list public static int max_xor_sublist(Node head, int K) { int max_xor = 0 ; Node curr = head; // Traverse the linked list while (curr != null ) { int curr_xor = 0 ; int count = 0 ; Node temp = curr; // Calculate XOR of the next K nodes // (or less if the list ends) while (count < K && temp != null ) { curr_xor ^= temp.data; temp = temp.next; count++; } // Update max_xor if the current XOR is // greater and the sublist has // exactly K elements if (count == K && curr_xor > max_xor) { max_xor = curr_xor; } curr = curr.next; } return max_xor; } // Driver code public static void main(String[] args) { // Create a linked list and // initialize it with values Node head = new Node( 4 ); head.next = new Node( 6 ); head.next.next = new Node( 9 ); head.next.next.next = new Node( 7 ); int K = 2 ; // Find and print the maximum XOR value // of a sublist of length K int result = max_xor_sublist(head, K); System.out.println( "Maximum XOR value of a sublist of length " + K + " is: " + result); // Create another linked list and // initialize it with values Node head2 = new Node( 1 ); head2.next = new Node( 2 ); head2.next.next = new Node( 3 ); head2.next.next.next = new Node( 4 ); head2.next.next.next.next = new Node( 5 ); K = 3 ; // Find and print the maximum XOR value // of a sublist of length K result = max_xor_sublist(head2, K); System.out.println( "Maximum XOR value of a sublist of length " + K + " is: " + result); } } |
Python3
# python implementation # A linked list node class Node: def __init__( self , data): self .data = data self . next = None # Function to find the maximum XOR value of # a sublist of length K in a linked list def max_xor_sublist(head, K): max_xor = 0 curr = head # Traverse the linked list while curr ! = None : curr_xor = 0 count = 0 temp = curr # Calculate XOR of the next K nodes # (or less if the list ends) while count < K and temp ! = None : curr_xor ^ = temp.data temp = temp. next count + = 1 # Update max_xor if the current XOR is # greater and the sublist has # exactly K elements if count = = K and curr_xor > max_xor: max_xor = curr_xor curr = curr. next return max_xor # Driver code if __name__ = = "__main__" : # Create a linked list and # initialize it with values head = Node( 4 ) head. next = Node( 6 ) head. next . next = Node( 9 ) head. next . next . next = Node( 7 ) K = 2 # Find and print the maximum XOR value # of a sublist of length K result = max_xor_sublist(head, K) print ( "Maximum XOR value of a sublist of length" , K, "is:" , result) # Create another linked list and # initialize it with values head2 = Node( 1 ) head2. next = Node( 2 ) head2. next . next = Node( 3 ) head2. next . next . next = Node( 4 ) head2. next . next . next . next = Node( 5 ) K = 3 # Find and print the maximum XOR value # of a sublist of length K result = max_xor_sublist(head2, K) print ( "Maximum XOR value of a sublist of length" , K, "is:" , result) # This code is contributed by Sakshi |
C#
// C# code for the above aprpoach using System; // A linked list node public class Node { public int data; public Node next; public Node( int data) { this .data = data; next = null ; } } public class GFG { // Function to find the maximum XOR value of // a sublist of length K in a linked list public static int MaxXORSublist(Node head, int K) { int max_xor = 0; Node curr = head; // Traverse the linked list while (curr != null ) { int curr_xor = 0; int count = 0; Node temp = curr; // Calculate XOR of the next K nodes // (or less if the list ends) while (count < K && temp != null ) { curr_xor ^= temp.data; temp = temp.next; count++; } // Update max_xor if the current XOR is // greater and the sublist has // exactly K elements if (count == K && curr_xor > max_xor) { max_xor = curr_xor; } curr = curr.next; } return max_xor; } // Drivers code public static void Main( string [] args) { // Create a linked list and // initialize it with values Node head = new Node(4); head.next = new Node(6); head.next.next = new Node(9); head.next.next.next = new Node(7); int K = 2; // Find and print the maximum XOR value // of a sublist of length K int result = MaxXORSublist(head, K); Console.WriteLine( "Maximum XOR value of a sublist of length " + K + " is: " + result); // Create another linked list and // initialize it with values Node head2 = new Node(1); head2.next = new Node(2); head2.next.next = new Node(3); head2.next.next.next = new Node(4); head2.next.next.next.next = new Node(5); K = 3; // Find and print the maximum XOR value // of a sublist of length K result = MaxXORSublist(head2, K); Console.WriteLine( "Maximum XOR value of a sublist of length " + K + " is: " + result); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code for the above aprpoach: // A linked list node class Node { constructor(data) { this .data = data; this .next = null ; } } // Function to find the maximum XOR value of // a sublist of length K in a linked list function maxXorSublist(head, K) { let max_xor = 0; let curr = head; // Traverse the linked list while (curr !== null ) { let curr_xor = 0; let count = 0; let temp = curr; // Calculate XOR of the next K nodes // (or less if the list ends) while (count < K && temp !== null ) { curr_xor ^= temp.data; temp = temp.next; count++; } // Update max_xor if the current XOR is // greater and the sublist has // exactly K elements if (count === K && curr_xor > max_xor) { max_xor = curr_xor; } curr = curr.next; } return max_xor; } // Create a linked list and // initialize it with values let head = new Node(4); head.next = new Node(6); head.next.next = new Node(9); head.next.next.next = new Node(7); let K = 2; // Find and print the maximum XOR value // of a sublist of length K let result = maxXorSublist(head, K); console.log(`Maximum XOR value of a sublist of length ${K} is: ${result}`); // Create another linked list and // initialize it with values let head2 = new Node(1); head2.next = new Node(2); head2.next.next = new Node(3); head2.next.next.next = new Node(4); head2.next.next.next.next = new Node(5); K = 3; // Find and print the maximum XOR value // of a sublist of length K result = maxXorSublist(head2, K); console.log(`Maximum XOR value of a sublist of length ${K} is: ${result}`); |
Maximum XOR value of a sublist of length 2 is: 15 Maximum XOR value of a sublist of length 3 is: 5
Time Complexity: O(n*K), where n is the number of nodes in the linked list and K is the length of the sublists being considered.
Auxiliary Space: O(1) because we are only using a constant amount of extra space.