Maximum and Minimum element of a linked list which is divisible by a given number k

0 1 8 minutes read

Given a singly linked list of $N$ nodes. Find the smallest and largest elements in linked list divisible by a given number $K$ .

Examples:

Input : List = 15 -> 14 -> 13 -> 22 -> 50 , K = 5
Output :
Maximum element in linked list divisible by K: 50
Minimum element in linked list divisible by K: 5

Input : List = 10 -> 14 -> 13 -> 22 -> 100 , K = 10
Output :
Maximum element in linked list divisible by K: 100
Minimum element in linked list divisible by K: 10

Approach:

The idea is to traverse the linked list to the end and initialize the max and min variable to INT_MIN and INT_MAX respectively.
After that check a condition that if the max value is less than the current node’s value and divisible by K then current node’s value is assigned to max.
Similarly, check if the current node’s value is less than min value and divisible by k then the current node’s value is assigned to min. Repeat above two steps until the end of the list is reached.

Below is the implementation of the above approach:

C++

// Program to find the smallest and largest
// elements divisible by a given number k 
// in singly linked list
 
#include <bits/stdc++.h>
 
using namespace std;
 
/* Linked list node */
struct Node {
    int data;
    struct Node* next;
};
 
// Function to print max and min elements of
// linked list divisible by K
void findMaxMin(struct Node* head, int k)
{
    // Declare a min variable and initialize
    // it with INT_MAX value.
    // INT_MAX is integer type and its value
    // is 32767 or greater.
    int min = INT_MAX;
 
    // Declare a max variable and initialize
    // it with INT_MIN value.
    // INT_MIN is integer type and its value
    // is -32767 or less.
    int max = INT_MIN;
 
    // Check loop while head not equal to NULL
    while (head != NULL) {
 
        // If head->data is less than min and divisible
        // by k then assign value of head->data to min
        // otherwise node point to next node.
        if ((head->data < min) && (head->data % k == 0))
            min = head->data;
 
        // If head->data is greater than max and divisible
        // by k then assign value of head->data to max
        // otherwise node point to next node.
        if ((head->data > max) && (head->data % k == 0))
            max = head->data;
 
        head = head->next;
    }
 
    // Print max element
    cout << "Max Element : " << max << endl;
 
    // print min element
    cout << "Min Element : " << min;
}
 
// Function that pushes the element in the linked list.
void push(struct Node** head, int data)
{
    // Allocate dynamic memory for newNode.
    struct Node* newNode = new Node();
 
    // Assign the data into newNode.
    newNode->data = data;
 
    // newNode->next assign the address of
    // head node.
    newNode->next = (*head);
 
    // newNode become the headNode.
    (*head) = newNode;
}
 
// Driver Code
int main()
{
    // Start with empty list
    struct Node* head = NULL;
 
    // Using push() function to construct
    // singly linked list
    // 50->5->13->14->15
    push(&head, 15);
    push(&head, 14);
    push(&head, 13);
    push(&head, 5);
    push(&head, 50);
 
    int k = 5;
 
    findMaxMin(head, k);
 
    return 0;
}

Java

// Java program to find the smallest and largest 
// elements divisible by a given number k 
// in singly linked list 
class GFG
{
     
// Linked list node /
static class Node
{ 
    int data; 
    Node next; 
}; 
 
// Function to print max and min elements of 
// linked list divisible by K 
static void findMaxMin( Node head, int k) 
{ 
    // Declare a min variable and initialize 
    // it with INT_MAX value. 
    // INT_MAX is integer type and its value 
    // is 32767 or greater. 
    int min = Integer.MAX_VALUE; 
 
    // Declare a max variable and initialize 
    // it with INT_MIN value. 
    // INT_MIN is integer type and its value 
    // is -32767 or less. 
    int max = Integer.MIN_VALUE; 
 
    // Check loop while head not equal to null 
    while (head != null) 
    { 
 
        // If head.data is less than min and divisible 
        // by k then assign value of head.data to min 
        // otherwise node point to next node. 
        if ((head.data < min) && (head.data % k == 0)) 
            min = head.data; 
 
        // If head.data is greater than max and divisible 
        // by k then assign value of head.data to max 
        // otherwise node point to next node. 
        if ((head.data > max) && (head.data % k == 0)) 
            max = head.data; 
 
        head = head.next; 
    } 
 
    // Print max element 
    System.out.println( "Max Element : " + max); 
 
    // print min element 
    System.out.println( "Min Element : " + min); 
} 
 
// Function that push the element in linked list. 
static Node push( Node head, int data) 
{ 
    // Allocate dynamic memory for newNode. 
    Node newNode = new Node(); 
 
    // Assign the data into newNode. 
    newNode.data = data; 
 
    // newNode.next assign the address of 
    // head node. 
    newNode.next = (head); 
 
    // newNode become the headNode. 
    (head) = newNode; 
    return head;
} 
 
// Driver Code 
public static void main(String args[]) 
{ 
    // Start with empty list 
    Node head = null; 
 
    // Using push() function to construct  
    // singly linked list 
    // 50.5.13.14.15 
    head = push(head, 15); 
    head = push(head, 14); 
    head = push(head, 13); 
    head = push(head, 5); 
    head = push(head, 50); 
 
    int k = 5; 
 
    findMaxMin(head, k); 
}
} 
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to find the smallest and largest 
# elements divisible by a given number k 
# in singly linked list 
 
# Linked list node /
class Node:
    def __init__(self):
        self.data = 0
        self.next = None
 
# Function to print max and min elements of 
# linked list divisible by K 
def findMaxMin(head, k): 
 
    # Declare a min variable and initialize 
    # it with INT_MAX value. 
    # INT_MAX is integer type and its value 
    # is 32767 or greater. 
    min = 32767
 
    # Declare a max variable and initialize 
    # it with INT_MIN value. 
    # INT_MIN is integer type and its value 
    # is -32767 or less. 
    max = -32767
 
    # Check loop while head not equal to None 
    while (head != None) :
     
        # If head.data is less than min and divisible 
        # by k then assign value of head.data to min 
        # otherwise node point to next node. 
        if ((head.data < min) and (head.data % k == 0)) :
            min = head.data 
 
        # If head.data is greater than max and divisible 
        # by k then assign value of head.data to max 
        # otherwise node point to next node. 
        if ((head.data > max) and (head.data % k == 0)) :
            max = head.data 
 
        head = head.next
     
    # Print max element 
    print( "Max Element : " , max) 
 
    # print min element 
    print( "Min Element : " , min) 
 
# Function that push the element in linked list. 
def push( head, data): 
 
    # Allocate dynamic memory for newNode. 
    newNode = Node() 
 
    # Assign the data into newNode. 
    newNode.data = data 
 
    # newNode.next assign the address of 
    # head node. 
    newNode.next = (head) 
 
    # newNode become the headNode. 
    (head) = newNode 
    return head
 
# Driver Code 
 
# Start with empty list 
head = None
 
# Using push() function to construct 
# singly linked list 
# 50.5.13.14.15 
head = push(head, 15) 
head = push(head, 14) 
head = push(head, 13) 
head = push(head, 5) 
head = push(head, 50) 
 
k = 5
 
findMaxMin(head, k) 
 
# This code is contributed by Arnab Kundu

C#

// C# program to find the smallest and largest 
// elements divisible by a given number k 
// in singly linked list 
using System;
 
