Máximo de enteros ocurridos después de M operaciones circulares en un rango dado

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *