Given a singly linked list of 
nodes. Find the smallest and largest elements in linked list divisible by a given number 
.
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: 5Input : 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 Kvoid 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 Codeint 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 = 5findMaxMin(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 listvar 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
