Dado un entero N y una array arr[] que consta de M enteros del rango [1, N] . (M – 1) las operaciones deben realizarse. En cada i- ésima operación, recorre todos los elementos consecutivos en el rango [1, N] desde arr[i] hasta arr[i + 1] circularmente. La tarea es imprimir los elementos más visitados en orden después de completar M operaciones.
Ejemplos:
Entrada: N = 4, arr[] = {1, 2, 1, 2}
Salida: 1 2
Explicación:
Operación 1: 1–>2.
Operación 2: 2–>3–>4–>1.
Operación 3: 1–>2.
Después de completar las tres operaciones, los enteros máximos que ocurren son {1, 2}.
Por lo tanto, imprime {1, 2}Entrada: N = 6, arr[] = {1, 2, 1, 2, 3}
Salida: 1 2 3
Enfoque: siga los pasos a continuación para resolver el problema:
- Cree un mapa para contar el número de veces que se visita un elemento y la variable maxVisited para almacenar el recuento de visitas máximas para cualquier elemento.
- Recorra la array y realice las siguientes operaciones:
- Comience con el elemento actual en A[i] y visite todos los elementos consecutivos en forma circular ( mod N ) hasta A[i+1] .
- Durante cada iteración, incremente su recuento de visitas en 1 y realice un seguimiento del recuento de visitas más alto en la variable maxVisited .
- Después de completar cada ronda, incremente el conteo en 1 para el último elemento visitado.
- Encuentre la frecuencia máxima (digamos maxFreq ) almacenada en el Mapa .
- Después de completar los pasos anteriores, itere el Mapa e imprima los elementos que tienen la frecuencia maxFreq .
A continuación se muestra la implementación del enfoque anterior:
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 operations
void 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 form 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 Code
int main()
{
int N = 4;
vector<int> arr = { 1, 2, 1, 2 };
// Function Call
mostvisitedsector(N, arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find the maximum
// occurred integer after completing
// all circular operations
static 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 form 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 Code
public 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 operations
def 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 form 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 Code
if __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 approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to find the maximum
// occurred integer after completing
// all circular operations
static 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 form 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 Code
public 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 operations
function 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 form 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 Code
var N = 4;
var arr = [1, 2, 1, 2];
// Function Call
mostvisitedsector(N, arr);
// This code is contributed by importantly.
</script>
Producción:
1 2
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA