Рубрики

Сумма элементов в массиве с основной частотой

При заданном массиве arr задача состоит в том, чтобы найти сумму элементов, которые имеют простые частоты в массиве.
Примечание: 1 не является ни простым, ни составным.

Примеры:

Input: arr[] = {5, 4, 6, 5, 4, 6}
Output: 15
All the elements appear 2 times which is a prime
So, 5 + 4 + 6 = 15

Input: arr[] = {1, 2, 3, 3, 2, 3, 2, 3, 3}
Output: 5
Only 2 and 3 appears prime number of times i.e. 3 and 5 respectively.
So, 2 + 3 = 5

Подходить:

  • Пройдите по массиву и сохраните частоты всех элементов на карте .
  • Построить сито из эратосфена, которое будет использоваться для проверки простоты числа в O (1) времени.
  • Вычислите сумму элементов с основной частотой, используя массив Sieve, рассчитанный на предыдущем шаге.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для поиска суммы элементов
// в массиве с основной частотой
#include <bits/stdc++.h>

using namespace std;

  
// Функция создания сита для проверки простых чисел

void SieveOfEratosthenes(bool prime[], int p_size)

{

    // Ложь здесь указывает

    // что это не простое число

    prime[0] = false;

    prime[1] = false;

  

    for (int p = 2; p * p <= p_size; p++) {

  

        // Если простое число [p] не изменилось,

        // тогда это простое число

        if (prime[p]) {

  

            // Обновить все кратные р,

            // установить их не простыми

            for (int i = p * 2; i <= p_size; i += p)

                prime[i] = false;

        }

    }

}

  
// Функция для возврата суммы элементов
// в массиве с основной частотой

int sumOfElements(int arr[], int n)

{

    bool prime[n + 1];

    memset(prime, true, sizeof(prime));

  

    SieveOfEratosthenes(prime, n + 1);

  

    int i, j;

  

    // Карта используется для хранения

    // частоты элементов

    unordered_map<int, int> m;

    for (i = 0; i < n; i++)

        m[arr[i]]++;

  

    int sum = 0;

  

    // Обход карты с использованием итераторов

    for (auto it = m.begin(); it != m.end(); it++) {

  

        // Подсчитать количество элементов

        // имея простые частоты

        if (prime[it->second]) {

            sum += (it->first);

        }

    }

  

    return sum;

}

  
// Код драйвера

int main()

