Given a Singly linked list, the task is to count the number of nodes whose data value is equal to its frequency.
Examples:
Input: Linked list = 2 -> 3 -> 3 -> 3 -> 4 -> 2
Output: 2
Frequency of element 2 is 2
Frequency of element 3 is 3
Frequency of element 4 is 1
So, 2 and 3 are elements which have same frequency as it’s valueInput: Linked list = 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 1
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach:
Approach to solve this problem is as following
- Iterate over the linked list and store the frequency of every element of the array using a map
- Iterate over the map and count the number of elements whose frequency is equal to their value
Below is the implementation of the above approach:
C++
/* Link list node */#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* next;};// Function to add a node at the // beginning of Listvoid push(Node** head_ref, int data) { /* allocate node */ Node* new_node =new Node(); /* put in the data */ new_node->data = data; // link the old list of the new // node new_node->next = (*head_ref); // move the head to point to the // new node (*head_ref) = new_node; } // Counts the no. of occurrences of a// node in a linked listint countValuesWithSameFreq(Node* start){ map<int, int> mpp; Node* current = start; int count = 0; while (current != NULL) { mpp[current->data] += 1; current = current->next; } int ans = 0; for (auto x : mpp) { int value = x.first; int freq = x.second; // Check if value equals to frequency // and increment the count if (value == freq) { ans++; } } return ans;}// main programint main(){ Node* head = NULL; push(&head, 3); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 2); push(&head, 3); cout << countValuesWithSameFreq(head); return 0;} |
Java
/* Link list node */import java.util.*;class GFG{public static class Node{ int data; Node next;};// Function to add a node at the// beginning of Liststatic Node push(Node head_ref, int data){ // Allocate node Node new_node = new Node(); // Put in the data new_node.data = data; // Link the old list of the new // node new_node.next = head_ref; // Move the head to point to the // new node head_ref = new_node; return head_ref;}// Counts the no. of occurrences of a// node in a linked liststatic int countValuesWithSameFreq(Node start){ HashMap<Integer, Integer> mpp = new HashMap<>(); Node current = start; while (current != null) { if (mpp.containsKey(current.data)) { mpp.put(current.data, mpp.get(current.data) + 1); } else { mpp.put(current.data, 1); } current = current.next; } int ans = 0; for(Map.Entry<Integer, Integer> x : mpp.entrySet()) { int value = x.getKey(); int freq = x.getValue(); // Check if value equals to frequency // and increment the count if (value == freq) { ans++; } } return ans;}// Driver code public static void main(String[] args){ Node head = null; head = push(head, 3); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 2); head = push(head, 3); System.out.print(countValuesWithSameFreq(head));}}// This code is contributed by amal kumar choubey |
Python3
# Link list node class Node: def __init(self, next): self.data = 0 self.next = None # Function to add a node at the # beginning of Listdef push(head_ref, data): # Allocate node new_node = Node() # Put in the data new_node.data = data # Link the old list of the new # node new_node.next = (head_ref) # Move the head to point to the # new node (head_ref) = new_node return head_ref # Counts the no. of occurrences of a# node in a linked listdef countValuesWithSameFreq(start): mpp = dict() current = start count = 0 while (current != None): if current.data not in mpp: mpp[current.data] = 0 mpp[current.data] += 1 current = current.next ans = 0 for x in mpp.keys(): value = x freq = mpp[x] # Check if value equals to frequency # and increment the count if (value == freq): ans += 1 return ans # Driver codeif __name__=='__main__': head = None head = push(head, 3) head = push(head, 4) head = push(head, 3) head = push(head, 2) head = push(head, 2) head = push(head, 3) print(countValuesWithSameFreq(head)) # This code is contributed by rutvik_56 |
C#
/* Link list node */using System;using System.Collections.Generic;class GFG{public class Node{ public int data; public Node next;};// Function to add a node at the// beginning of Liststatic Node push(Node head_ref, int data){ // Allocate node Node new_node = new Node(); // Put in the data new_node.data = data; // Link the old list of the new // node new_node.next = head_ref; // Move the head to point to the // new node head_ref = new_node; return head_ref;}// Counts the no. of occurrences of a// node in a linked liststatic int countValuesWithSameFreq(Node start){ Dictionary<int, int> mpp = new Dictionary<int, int>(); Node current = start; while (current != null) { if (mpp.ContainsKey(current.data)) { mpp[current.data] = mpp[current.data] + 1; } else { mpp.Add(current.data, 1); } current = current.next; } int ans = 0; foreach(KeyValuePair<int, int> x in mpp) { int value = x.Key; int freq = x.Value; // Check if value equals to frequency // and increment the count if (value == freq) { ans++; } } return ans;}// Driver code public static void Main(String[] args){ Node head = null; head = push(head, 3); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 2); head = push(head, 3); Console.Write(countValuesWithSameFreq(head));}}// This code is contributed by Rohit_ranjan |
Javascript
<script>/* Link list node */class Node{ constructor() { this.data = 0; this.next = null; }};// Function to add a node at the// beginning of Listfunction push(head_ref, data){ // Allocate node var new_node = new Node(); // Put in the data new_node.data = data; // Link the old list of the new // node new_node.next = head_ref; // Move the head to point to the // new node head_ref = new_node; return head_ref;}// Counts the no. of occurrences of a// node in a linked listfunction countValuesWithSameFreq(start){ var mpp = new Map(); var current = start; while (current != null) { if (mpp.has(current.data)) { mpp.set(current.data , mpp.get(current.data)+1); } else { mpp.set(current.data, 1); } current = current.next; } var ans = 0; mpp.forEach((value, key) => { var value = value; var freq = key; // Check if value equals to frequency // and increment the count if (value == freq) { ans++; } }); return ans;}// Driver code var head = null;head = push(head, 3);head = push(head, 4);head = push(head, 3);head = push(head, 2);head = push(head, 2);head = push(head, 3);document.write(countValuesWithSameFreq(head));</script> |
Output:
2
Complexity Analysis:
Time Complexity: For a given linked list of size n, we are iterating over it once. So the time complexity of this solution is O(n)
Space Complexity: For a given linked list of size n, we are using an extra map which can have maximum of n key-values, so space complexity of this solution is O(n)
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!
