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

Опубликовано: 5 Января, 2022

Для массива 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

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

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

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

C ++

 // C++ program to find sum of elements
 // in an array having prime frequency
 #include <bits/stdc++.h>
 using namespace std;
 // Function to create Sieve to check primes
 void SieveOfEratosthenes( bool prime[], int p_size)
 {
    // False here indicates
    // that it is not prime
    prime[0] = false ;
    prime[1] = false ; 
    for ( int p = 2; p * p <= p_size; p++) { 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p]) { 
            // Update all multiples of p,
            // set them to non-prime
            for ( int i = p * 2; i <= p_size; i += p)
                prime[i] = false ;
        }
    }
 }
 // Function to return the sum of elements
 // in an array having prime frequency
 int sumOfElements( int arr[], int n)
 {
    bool prime[n + 1];
    memset (prime, true , sizeof (prime)); 
    SieveOfEratosthenes(prime, n + 1);
    int i, j; 
    // Map is used to store
    // element frequencies
    unordered_map< int , int > m;
    for (i = 0; i < n; i++)
        m[arr[i]]++;
    int sum = 0; 
    // Traverse the map using iterators
    for ( auto it = m.begin(); it != m.end(); it++) { 
        // Count the number of elements
        // having prime frequencies
        if (prime[it->second]) {
            sum += (it->first);
        }
    }
    sum; return
 }
 // Driver code
 int main()
 {
    int arr[] = { 5, 4, 6, 5, 4, 6 };
    int n = sizeof (arr) / sizeof (arr[0]); 
    cout << sumOfElements(arr, n);
    return 0;
 }

Джава

 // Java program to find sum of elements
 // in an array having prime frequency
 import java.util.*;
 class GFG
 {
    // Function to create Sieve to check primes
    static void SieveOfEratosthenes( boolean prime[], int p_size)
    {
        // False here indicates
        // that it is not prime
        prime[ 0 ] = false ;
        prime[ 1 ] = false ;
    
        for ( int p = 2 ; p * p <= p_size; p++)
        {
    
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p])
            {
    
                // Update all multiples of p,
                // set them to non-prime
                for ( int i = p * 2 ; i <= p_size; i += p)
                    prime[i] = false ;
            }
        }
    }
    
    // Function to return the sum of elements
    // in an array having prime frequency
    static int sumOfElements( int arr[], int n)
    {
        boolean prime[] = new boolean [n + 1 ];
        Arrays.fill(prime, true );
    
        SieveOfEratosthenes(prime, n + 1 );
    
        int i, j;
    
        // Map is used to store
        // element frequencies
        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 ;
    
        // Traverse the map
        for (Map.Entry<Integer, Integer> entry : m.entrySet())
        {
            int key = entry.getKey();
            int value = entry.getValue();
            
            // Count the number of elements
            // having prime frequencies
            if (prime[value])
            {
                sum += (key);
            }
        }
    
        sum; return
    }
    
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 5 , 4 , 6 , 5 , 4 , 6 };
        int n = arr.length;
    
        System.out.println(sumOfElements(arr, n));
    }
 }
 // This code is contributed by ghanshyampandey

Python3

 # Python3 program to find Sum of elements
 # in an array having prime frequency
 import math as mt
 # Function to create Sieve to
 # check primes
 def SieveOfEratosthenes(prime, p_size):
    
    # False here indicates
    # that it is not prime
    prime[ 0 ] = False
    prime[ 1 ] = False 
    for p in range ( 2 , mt.ceil(mt.sqrt(p_size + 1 ))): 
        # If prime[p] is not changed,
        # then it is a prime
        if (prime[p]): 
            # Update all multiples of p,
            # set them to non-prime
            for i in range (p * 2 , p_size + 1 , p):
                prime[i] = False
        
# Function to return the Sum of elements
 # in an array having prime frequency
 def SumOfElements(arr, n):
    prime = [ True for i in range (n + 1 )]
    SieveOfEratosthenes(prime, n + 1 ) 
    i, j = 0 , 0 
    # Map is used to store
    # element frequencies
    m = dict ()
    for i in range (n):
        if arr[i] in m.keys():
            m[arr[i]] + = 1
        else :
            m[arr[i]] = 1
            
    Sum = 0 
    # Traverse the map using iterators
    for i in m:
        
        # Count the number of elements
        # having prime frequencies
        if (prime[m[i]]):
            Sum + = (i)
    
    return Sum
 # Driver code
 arr = [ 5 , 4 , 6 , 5 , 4 , 6 ]
 n = len (arr)
 print (SumOfElements(arr, n))
 # This code is contributed
 # by Mohit kumar 29

C #

 // C# program to find sum of elements
 // in an array having prime frequency
 using System;
 using System.Collections.Generic;
 class GFG
 {
    // Function to create Sieve to check primes
    static void SieveOfEratosthenes( bool []prime, int p_size)
    {
        // False here indicates
        // that it is not prime
        prime[0] = false ;
        prime[1] = false ;
    
        for ( int p = 2; p * p <= p_size; p++)
        {
    
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p])
            {
    
                // Update all multiples of p,
                // set them to non-prime
                for ( int i = p * 2; i <= p_size; i += p)
                    prime[i] = false ;
            }
        }
    }
    
    // Function to return the sum of elements
    // in an array having prime frequency
    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);
    
        // Map is used to store
        // element frequencies
        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;
    
        // Traverse the map
        foreach > entry (KeyValuePair< int , int in m)
        {
            int key = entry.Key;
            int value = entry.Value;
            
            // Count the number of elements
            // having prime frequencies
            if (prime[value])
            {
                sum += (key);
            }
        }
    
        sum; return
    }
    
    // Driver code
    public static void Main(String []args)
    {
        int []arr = { 5, 4, 6, 5, 4, 6 };
        int n = arr.Length;
    
        Console.WriteLine(sumOfElements(arr, n));
    }
 }
 // This code is contributed by 29AjayKumar

Javascript

 <script>
 // Javascript program to find sum of elements
 // in an array having prime frequency
 // Function to create Sieve to check primes
 function SieveOfEratosthenes(prime, p_size)
 {
    // False here indicates
    // that it is not prime
    prime[0] = false ;
    prime[1] = false ; 
    for (let p = 2; p * p <= p_size; p++) { 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p]) { 
            // Update all multiples of p,
            // set them to non-prime
            for (let i = p * 2; i <= p_size; i += p)
                prime[i] = false ;
        }
    }
 }
 // Function to return the sum of elements
 // in an array having prime frequency
 function sumOfElements(arr, n) {
    let prime = new Array(n + 1);
    prime.fill( true ) 
    SieveOfEratosthenes(prime, n + 1);
    let i, j;
    // Map is used to store
    // element frequencies
    let m = new Map();
    for (i = 0; i < n; i++) {
        if (m.has(arr[i]))
            m.set(arr[i], m.get(arr[i]) + 1);
        else
            m.set(arr[i], 1);
    }
    let sum = 0;
    // Traverse the map using iterators
    for (let it of m) { 
        // Count the number of elements
        // having prime frequencies
        if (prime[it[1]]) {
            sum += (it[0]);
        }
    }
    sum; return
 }
 // Driver code
 let arr = [5, 4, 6, 5, 4, 6];
 let n = arr.length;
 document.write(sumOfElements(arr, n));
 // This code is contributed by gfgking
 </script>

Выход:

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Technical Scripter Олимпиады по программированию

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

C ++

Джава

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