Check if most frequent element in Linked list is divisible by smallest element
Given a Linked list, the task is to check if the most frequently occurring element in the linked list is divisible by the smallest element in the linked list. If divisible then return true otherwise return false.
Note: If there is more than one mode then take the greater mode.
Examples:
Input: Linked List: 4 -> 2 -> 1 -> 3 -> 3 -> 3
Output: True
Explanation: The Most frequent element in the linked list is 3, and the smallest element in the list is 1. Since 3 is divisible by 1, the output is true.Input: Linked List: 7 -> 7 -> 4 -> 4 ->7-> 7 -> 3 -> 6 -> 8 -> 8
Output: False
Explanation: The Most frequent element in the linked list is 7, and the smallest element in the list is 3. Since 7 is not divisible by 3, the output is false.Input: Linked List: 2 -> 2 -> 4 -> 4 -> 4 -> 6 -> 6 -> 6 -> 8 -> 8 -> 10 -> 10
Output: True
Explanation: In this test case, there are two modes, 4 and 6. Both of them occur with the same frequency and 6 is greater than them and it is divisible by the smallest element (2), so the function should return true.
Approach: To solve the problem follow the below idea:
We can use a modified version of the hash table approach to avoid finding the Most frequent element explicitly. We can maintain a variable to keep track of the current maximum frequency and update it whenever we encounter an element with a higher frequency. If we encounter an element with the same frequency as the current maximum, we update the maximum element to be the greater of the two. We also maintain a variable to keep track of the smallest element. After scanning the entire linked list, we check if the maximum element is divisible by the smallest element.
Below are the steps to implement the above idea:
- Initialize a hash table to store the frequency of each element in the linked list.
- Initialize variables to keep track of the maximum frequency and the element with the maximum frequency in the hash table, and the smallest element in the linked list.
- Scan the linked list and update the hash table and the tracking variables.
- Check if the element with the maximum frequency is divisible by the smallest element.
- If yes, return true, else return false.
Below is the Implementation to solve the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Linked list node struct Node { int data; Node* next; }; // Function to check if the mode is // divisible by the smallest element bool checkModeDivisibleByMin(Node* head) { // Hash table to store the frequency // of each element unordered_map< int , int > freq; // Variables to keep track of maximum // frequency and the element with // the maximum frequency int maxFreq = 0, maxElement = INT_MIN; // Variable to keep track of // the smallest element int minElement = INT_MAX; // Scan the linked list and update // the hash table and variables Node* curr = head; while (curr != NULL) { int element = curr->data; freq[element]++; if (freq[element] > maxFreq || (freq[element] == maxFreq && element > maxElement)) { maxFreq = freq[element]; maxElement = element; } if (element < minElement) { minElement = element; } curr = curr->next; } // Check if the maximum element is // divisible by the smallest element if (maxElement % minElement == 0) { return true ; } else { return false ; } } // Function to insert a node at the // end of the linked list void insertNode(Node** headRef, int data) { Node* newNode = new Node{ data, NULL }; if (*headRef == NULL) { *headRef = newNode; return ; } Node* lastNode = *headRef; while (lastNode->next != NULL) { lastNode = lastNode->next; } lastNode->next = newNode; } // Function to print the linked list void printList(Node* head) { while (head != NULL) { cout << head->data; if (head->next != NULL) { cout << " -> " ; } head = head->next; } cout << endl; } // Driver code int main() { // Test the function with // some testcases Node* head1 = NULL; insertNode(&head1, 4); insertNode(&head1, 2); insertNode(&head1, 1); insertNode(&head1, 3); insertNode(&head1, 3); insertNode(&head1, 3); cout << "Linked List : " ; printList(head1); cout << "Output : " << boolalpha << checkModeDivisibleByMin(head1) << endl; return 0; } |
Linked List : 4 -> 2 -> 1 -> 3 -> 3 -> 3 Output : true
Time Complexity: O(n)
Auxiliary Space: O(n)
Approach 2: Sorting the linked list in ascending order and then traversing the sorted linked list to find the smallest and largest elements. After finding the smallest and largest elements, we check if the largest element is divisible by the smallest element.
Algorithm steps:
- Traverse the linked list and find its length.
- Create a new array of integers of the same size as the length of the linked list.
- Traverse the linked list again and copy its elements into the array.
- Sort the array in ascending order.
- Find the smallest element of the sorted array.
- Find the largest element of the sorted array.
- Check if the largest element is divisible by the smallest element.
- If yes, return true, else return false.
Below is the Implementation to solve the above approach:
C++
//C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Linked list node struct Node { int data; Node* next; }; // Function to check if the mode is // divisible by the smallest element bool checkModeDivisibleByMin(Node* head) { // Find the smallest element in the list int minElement = INT_MAX; Node* curr = head; while (curr != NULL) { int element = curr->data; if (element < minElement) { minElement = element; } curr = curr->next; } // Count the frequency of each element unordered_map< int , int > freq; curr = head; while (curr != NULL) { int element = curr->data; freq[element]++; curr = curr->next; } // Check if the maximum element is // divisible by the smallest element int maxFreq = 0, maxElement = INT_MIN; for ( auto it : freq) { int element = it.first; int frequency = it.second; if (frequency > maxFreq || (frequency == maxFreq && element > maxElement)) { maxFreq = frequency; maxElement = element; } } if (maxElement % minElement == 0) { return true ; } else { return false ; } } // Function to insert a node at the // end of the linked list void insertNode(Node** headRef, int data) { Node* newNode = new Node{ data, NULL }; if (*headRef == NULL) { *headRef = newNode; return ; } Node* lastNode = *headRef; while (lastNode->next != NULL) { lastNode = lastNode->next; } lastNode->next = newNode; } // Function to print the linked list void printList(Node* head) { while (head != NULL) { cout << head->data; if (head->next != NULL) { cout << " -> " ; } head = head->next; } cout << endl; } // Driver code int main() { // Test the function with // some testcases Node* head1 = NULL; insertNode(&head1, 4); insertNode(&head1, 2); insertNode(&head1, 1); insertNode(&head1, 3); insertNode(&head1, 3); insertNode(&head1, 3); cout << "Linked List : " ; printList(head1); cout << "Output : " << boolalpha << checkModeDivisibleByMin(head1) << endl; return 0; } |
Linked List : 4 -> 2 -> 1 -> 3 -> 3 -> 3 Output : true
Time Complexity: O(nlogn) because of the sorting algorithm used.
Auxiliary Space: O(1) because we are not using any additional data structures to store the frequency of elements.