Problem : Sherlock and the Perfect array
Difficulty :
Easy, Ad-hoc
Pre-requisites :
Simple Math
Problem :
Given an array A of size N and a number K, one operation is defined: Select any two distinct indices i and j and replace A[i] or A[j] by the product A[i]*A[j].
A pair (x,y) is said to be perfect if either x > K or y > K.
Find the minimum number of operations needed to make every possible pair in the array A perfect.
If it is not possible to make every pair perfect, then print -1.
Explanation :
Every pair in an array will become perfect if any N-1 numbers become greater than K. Sort the array and check whether largest number is greater than K or not.
If yes, then check from 2nd element in array(we can skip 1st (smallest) number because we are concerned only for N-1 numbers) and see whether ith number is greater than K or not and if it is not, apply defined operation on it i.e replace ith element with product of largest number and ith number. However if largest number is less than or equal to K, then apply the operation on Largest and Second Largest number till one number becomes greater than K. Now apply the same technique as previous.
However, There are many boundary cases you need to consider. Notice that if any two numbers in an array are 0, then answer is always -1.
Also when any one number is 0 and rest others are 1, then if K = 0 then answer will be 0 else answer will be -1.
Similarly, if all numbers are equal to 1 then if K = 0 then answer is 0 alse answer is -1.
Also when N = 2, the above cases need to be judged seperately.
Author’s Solution can be found here