Chef and easy problem 2 CodeChef Solution

Problem -Chef and easy problem 2 CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Chef and easy problem 2 CodeChef Solution in C++14

#include <bits/stdc++.h>
//for policy based ds //p.order_of_key() -> returns index of value //*p.find_by_order(3) ->value at index
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less

using namespace __gnu_pbds; //for policy based ds
using namespace std;

#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define maxHeap priority_queue<int>;
#define minHeap priority_queue<int, vi, greater<int>>
#define mod 1000000007
#define inf 1e18
#define rep(i, s, n) for (int i = s; i < n; i++)
#define sp(ans, pre) fixed << setprecision(pre) << y
#define pb push_back
#define srt(v) sort(v.begin(), v.end())
#define all(v) begin(v), end(v)
#define inputArr(i, arr) \
    for (int &i : arr)   \
        cin >> i;
#define ll long long
#define ull unsigned long long
#define lld long double
#define kickPrint(tt) cout << "Case #" << tt << ": "

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

time_t Begin;

//////////////////Debug///////////////
#define debug(x)       \
    cout << #x << " "; \
    _print(x);         \
    cout << endl;
void _print(ll t)
{
    cout << t;
}
//void _print(int t) {cout << t;}
void _print(string t) { cout << t; }
void _print(char t) { cout << t; }
void _print(lld t) { cout << t; }
void _print(double t) { cout << t; }
void _print(ull t) { cout << t; }
void display(ll a[], ll n)
{
    for (ll i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p)
{
    cout << "{";
    _print(p.ff);
    cout << ",";
    _print(p.ss);
    cout << "}";
}
template <class T>
void _print(vector<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T>
void _print(set<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T>
void _print(multiset<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T, class V>
void _print(map<T, V> v)
{
    cout << "[ ";
    for (auto i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <typename T, typename U>
inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }

void init()
{
    Begin = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
void timeTaken()
{
#ifndef ONLINE_JUDGE
    double time_taken = double(clock() - Begin) / double(CLOCKS_PER_SEC);
    cout << "Execution Time: " << fixed << setprecision(5) << time_taken << "s\n";
#endif
}

vector<int> computeLps(string s, int M)
{
    int len = 0;
    vector<int> lps(M + 20);

    lps[0] = 0;

    int i = 1;
    while (i < M)
    {
        if (s[i] == s[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
            {
                len = lps[len - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
    // debug(len);
    return lps;
}

int ceiling(int x, int y)
{
    int res = x / y;
    if (x % y)
    {
        if (x >= 0)
            res++;
    }
    return res;
}

vector<vector<int>> makePrefix(vector<vector<int>> &grid)
{
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> prefix(n + 1, vector<int>(m + 1));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
        }
    }

    return prefix;
}

int query(int x1, int y1, int x2, int y2, vector<vector<int>> &prefix)
{
    // cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;

    // cout << "query: " << prefix[x2 + 1][y2 + 1] << " " << prefix[x2 + 1][y1] << " " << prefix[x1][y2 + 1] << " " << prefix[x1][y2] << endl;
    return prefix[x2 + 1][y2 + 1] - prefix[x2 + 1][y1] - prefix[x1][y2 + 1] + prefix[x1][y1];
}

int toInt(string &s)
{
    int res = 0;
    for (char c : s)
        res = res * 10 + (c - '0');
    return res;
}

bool isValid(int i, int j, int n, int m)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, 1, -1, 0};

int moduloExponentiation(int a, int b, int m)
{
    if (b == 0)
        return 1;

    int res = moduloExponentiation(a, b / 2, m);
    res = (res * res) % m;

    if (b % 2)
        res = (res * a) % m;
    return res;
}

vector<int> smallesrPrimeDivisor(int n)
{
    vector<int> arr(n + 1);
    for (int i = 2; i <= n; i++)
    {
        if (arr[i])
            continue;
        for (int j = i; j <= n; j += i)
            if (!arr[j])
                arr[j] = i;
    }
    arr[1] = 1;
    return arr;
}

// const int MX = 100000;
int32_t main()
{
    init();
    //--------------------

    vector<int> smallestPrimeDivisorArr = smallesrPrimeDivisor(1e6 + 10);
    int t = 1;
    cin >> t;
    for (int tt = 1; tt <= t; tt++)
    {
        int n;
        cin >> n;
        vector<int> arr(n);
        inputArr(i, arr);
        map<int, int> primeCnt;
        for (int i : arr)
        {
            int x = i;
            while (x > 1)
            {
                int pre = smallestPrimeDivisorArr[x];
                int cnt = 0;
                while (smallestPrimeDivisorArr[x] == pre)
                {
                    x /= smallestPrimeDivisorArr[x];
                    cnt++;
                }

                primeCnt[pre] = max(primeCnt[pre], cnt);
            }
        }

        int res = 0;
        for (auto i : primeCnt)
            res += i.second;

        cout << res << "\n";
    }
    //---------------------------
    timeTaken();
    return 0;
}

Chef and easy problem 2 CodeChef Solution in PYTH 3

# cook your dish here
from collections import defaultdict
from sys import *
def input():
    return stdin.readline()
a = [True] * 1000100
def primes_sieve2(limit):
    a[0] = a[1] = False
    l=[]
    for (i, isprime) in enumerate(a):
        if isprime:
            l.append(i)
            for n in range(i*i, limit, i):
                a[n] = False
    return l
prime=primes_sieve2(1000100)
fac=[[] for i in range(1000100)]
for i in prime:
    for j in range(i,1000100,i):
        fac[j].append(i)
def get(divisors):
    div=fac[divisors]
    new=defaultdict(int)
    tar=divisors;ind=0;
    while(tar>1):
        fir=div[ind]
        while(tar>1 and tar%fir==0):
            tar//=fir;
            new[fir]+=1
        ind+=1
    return new
for _ in range(int(input())):
    n=int(input())
    lis=[int(i) for i in input().split()]
    vis=defaultdict(list);it=0
    for i in lis:
        for i,j in get(i).items():
            vis[i].append(j)
    for j in vis.values():
        it+=max(j)
    print(it)

Chef and easy problem 2 CodeChef Solution in C

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define inchar getchar_unlocked
 
inline int inPos() 
{
	int n = 0;
	register int ch = inchar();
	while (ch < '0' || ch > '9') ch = inchar();
	while (ch >= '0' && ch <= '9') 
	{
		n = (n << 3) + (n << 1) + (ch - '0');
		ch = inchar();
	}
	return n;
}

int cmp(int *a, int *b)
{
    return (*a>*b);
}
 
int main()
{
    int i, j, x, k = 1, p[168], *c, t, a, b, max, pos;
    c = (int *)calloc(998,sizeof(int));
    p[0] = 2;
    for (i=3; i<32; i+=2)
    {
        if (c[i]==0)
        {
            p[k++] = i;
            for (j=i*i, x=i<<1; j<998; j+=x)
                c[j] = 1;
        }
    }
    for (;i<998; i+=2)
    {
        if (c[i]==0)
            p[k++] = i;
    }
    t = inPos();
    while (t--)
    {
        b = inPos();
        int q, *ans, w[b], count=0, v=0;
        ans = (int *)calloc(168,sizeof(int));
        max = -1;
        while (b--)
        {
            a = inPos();
            pos = 0;
            for (i=0; i<168; i++)
            {
                q = 0;
                while (a%p[i]==0)
                {
                    pos = i;
                    q++;
                    a = a/p[i];
                }
                if (q>ans[i])
                    ans[i] = q;
                if (a==1)
                    break;
            }
            if (pos>max)
                max = pos;
            if (a!=1)
                w[v++] = a;
        }
        qsort(w, v, sizeof(int), cmp);
        for (i=0; i<=max; i++)
            count += ans[i];
        for (i=0; i<v; i++)
        {
            count++;
            while (w[i]==w[i+1])
                i++;
        }
        printf("%d\n", count);
    }
    return 0;
} 

Chef and easy problem 2 CodeChef Solution in JAVA


import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import static java.lang.System.out;
 class CodeChef{
   
    
    
    static HashMap<Integer,Integer> map=new HashMap<>();
    
    public static void main(String[] args) {
        
        
        Scanner scanner=new Scanner(System.in);
        int T=scanner.nextInt();
        while(T-->0){
            int n=scanner.nextInt();
            int data[]=new int[n];
            for(int i=0;i<n;i++)
                data[i]=scanner.nextInt();
            
            for(int i:data){
                
                for(int j=2;j*j<=i;j++){
                    int count=0;
                    while(i%j==0){
                        count++;
                        i=i/j;
                    }
                  if(count>0){
                      if(map.containsKey(j)) map.put(j,Math.max(map.get(j),count));
                      else map.put(j,count);
                  }
                }
                if(i>1)  if(!map.containsKey(i)) map.put(i,1); 
                
            }
            
            int result=0;
            for(Map.Entry<Integer,Integer> entry:map.entrySet())
                result+=entry.getValue();
            
            out.println(result);
            map.clear();
            
            
        }
        
        
        
    }
}

Chef and easy problem 2 CodeChef Solution in PYPY 3

from collections import defaultdict
a = [True] * 1000100
def primes_sieve2(limit):
    a[0] = a[1] = False
    l=[]
    for (i, isprime) in enumerate(a):
        if isprime:
            l.append(i)
            for n in range(i*i, limit, i):
                a[n] = False
    return l
prime=primes_sieve2(1000100)
fac=[[] for i in range(1000100)]
for i in prime:
    for j in range(i,1000100,i):
        fac[j].append(i)
def get(divisors):
    div=fac[divisors]
    new=defaultdict(int)
    tar=divisors;ind=0;
    while(tar>1):
        fir=div[ind]
        while(tar>1 and tar%fir==0):
            tar//=fir;
            new[fir]+=1
        ind+=1
    return new
for _ in range(int(input())):
    n=int(input())
    lis=[int(i) for i in input().split()]
    vis=defaultdict(list);it=0
    for i in lis:
        for i,j in get(i).items():
            vis[i].append(j)
    for j in vis.values():
        it+=max(j)
    print(it)

Chef and easy problem 2 CodeChef Solution in PYTH

# cook your code here
bound = 10 ** 6
prime = [[] for _ in xrange(bound+1)] 
for i in range(2, bound+1):
    if not prime[i]:
        for j in xrange(i, bound+1, i):
            prime[j].append(i) 
            
from collections import defaultdict as ddict
t = int(raw_input())
while t:
    t -= 1 
    distinct = ddict(int)
    n = int(raw_input())
    s = map(int, raw_input().split()) 
    for i in s:
        
        for p in prime[i]:
            cnt = 0
            while i % p == 0:
                i //= p 
                cnt += 1 
            distinct[p] = max(distinct[p], cnt)
        
            
    
    r = 0 
    for i in distinct:
        r += distinct[i]
    print r
    
            

Chef and easy problem 2 CodeChef Solution in C#

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;

namespace Practise
{
    class Program
    {
        public static void Main()
        {
            const int MAX_LIMIT = 1000;
            int T = MyReader.ReadInt();
            List<int> PrimeNumbers = Utility.GetPrimes(MAX_LIMIT);

            // This is precalculated for prime numbers below 1000
            int totalPrimes = PrimeNumbers.Count;

            while (T-- > 0)
            {
                int N = MyReader.ReadInt();
                int[] numbers = MyReader.ReadAndSplitInt();

                int[] primeHash = new int[totalPrimes];
                for (int i = 0; i < N; i++)
                {
                    int[] tempHash = new int[totalPrimes];
                    for (int j = 0; j < totalPrimes && numbers[i] > 1; j++)
                    {
                        while (numbers[i] % PrimeNumbers[j] == 0)
                        {
                            tempHash[j] += 1;
                            numbers[i] = numbers[i] / PrimeNumbers[j];
                        }
                    }

                    for (int j = 0; j < totalPrimes; j++)
                    {
                        primeHash[j] = Math.Max(primeHash[j], tempHash[j]);
                    }
                }

                int totalCount = 0;
                for (int i = 0; i < totalPrimes; i++)
                {
                    totalCount += primeHash[i];
                }

                // Perform a second pass for primes > 1000
                HashSet<int> used = new HashSet<int>();
                for (int i = 0; i < N; i++)
                {
                    if (numbers[i] == 1 || used.Contains(numbers[i]))
                        continue;

                    totalCount++;
                    used.Add(numbers[i]);
                }

                Console.WriteLine(totalCount);
            }
        }
    }

    class MyReader
    {
        public static int ReadInt()
        {
            return Convert.ToInt32(Console.ReadLine());
        }

        public static long ReadLong()
        {
            return Convert.ToInt32(Console.ReadLine());
        }

        public static void SplitTwoInt(out int a, out int b)
        {
            int[] ret = ReadAndSplitInt();
            a = ret[0];
            b = ret[1];
        }

        public static void SplitThreeInt(out int a, out int b, out int c)
        {
            int[] ret = ReadAndSplitInt();
            a = ret[0];
            b = ret[1];
            c = ret[2];
        }

        public static int[] ReadAndSplitInt()
        {
            String[] input = Console.ReadLine().Split();
            int count = input.Length;
            int[] a = new int[count];
            for (int i = 0; i < count; i++)
            {
                a[i] = Convert.ToInt32(input[i]);
            }
            return a;
        }
    }

    class Utility
    {
        public static List<int> GetPrimes(int limit)
        {
            bool[] isPrime = GeneratePrimes(limit);
            List<int> primes = new List<int>();

            for (int i = 2; i <= limit; i++)
            {
                if (isPrime[i])
                    primes.Add(i);
            }

            return primes;
        }

        public static bool[] GeneratePrimes(int limit)
        {
            bool[] isPrime = new bool[limit+1];
            for (int i = 2; i <= limit; i++)
                isPrime[i] = true;

            for (int i = 2; i <= limit; i++)
            {
                if (isPrime[i])
                {
                    int j = 2;
                    while (i * j <= limit)
                    {
                        isPrime[i * j] = false;
                        j++;
                    }
                }
            }

            return isPrime;
        }
    }
}
Chef and easy problem 2 CodeChef Solution Review:

In our experience, we suggest you solve this Chef and easy problem 2 CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Chef and easy problem 2 CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Chef and easy problem 2 CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *