Find the Highest Occurring Digit in a Linked List Nodes
Given a linked list, the task is to find the highest occurring digit in the linked list. Each node in the linked list contains a positive integer value. Analyze the digits present in these values and determine the digit that occurs the most frequently throughout the linked list.
Examples:
Input: 2 -> 11 -> 3 -> 2 -> 1
Output: 1
Explanation: In this example, the linked list is: 2 -> 11 -> 3 -> 2 -> 1. The digit 2 occurs twice, the digit 1 occurs thrice, and the digit 3 also occurs once. The digit 2 occurs in two nodes: the first node (2) and the fourth node (2). The digit 1 occurs in two nodes: the second node contains two times (11) and the fifth node (1). The digit 3 occurs in one node: the third node (3). Among these digits, the digit 1 has the highest occurrence with a count of 3. Therefore, the output is 1.Input: 5 -> 5 -> 3 -> 2 -> 12
Output: 5
Explanation: In this example, the linked list is: 5 -> 5 -> 3 -> 2 -> 12. The digit 5 occurs twice, the digit 3 occurs once, and the digit 2 also occurs twice. The digit 5 occurs in two nodes: the first node (5) and the second node (5). The digit 3 occurs in one node : the third node (3). The digit 2 occurs in two node: the fourth node (2) and in the fifth node (2). Among these digits, the digit 5 and 2 has the highest occurrence with a count of 2 . Therefore, the output is 5 because 5 digit occurs before digit 2.
Approach: To solve the problem follow the below idea:
The intuition behind the approach is to iterate through the linked list and examine each node’s value. By extracting individual digits from the value, we can keep track of their occurrences using an unordered map. The algorithm maintains a count for each digit encountered, updating the count whenever a digit is encountered again. Throughout the traversal, it identifies the digit with the highest count. Finally, it returns the digit that occurs the most frequently in the linked list. This approach efficiently determines the highest occurring digit by analyzing the digits within the linked list nodes and selecting the one with the maximum count.
Below are the steps of the approach:
- Initialize variables: maxCount and digitWithMaxCount.
- Start traversing the linked list from the head.
- For each node, extract its value.
- Count how many times each digit appears in the value.
- Update maxCount and digitWithMaxCount if a digit appears more times.
- Move to the next node and repeat steps 3-5.
- After traversing all nodes, return the digit with the highest count.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Define a structure for // the linked list node struct Node { // Data value of the node int data; // Pointer to the next node // in the list struct Node* next; }; // Function to find the highest occurring // digit in the linked list int highestOccurringDigit(Node* head) { // Initialize a map to store // digit counts unordered_map< int , int > digitCount; // Initialize maximum count int maxCount = 0; // Initialize digit with the // maximum count int digitWithMaxCount = 0; // Start traversing the // linked list Node* current = head; while (current != NULL) { // Get the value stored in // the current node int num = current->data; // Extract individual digits from // the number and count them while (num != 0) { // Extract the last digit int digit = num % 10; // Increment the count of // the current digit digitCount[digit]++; // Update maxCount and // digitWithMaxCount if needed if (digitCount[digit] > maxCount || (digitCount[digit] == maxCount && digit > digitWithMaxCount)) { maxCount = digitCount[digit]; digitWithMaxCount = digit; } // Remove the last digit num /= 10; } // Move to the next node /// in the linked list current = current->next; } // Return the digit with // the highest occurrence return digitWithMaxCount; } // Function to create a new node with // the given data value Node* createNode( int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = NULL; return newNode; } // Drivers code int main() { // Create a linked list with // sample data Node* head = createNode(2); head->next = createNode(11); head->next->next = createNode(3); head->next->next->next = createNode(2); head->next->next->next->next = createNode(1); // Find and print the highest occurring // digit in the linked list int highestDigit = highestOccurringDigit(head); cout << "Highest Occurring Digit: " << highestDigit << endl; return 0; } |
Java
import java.util.HashMap; import java.util.Map; // Define a class for the linked list node class Node { // Data value of the node int data; // Pointer to the next node in the list Node next; Node( int data) { this .data = data; this .next = null ; } } public class Main { // Function to find the highest occurring digit in the linked list static int highestOccurringDigit(Node head) { // Initialize a map to store digit counts Map<Integer, Integer> digitCount = new HashMap<>(); // Initialize maximum count int maxCount = 0 ; // Initialize digit with the maximum count int digitWithMaxCount = 0 ; // Start traversing the linked list Node current = head; while (current != null ) { // Get the value stored in the current node int num = current.data; // Extract individual digits from the number and count them while (num != 0 ) { // Extract the last digit int digit = num % 10 ; // Increment the count of the current digit digitCount.put(digit, digitCount.getOrDefault(digit, 0 ) + 1 ); // Update maxCount and digitWithMaxCount if needed if (digitCount.get(digit) > maxCount || (digitCount.get(digit) == maxCount && digit > digitWithMaxCount)) { maxCount = digitCount.get(digit); digitWithMaxCount = digit; } // Remove the last digit num /= 10 ; } // Move to the next node in the linked list current = current.next; } // Return the digit with the highest occurrence return digitWithMaxCount; } // Function to create a new node with the given data value static Node createNode( int data) { return new Node(data); } public static void main(String[] args) { // Create a linked list with sample data Node head = createNode( 2 ); head.next = createNode( 11 ); head.next.next = createNode( 3 ); head.next.next.next = createNode( 2 ); head.next.next.next.next = createNode( 1 ); // Find and print the highest occurring digit in the linked list int highestDigit = highestOccurringDigit(head); System.out.println( "Highest Occurring Digit: " + highestDigit); } } // This code is contributed by Vikram_Shirsat |
Python3
# Python code for the above approach # Define a class for the linked list node class Node: # Constructor to initialize the node def __init__( self , data): self .data = data self . next = None # Function to find the highest occurring # digit in the linked list def highest_occuring_digit(head): # Initialize a dictionary to store digit counts digit_count = {} # Initialize maximum count max_count = 0 # Initialize digit with the maximum count digit_with_max_count = 0 # Start traversing the linked list current = head while current is not None : # Get the value stored in the current node num = current.data # Extract individual digits from the number and count them while num ! = 0 : # Extract the last digit digit = num % 10 # Increment the count of the current digit digit_count[digit] = digit_count.get(digit, 0 ) + 1 # Update max_count and digit_with_max_count if needed if digit_count[digit] > max_count or (digit_count[digit] = = max_count and digit > digit_with_max_count): max_count = digit_count[digit] digit_with_max_count = digit # Remove the last digit num / / = 10 # Move to the next node in the linked list current = current. next # Return the digit with the highest occurrence return digit_with_max_count # Function to create a new node with the given data value def create_node(data): return Node(data) # Driver code if __name__ = = "__main__" : # Create a linked list with sample data head = create_node( 2 ) head. next = create_node( 11 ) head. next . next = create_node( 3 ) head. next . next . next = create_node( 2 ) head. next . next . next . next = create_node( 1 ) # Find and print the highest occurring digit in the linked list highest_digit = highest_occuring_digit(head) print (f "Highest Occurring Digit: {highest_digit}" ) |
C#
// C# Code using System; using System.Collections.Generic; // Define a class for the linked list node class Node { // Data value of the node public int Data { get ; set ; } // Pointer to the next node in the list public Node Next { get ; set ; } public Node( int data) { Data = data; Next = null ; } } public class MainClass { // Function to find the highest occurring digit in the linked list static int HighestOccurringDigit(Node head) { // Initialize a dictionary to store digit counts Dictionary< int , int > digitCount = new Dictionary< int , int >(); // Initialize maximum count int maxCount = 0; // Initialize digit with the maximum count int digitWithMaxCount = 0; // Start traversing the linked list Node current = head; while (current != null ) { // Get the value stored in the current node int num = current.Data; // Extract individual digits from the number and count them while (num != 0) { // Extract the last digit int digit = num % 10; // Increment the count of the current digit digitCount[digit] = digitCount.TryGetValue(digit, out int count) ? count + 1 : 1; // Update maxCount and digitWithMaxCount if needed if (digitCount[digit] > maxCount || (digitCount[digit] == maxCount && digit > digitWithMaxCount)) { maxCount = digitCount[digit]; digitWithMaxCount = digit; } // Remove the last digit num /= 10; } // Move to the next node in the linked list current = current.Next; } // Return the digit with the highest occurrence return digitWithMaxCount; } // Function to create a new node with the given data value static Node CreateNode( int data) { return new Node(data); } public static void Main( string [] args) { // Create a linked list with sample data Node head = CreateNode(2); head.Next = CreateNode(11); head.Next.Next = CreateNode(3); head.Next.Next.Next = CreateNode(2); head.Next.Next.Next.Next = CreateNode(1); // Find and print the highest occurring digit in the linked list int highestDigit = HighestOccurringDigit(head); Console.WriteLine( "Highest Occurring Digit: " + highestDigit); } } // This code is contributed by guptapratik |
Javascript
// Define a class for the linked list node class Node { constructor(data) { this .data = data; // Data value of the node this .next = null ; // Pointer to the next node in the list } } // Function to find the highest occurring digit in the linked list function highestOccurringDigit(head) { // Initialize a map to store digit counts const digitCount = new Map(); // Initialize maximum count let maxCount = 0; // Initialize digit with the maximum count let digitWithMaxCount = 0; // Start traversing the linked list let current = head; while (current !== null ) { // Get the value stored in the current node let num = current.data; // Extract individual digits from the number and count them while (num !== 0) { // Extract the last digit const digit = num % 10; // Increment the count of the current digit digitCount.set(digit, (digitCount.get(digit) || 0) + 1); // Update maxCount and digitWithMaxCount if needed if (digitCount.get(digit) > maxCount || (digitCount.get(digit) === maxCount && digit > digitWithMaxCount)) { maxCount = digitCount.get(digit); digitWithMaxCount = digit; } // Remove the last digit num = Math.floor(num / 10); } // Move to the next node in the linked list current = current.next; } // Return the digit with the highest occurrence return digitWithMaxCount; } // Function to create a new node with the given data value function createNode(data) { return new Node(data); } // Create a linked list with sample data const head = createNode(2); head.next = createNode(11); head.next.next = createNode(3); head.next.next.next = createNode(2); head.next.next.next.next = createNode(1); // Find and print the highest occurring digit in the linked list const highestDigit = highestOccurringDigit(head); console.log( "Highest Occurring Digit: " + highestDigit); |
Highest Occurring Digit: 1
Time Complexity: O(N), where N is the number of nodes in the linked list.
Axillary Space: O(1) (constant) because the maximum number of entries in the unordered map remains constant regardless of the size of the linked list.