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!!