Company: Salesforce SDE_23april
Difficulty: medium
Salesforce uses an array of lead scores, leadScores , to prioritize potential clients. Each lead score is a positive integer representing the potential value of a lead. In some cases, the lead scores need to be optimized by splitting them into more granular scores for better prioritization. Given an array leadScores of n positive integers, the following operation can be performed 0 or more times: Select a lead score at index i where 0 ≤ i < n . Choose any two integers, x and y , such that x + y = leadScores[i] . Replace leadScores[i] with two new scores, x and y . The task is to determine the minimum number of operations required to sort the leadScores array in ascending order. Example n = 3 leadScores = [3, 4, 3] The array can be sorted in 2 operations: Select i = 0, leadScores[0] = 3. Choose x = 1, y = 2, leadScores' = [1, 2, 4, 3] . Select i = 2, leadScores[2] = 4. Choose x = 2, y = 2, leadScores' = [1, 2, 2, 2, 3] . Constraints 1 ≤ n ≤ 10 5 1 ≤ leadScores[i] ≤ 10