6

Check if most frequent element in Linked list is divisible by smallest element

 2 years ago
source link: https://www.geeksforgeeks.org/check-if-most-frequent-element-in-linked-list-is-divisible-by-smallest-element//
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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++ 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;
}
Output
Linked List : 4 -> 2 -> 1 -> 3 -> 3 -> 3
Output : true

Time Complexity: O(n)
Auxiliary Space: O(n)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK