Given an integer N and an array arr[] consisting of M integers from the range [1, N]. (M – 1) operations need to performed. In every ith operation, traverse every consecutive elements in the range [1, N] from arr[i] to arr[i + 1] circularly. The task is to print the most visited elements in sorted order after completing M operations.
Examples:
Input: N = 4, arr[] = {1, 2, 1, 2}
Output: 1 2
Explanation:
Operation 1: 1–>2.
Operation 2: 2–>3–>4–>1.
Operation 3: 1–>2.
After completing the three operations, the maximum occurred integers are {1, 2}.
Therefore, print {1, 2}Input: N = 6, arr[] = {1, 2, 1, 2, 3}
Output: 1 2 3
Approach: Follow the steps below to solve the problem:
- Create a Map to count the number of times an element is visited and variable maxVisited to store the count of maximum visits for any element.
- Traverse the array and perform the following operations:
- Start with the current element in A[i] and visit all the consecutive elements in circularly(mod N) till A[i+1].
- During each iteration, increment its visit count by 1, and keep track of the highest visit count in the maxVisited variable.
- After completing each round, increment the count by 1 for the last visited element.
- Find the maximum frequency(say maxFreq) stored in the Map.
- After completing the above steps, iterate the Map and print the elements having frequency maxFreq.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum// occurred integer after completing// all circular operationsvoid mostvisitedsector(int N, vector<int>& A){ // Stores the highest visit count // for any element int maxVisited = 0; // Stores the number of times an // element is visited map<int, int> mp; // Iterate over the array for (int i = 0; i < A.size() - 1; i++) { int start = A[i] % N; int end = A[i + 1] % N; // Iterate over the range // circularly from start to end while (start != end) { // Count number of times an // element is visited if (start == 0) { // Increment frequency // of N mp[N]++; // Update maxVisited if (mp[N] > maxVisited) { maxVisited = mp[N]; } } else { // Increment frequency // of start mp[start]++; // Update maxVisited if (mp[start] > maxVisited) { maxVisited = mp[start]; } } // Increment the start start = (start + 1) % N; } } // Increment the count for the last // visited element mp[A.back()]++; if (mp[A.back()] > maxVisited) { maxVisited = mp[A.back()]; } // Print most visited elements for (auto x : mp) { if (x.second == maxVisited) { cout << x.first << " "; } }}// Driver Codeint main(){ int N = 4; vector<int> arr = { 1, 2, 1, 2 }; // Function Call mostvisitedsector(N, arr); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to find the maximum// occurred integer after completing// all circular operationsstatic void mostvisitedsector(int N, ArrayList<Integer> A){ // Stores the highest visit count // for any element int maxVisited = 0; // Stores the number of times an // element is visited HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Iterate over the array for(int i = 0; i < A.size() - 1; i++) { int start = A.get(i) % N; int end = A.get(i + 1) % N; // Iterate over the range // circularly from start to end while (start != end) { // Count number of times an // element is visited if (start == 0) { // Increment frequency // of N if (mp.containsKey(N)) mp.put(N, mp.get(N) + 1); else mp.put(N, 1); // Update maxVisited if (mp.get(N) > maxVisited) { maxVisited = mp.get(N); } } else { // Increment frequency // of start if (mp.containsKey(start)) mp.put(start, mp.get(start) + 1); else mp.put(start, 1); // Update maxVisited if (mp.get(start) > maxVisited) { maxVisited = mp.get(start); } } // Increment the start start = (start + 1) % N; } } // Increment the count for the last // visited element int last = A.get(A.size() - 1); if (mp.containsKey(last)) mp.put(last, mp.get(last) + 1); else mp.put(last, 1); if (mp.get(last) > maxVisited) { maxVisited = mp.get(last); } // Print most visited elements for(Map.Entry x : mp.entrySet()) { if ((int)x.getValue() == maxVisited) { System.out.print(x.getKey() + " "); } }}// Driver Codepublic static void main(String[] args){ int N = 4; ArrayList<Integer> arr = new ArrayList<Integer>( Arrays.asList(1, 2, 1, 2)); // Function Call mostvisitedsector(N, arr);}}// This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach# Function to find the maximum# occurred integer after completing# all circular operationsdef mostvisitedsector(N, A): # Stores the highest visit count # for any element maxVisited = 0 # Stores the number of times an # element is visited mp = {} # Iterate over the array for i in range(0, len(A) - 1): start = A[i] % N end = A[i + 1] % N # Iterate over the range # circularly from start to end while (start != end): # Count number of times an # element is visited if (start == 0): # Increment frequency # of N if N in mp: mp[N] = mp[N] + 1 else: mp[N] = 1 # Update maxVisited if (mp[N] > maxVisited): maxVisited = mp[N] else: # Increment frequency # of start if start in mp: mp[start] = mp[start] + 1 else: mp[start] = 1 # Update maxVisited if (mp[start] > maxVisited): maxVisited = mp[start] # Increment the start start = (start + 1) % N # Increment the count for the last # visited element if A[-1] in mp: mp[A[-1]] = mp[A[-1]] + 1 if (mp[A[-1]] > maxVisited): maxVisited = mp[A[-1]] # Print most visited elements for x in mp: if (mp[x] == maxVisited): print(x, end = ' ')# Driver Codeif __name__ == '__main__': N = 4 arr = [ 1, 2, 1, 2 ] # Function Call mostvisitedsector(N, arr)# This code is contributed by akhilsaini |
C#
// C# program for the above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{// Function to find the maximum// occurred integer after completing// all circular operationsstatic void mostvisitedsector(int N, ArrayList A){ // Stores the highest visit count // for any element int maxVisited = 0; // Stores the number of times an // element is visited Dictionary<int, int> mp = new Dictionary<int, int>(); // Iterate over the array for(int i = 0; i < A.Count - 1; i++) { int start = (int)A[i] % N; int end = (int)A[i + 1] % N; // Iterate over the range // circularly from start to end while (start != end) { // Count number of times an // element is visited if (start == 0) { // Increment frequency // of N if (mp.ContainsKey(N)) mp[N] = mp[N] + 1; else mp[N] = 1; // Update maxVisited if (mp[N] > maxVisited) { maxVisited = mp[N]; } } else { // Increment frequency // of start if (mp.ContainsKey(start)) mp[start] = mp[start] + 1; else mp[start] = 1; // Update maxVisited if (mp[start] > maxVisited) { maxVisited = mp[start]; } } // Increment the start start = (start + 1) % N; } } // Increment the count for the last // visited element int last_element = (int)A[A.Count - 1]; if (mp.ContainsKey(last_element)) mp[last_element] = mp[last_element] + 1; else mp[last_element] = 1; if (mp[last_element] > maxVisited) { maxVisited = mp[last_element]; } // Print most visited elements foreach(var x in mp) { if ((int)x.Value == maxVisited) { Console.Write(x.Key + " "); } }}// Driver Codepublic static void Main(){ int N = 4; ArrayList arr = new ArrayList(){ 1, 2, 1, 2 }; // Function Call mostvisitedsector(N, arr);}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum// occurred integer after completing// all circular operationsfunction mostvisitedsector(N, A){ // Stores the highest visit count // for any element var maxVisited = 0; // Stores the number of times an // element is visited var mp = new Map(); // Iterate over the array for (var i = 0; i < A.length - 1; i++) { var start = A[i] % N; var end = A[i + 1] % N; // Iterate over the range // circularly from start to end while (start != end) { // Count number of times an // element is visited if (start == 0) { // Increment frequency // of N if(mp.has(N)) mp.set(N, mp.get(N)+1); else mp.set(N, 1); // Update maxVisited if (mp.get(N) > maxVisited) { maxVisited = mp.get(N); } } else { // Increment frequency // of start if(mp.has(start)) mp.set(start, mp.get(start)+1) else mp.set(start, 1); // Update maxVisited if (mp.get(start) > maxVisited) { maxVisited = mp.get(start); } } // Increment the start start = (start + 1) % N; } } // Increment the count for the last // visited element var back = A[A.length-1]; if(mp.has(back)) mp.set(back, mp.get(back)+1) else mp.set(back, 1); if (mp.get(back) > maxVisited) { maxVisited = mp.get(back); } // Print most visited elements mp.forEach((value, key) => { if (value == maxVisited) { document.write(key+" "); } });}// Driver Codevar N = 4;var arr = [1, 2, 1, 2];// Function Callmostvisitedsector(N, arr);// This code is contributed by importantly.</script> |
Output:
1 2
Time Complexity: O(N*M)
Auxiliary Space: 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!
