CVCE002 - Editorial

editorial
, ,
1

PROBLEM LINK

Forgetful Sally - Practice

Author: Muneeb Hussaini
Testers: Srilekhya, Chitturi Sai Suman
Editorialist: Muneeb Hussaini

DIFFICULTY

Easy

PREREQUISITES

None

PROBLEM

Sally has amnesia and only remembers a few prime numbers (may contain 0 and 1 as well). She wants to know whether a given number x can be represented as a product of only the prime numbers she knows. Output YES if x can be represented, NO otherwise.

QUICK EXPLANATION

Given an array of prime numbers and a number x, the array is traversed and x is divided and updated by each number it is divisible by until no such number remains. If the resulting x is 1 then output YES, else NO.

EXPLANATION

Given an array a containing n prime numbers [a_0, a_2, a_3, a_{n - 1}] (may include 0 or 1) and an integer x.
The first step is to handle edge cases.

  • Edge Case 1: x = 0
    If x is 0 then it can be expressed using the given array if and only if the array contains 0. Output YES if 0 is found in a and NO otherwise.
  • Edge Case 2: x = 1
    Likewise, if x is 1 then it can be expressed using the given array if and only if the array contains 1. Output YES if 1 is found in a and NO otherwise.

Once the edge cases are solved, the problem becomes simpler.
x can be represented as a product of the array of prime numbers iff all of the divisors of x are found in the array.
In other words, all of x's prime factors must be present in the array.

One way to solve this is to simply find all the factors of x and store them in a set F. Consider A as set of a. Now, x can be represented using array integers iff F is a subset of A.

The above solution requires iterating over the set \{i\mid\ x\ \%\ i = =0\}, checking if they are prime and then storing them in a set.

A more efficient solution would be to simply divide x by each a_i in a provided x is divisible by a_i.

  • The array a is traversed using i.
  • If x is divisible by a_i then it is divided by a_i and updated i.e. x = \cfrac{x}{a_i}.
  • Above step is repeated as long as x is divisible by a_i.
  • Once or if x is not divisible by a_i, i is incremented and the array is further traversed.
    Once the above steps take place, the x obtained gives us the output. If x is 1 then all of its prime divisors are present in the array and output is given as YES. If x is not 1 then output is given as NO.

SOLUTIONS

Setter's Solution 
def func():
    x, m = map(int, input().split()) #x is number, m is array length
    a = [int(x) for x in input().split()] #array with factors
    if x == 1 and 1 in a:
        return "YES"
    if x == 0 and 0 in a:
        return "YES"
    if x == 0 or x == 1:
        return "NO"
    while 0 in a:
        a.remove(0) #division by zero not possible
    while 1 in a:
        a.remove(1) #1 is a factor for every number
    for i in a:
        while(x % i == 0): #x is divided by each factor until it is no longer divisible by it
            x //= i
        if (x == 1): #if x = 1 then it can be represented as a product of given factors
            return "YES"
    return "NO"
 
n = int(input()) #number of test cases
for i in range(n):
    print(func())
3 Likes