{

    int arr[] = { 5, 4, 6, 5, 4, 6 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    cout << sumOfElements(arr, n);

    return 0;

}

Джава

// Java программа для поиска суммы элементов
// в массиве с основной частотой

import java.util.*;

  

class GFG 

{

  

    // Функция создания сита для проверки простых чисел

    static void SieveOfEratosthenes(boolean prime[], int p_size)

    {

        // Ложь здесь указывает

        // что это не простое число

        prime[0] = false;

        prime[1] = false;

      

        for (int p = 2; p * p <= p_size; p++)

        {

      

            // Если простое число [p] не изменилось,

            // тогда это простое число

            if (prime[p]) 

            {

      

                // Обновить все кратные р,

                // установить их не простыми

                for (int i = p * 2; i <= p_size; i += p)

                    prime[i] = false;

            }

        }

    }

      

    // Функция для возврата суммы элементов

    // в массиве с основной частотой

    static int sumOfElements(int arr[], int n)

    {

        boolean prime[] = new boolean[n + 1];

        Arrays.fill(prime, true);

      

        SieveOfEratosthenes(prime, n + 1);

      

        int i, j;

      

        // Карта используется для хранения

        // частоты элементов

        HashMap<Integer, Integer> m = new HashMap<>();

        for (i = 0; i < n; i++) 

        {

            if(m.containsKey(arr[i]))

                m.put(arr[i], m.get(arr[i]) + 1);

            else

                m.put(arr[i], 1);

        }

      

        int sum = 0;

      

        // Пройдите по карте

        for (Map.Entry<Integer, Integer> entry : m.entrySet()) 

        {

            int key = entry.getKey();

            int value = entry.getValue();

              

            // Подсчитать количество элементов

            // имея простые частоты

            if (prime[value]) 

            {

                sum += (key);

            }

        }

      

        return sum;

    }

      

    // Код драйвера

    public static void main(String args[])

    {

        int arr[] = { 5, 4, 6, 5, 4, 6 };

        int n = arr.length;

      

        System.out.println(sumOfElements(arr, n));

    }

}

  
// Этот код предоставлен ghanshyampandey

python3

# Python3 программа для поиска суммы элементов
# в массиве с основной частотой

import math as mt

  
# Функция создания сита для
# проверить простые числа

def SieveOfEratosthenes(prime, p_size):

      

    # Ложь здесь указывает

    # что это не простое

    prime[0] = False

    prime[1] = False

  

    for p in range(2, mt.ceil(mt.sqrt(p_size + 1))):

  

        # Если простое число [p] не изменилось,

        # тогда это простое

        if (prime[p]):

  

            # Обновить все кратные р,

            # установите их не простыми

            for i in range(p * 2, p_size + 1, p):

                prime[i] = False

          
# Функция для возврата суммы элементов
# в массиве с основной частотой

def SumOfElements(arr, n):

    prime = [True for i in range(n + 1)]

    SieveOfEratosthenes(prime, n + 1)

  

    i, j = 0, 0

  

    # Карта используется для хранения

    # частоты элементов

    m = dict()

    for i in range(n):

        if arr[i] in m.keys():

            m[arr[i]] += 1

        else:

            m[arr[i]] = 1

              

    Sum = 0

  

    # Обход карты с использованием итераторов

    for i in m:

          

        # Подсчитать количество элементов

        # имеющие простые частоты

        if (prime[m[i]]):

            Sum += (i)

      

    return Sum

  
# Код драйвера

arr = [5, 4, 6, 5, 4, 6 ]

n = len(arr)

print(SumOfElements(arr, n))

  
# Этот код добавлен
# Мохит Кумар 29

C #

// C # программа для поиска суммы элементов
// в массиве с основной частотой

using System;

using System.Collections.Generic;

  

class GFG 

{

  

    // Функция создания сита для проверки простых чисел

    static void SieveOfEratosthenes(bool []prime, int p_size)

    {

        // Ложь здесь указывает

        // что это не простое число

        prime[0] = false;

        prime[1] = false;

      

        for (int p = 2; p * p <= p_size; p++)

        {

      

            // Если простое число [p] не изменилось,

            // тогда это простое число

            if (prime[p]) 

            {

      

                // Обновить все кратные р,

                // установить их не простыми

                for (int i = p * 2; i <= p_size; i += p)

                    prime[i] = false;

            }

        }

    }

      

    // Функция для возврата суммы элементов

    // в массиве с основной частотой

    static int sumOfElements(int []arr, int n)

    {

        bool []prime = new bool[n + 1];

        for(int i = 0; i < n+1; i++)

            prime[i] = true;

      

        SieveOfEratosthenes(prime, n + 1);

  

      

        // Карта используется для хранения

        // частоты элементов

        Dictionary<int,int> m = new Dictionary<int,int>();

        for (int i = 0 ; i < n; i++)

        {

            if(m.ContainsKey(arr[i]))

            {

                var val = m[arr[i]];

                m.Remove(arr[i]);

                m.Add(arr[i], val + 1); 

            }

            else

            {

                m.Add(arr[i], 1);

            }

        }

      

        int sum = 0;

      

        // Пройдите по карте

        foreach(KeyValuePair<int, int> entry in m)

        {

            int key = entry.Key;

            int value = entry.Value;

              

            // Подсчитать количество элементов

            // имея простые частоты

            if (prime[value]) 

            {

                sum += (key);

            }

        }

      

        return sum;

    }

      

    // Код драйвера

    public static void Main(String []args)

    {

        int []arr = { 5, 4, 6, 5, 4, 6 };

        int n = arr.Length;

      

        Console.WriteLine(sumOfElements(arr, n));

    }

}

  
// Этот код предоставлен 29AjayKumar

Выход:

15

Рекомендуемые посты:

Сумма элементов в массиве с основной частотой

0.00 (0%) 0 votes