Maximum XOR sublist of length K in Linked list - Coding

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}`);

Output

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.

Reffered: https://www.geeksforgeeks.org

DSA

Related
Decode the String of special characters
Determining Word Equivalence between Arrays
Check Contiguous 1s Sequence in Binary Linked List
Count Valid Numbers with Equal Digit Frequencies
Find the length of the longest possible word chain

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12