CFPRIME - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Vikas Yadav
Tester: Deepak Chaudhary
Editorialist: Vikas Yadav

DIFFICULTY:

EASY

PREREQUISITES:

Data type
Prime Number

PROBLEM:

You are given a list of N element A1, A2…An and you have to create a new number by adding number of digits of each element in the list. If the number is prime then print “Yes” otherwise print “No”.

QUICK EXPLANATION:

Update the given list with respective number of digit of elements.
Create a new number by finding the sum of elements of updated list.
Check whether new number is prime or not.

EXPLANATION:

Take a new variable let say sum = 0, then find the number of digits of each elements present in list and update the sum with sum of all digit counts. Finally check if updated value of sum is prime then print “Yes” otherwise print “No”.

Common Mistake:

Use proper data-type to store value 0 ≤ A[i] ≤ 10^{18}.
Count the digit of element 0 as 1.

SOLUTIONS:

Setter's Solution 
// Chef and Prime

#include <bits/stdc++.h>
using namespace std;
#define int long long

// Check Prime
bool isPrime(int n) 
{  
    if (n < 2) 
        return false; 
  
    int e = sqrt(n);
    for (int i = 2; i <= e; i++) 
        if (n % i == 0) 
            return false; 
  
    return true; 
} 

void solve()
{
    int test_cases;
    cin >> test_cases;

    while(test_cases--)
    {
        int n;
        cin >> n;

        int arr[n];
        for(int i = 0; i < n; i++)
            cin >> arr[i];

        int sum = 0;
        
        // Digit counting
        for(int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += 1;
            else
            {
                int count = 0;
                while(arr[i] > 0)
                {
                    arr[i] /= 10 ;
                    count++;
                }

                sum += count;
            }
        }

        if(isPrime(sum))
        {
            cout<<"Yes\n";
        }
        else
        {
            cout<<"No\n";
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();

    return 0;
}
Solution using log10() 
// Chef and Prime

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int test_cases;
    cin >> test_cases;

    while(test_cases--)
    {
        int n;
        cin >> n;

        int a[n];
        for(int i = 0; i < n; i++)
            cin >> a[i];

        int result = 0;
        
        // Digit counting
        for(int i = 0; i < n; i++)
        {
            if(a[i] == 0)
                result += 1;
            else
                result += (floor(log10(a[i])) + 1);     //O(1)
        }

        bool flag = false;
        int e = sqrt(result);

        //Prime checking
        for(int i = 2 ; i <= e; i++)
        {
            if(result % i == 0)
            {
                flag = true;
                break;
            }
        }

        if(flag)
        {
            cout<<"No\n";
        }
        else
        {
            cout<<"Yes\n";
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();

    return 0;
}