class GFG 
{ 
     
// Linked list node / 
public class Node 
{ 
    public int data; 
    public Node next; 
}; 
 
// Function to print max and min elements of 
// linked list divisible by K 
static void findMaxMin( Node head, int k) 
{ 
    // Declare a min variable and initialize 
    // it with INT_MAX value. 
    // INT_MAX is integer type and its value 
    // is 32767 or greater. 
    int min = int.MaxValue; 
 
    // Declare a max variable and initialize 
    // it with INT_MIN value. 
    // INT_MIN is integer type and its value 
    // is -32767 or less. 
    int max = int.MinValue; 
 
    // Check loop while head not equal to null 
    while (head != null) 
    { 
 
        // If head.data is less than min and divisible 
        // by k then assign value of head.data to min 
        // otherwise node point to next node. 
        if ((head.data < min) && (head.data % k == 0)) 
            min = head.data; 
 
        // If head.data is greater than max and divisible 
        // by k then assign value of head.data to max 
        // otherwise node point to next node. 
        if ((head.data > max) && (head.data % k == 0)) 
            max = head.data; 
 
        head = head.next; 
    } 
 
    // Print max element 
    Console.WriteLine( "Max Element : " + max); 
 
    // print min element 
    Console.WriteLine( "Min Element : " + min); 
} 
 
// Function that push the element in linked list. 
static Node push( Node head, int data) 
{ 
    // Allocate dynamic memory for newNode. 
    Node newNode = new Node(); 
 
    // Assign the data into newNode. 
    newNode.data = data; 
 
    // newNode.next assign the address of 
    // head node. 
    newNode.next = (head); 
 
    // newNode become the headNode. 
    (head) = newNode; 
    return head; 
} 
 
// Driver Code 
public static void Main(String []args) 
{ 
    // Start with empty list 
    Node head = null; 
 
    // Using push() function to construct 
    // singly linked list 
    // 50.5.13.14.15 
    head = push(head, 15); 
    head = push(head, 14); 
    head = push(head, 13); 
    head = push(head, 5); 
    head = push(head, 50); 
 
    int k = 5; 
 
    findMaxMin(head, k); 
} 
} 
 
// This code contributed by Rajput-Ji

Javascript

<script>
// javascript program to find the smallest and largest 
// elements divisible by a given number k 
// in singly linked list     // Linked list node /
class Node {
    constructor(val) {
        this.data = val;
        this.next = null;
    }
}
 
    // Function to print max and min elements of
    // linked list divisible by K
    function findMaxMin(head , k) {
        // Declare a min variable and initialize
        // it with INT_MAX value.
        // INT_MAX is integer type and its value
        // is 32767 or greater.
        var min = Number.MAX_VALUE;
 
        // Declare a max variable and initialize
        // it with INT_MIN value.
        // INT_MIN is integer type and its value
        // is -32767 or less.
        var max = Number.MIN_VALUE;
 
        // Check loop while head not equal to null
        while (head != null) {
 
            // If head.data is less than min and divisible
            // by k then assign value of head.data to min
            // otherwise node point to next node.
            if ((head.data < min) && (head.data % k == 0))
                min = head.data;
 
            // If head.data is greater than max and divisible
            // by k then assign value of head.data to max
            // otherwise node point to next node.
            if ((head.data > max) && (head.data % k == 0))
                max = head.data;
 
            head = head.next;
        }
 
        // Print max element
        document.write("Max Element : " + max);
 
        // print min element
        document.write("<br/>Min Element : " + min);
    }
 
    // Function that push the element in linked list.
    function push(head , data) {
        // Allocate dynamic memory for newNode.
var newNode = new Node();
 
        // Assign the data into newNode.
        newNode.data = data;
 
        // newNode.next assign the address of
        // head node.
        newNode.next = (head);
 
        // newNode become the headNode.
        (head) = newNode;
        return head;
    }
 
    // Driver Code
     
        // Start with empty list
var head = null;
 
        // Using push() function to construct
        // singly linked list
        // 50.5.13.14.15
        head = push(head, 15);
        head = push(head, 14);
        head = push(head, 13);
        head = push(head, 5);
        head = push(head, 50);
 
        var k = 5;
 
        findMaxMin(head, k);
 
// This code contributed by umadevi9616 
</script>

Output

Max Element : 50
Min Element : 5

Complexity Analysis:

Time complexity: O(n)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!