Hello codeforces!!

Recently I was attempting an hiring test and came across the following problem which I could not solve. Could anybody help me in solving this problem?

You are given a special type of array — an expanding array. An expanding array is an array which has only distinct elements and keep expanding based on the following process:

• Pick any 2 integers (A and B, A > B) randomly from the existing expanding array. If integer part of A / B (lets call it Z) is not present in the array, we expand our original expanding array and add Z to it.

Keep repeating above operation until array cannnot be extended further. Find the final size of expanding array.

Constraints: Array size <= 500, each array element Arr[i]: 1<=Arr[i]<=1000.

Example: I/P : Arr = [9, 4], O/P : 3, Final expanding array is :[9,4,2].

Thanks in advance!!

Hi all!!

Could anybody help me solving following problem:

We are given a list of N unsorted elements, we need to find minimum number of addition operations in which the elements of the array can be added to make all the elements greater than or equal to K. We are allowed to add two elements together and make them one.e.g.

arr[]={1 10 12 9 2 3}, k=6 => Output=2

 arr[]={1 2 3 4 5 6}, k=7 => output=3

Constraints:

1<=n,k<=1e5

1<=arr[i]<=1e6

Thanks in advance!!

Hello all, Recently I was attempting the following problem: Given an array of integers, arr. Find sum of floor of (arr[i]/arr[j]) for all pairs of indices (i,j).

e.g. arr[]={1,2,3,4,5}, Sum=27.

I could only think of naive O(n^2) solution. Is there any other better approach?

Thanks in advance.

Hi all,

Recently I was solving problem Sad Powers. In the editorial of the problem it is mentioned that sqrt() function of c++ has some precision issues. On using the function in my problem on some value gives me wrong answer. After looking others solution I observed that some have used additional checks. e.g. If square root of value x is required then many solutions have checked for both x and (x-1) /(x+1). I could not understand why that additional check is required.

Can anybody please tell why this additional check is required or what are the issues with sqrt() function?

Thanks!!