### nik1996's blog

By nik1996, 4 years ago, 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].

By nik1996, 5 years ago, 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

By nik1996, 5 years ago, 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?

By nik1996, history, 5 years ago,  c++,