Entering edit mode

Omega Primes

Carl is bored of playing with ordinary prime numbers . Thus he comes up woth pecial numbers called Omega Primes. A number X is called Omega Prime , if there exists no perfect square Y (Y>1) such that Y divides X

For example 6 is an Omega Prime because there is no perfect square 1 that divides 6 . On the other hand ,12 is not Omega Prime as 4 (which is a perfect square ) is divisor of 12

Carl decides to play a bot more with Omga primes . He has an Array A of integers . Carl wants to find the number of different subsets such that the product of elements for each subset , results in an Omega Prime . Help Carl find this number .

since this number can be large , output the answer modulo 10^9 + 7

Problem Constraints

1<= Length of A <= 2 * 10 ^4

1 <= A[i] <= 30

Input

The first argument is the integer array A

Output

Return an integer denoting the number of dieffernt desired subsets modulo 10^9 + 7

Input 1:

A = [2,4,3]

Input 2

A= [2 ,2, 2]

Example Output

Output 1 :

Output 2:

Explanation 1:

The different subsets are [0,2] , [0] , [2]. (the numbers denote the number of indcies n the array of elements )

Explanation 2:

The different subsets are : [0], [1] , [2]

Red Zone

There are people that believe that Earth is flat and NASA is a scam . They calll themselves flat earthers . They were already worried that the 6 foot social distancing rule might push some people out of earth.

Now they decided to think about a new issue , Since the Earth is flat. Lets imagine it as an 2D infinite grid .. They have the coordinates of certain points which are orange zones and have some COVID 19 cases reported . Now each day the orange zones have become more fatal . After d days , all the locations within a eucledian distance of d of a particular orange zone can be affected by this zone

They know N orange zones each of whose coordinates are given by (A[i][0] , A[i][1]). Now a location is considered a red zone if its affected by B orange zones .. You need to find the first day which the first red zone is reported .

Problem Constraints

2 <= B <= N <= 100

0<= A[i][0], A[i][1] <= 10^9

Input format

The first arguement contains a 2D array A of size N ., denoting the coordinates of the orange zones

The second arguement contains an integer B

Output Format

Return the ifrst day at whocch red zone is reported

Example Input

Input 1
[
    [8,5]
    [0,4]
    [3,6]
]
B:3

Input 2

A :
[
    [2,3]
    [9,4]
    [10,3]
]
B:2


Output 1
5

Output 2
1

Example Explanation

Explanation 1.
One of the red zones will be (5, 4) and it is within a distance of 5 from all the orange zones
Explanation 2:
one of the red cones will be (9, 3) C is within a distance of 1 from 2 orange cones.

Fractional Knapsack

Problem Description
You are inside Gringotts Gold Bank with a Knapsack that can hold B weight of Gold coins.
In the Gringotts bank, gold coins have some unique properties:
1. Each Gold coin has a weight equal to some non-negative power of 2.
2. Each Gold Coin can be further divided into two gold coins of equal weight.
There are N gold coins in the Bank, given by array A. where Ali] is the weight of the it gold coin.
You have to fill the knapsack completely, by making minimum number of divisions of the gold coins.
Calculate the minimum number of divisions needed to fill the knapsack completely.
Note: In case it is impossible to fill the knapsack completely, output -1.
Problem Constraints

1 <= N <= 10^5
1 <= B <= 10^18
1 <= A[i] <= 10^9

Input Format

The first argument given is an array. A
The second argument given is an integer, B.

Output Format

Return an integer denoting the minimum number of division that are required to fill the knapsack completely.
Example Input
Input 1:
A - [16, 1, 4, 1]
B = 23
Input 2:
A = [1, 32, 1]
B = 10

Output 1

-1

Output2

Example Explanation
Explanation 1:

It is impossible to fill the knapsack of weight 23

Explanation 2:
You can convert cold coin of weight 32 into gold coin of weight 8 with 2 divisions.
1.e. 32 -> 16 ÷ 16
16 -> 8 + 8.
And Now to fill the knapsack with weight 10
three gold coins with weight 1, 1