<\/strong><\/u><\/a><\/p>\n\nInput:\n1\n3\n4 2 6\n\nOutput:\n2\n0 8\n\nExplanation:\nIn the given array,\nIf we introduce 0, the array becomes [0, 2, 4, 6] which is an Arithmetic Progression with common difference 2.\nIf we introduce 8, the array becomes [2, 4, 6, 8] which is an Arithmetic Progression with common difference 2.\nSo, we print 2, because there are two such numbers, also we print 0 and 8 because they're required numbers.<\/code><\/pre>\nSolving Approach :<\/h3>\n
Bruteforce Approach<\/strong>:
\n1) We sort the array and introduce numbers one by one. After adding one number, we check if the current formed sequence is Arithmetic Progression or not. If yes, increase the count and print the note the added number.
\n2) After the whole array is traversed for adding the number, we print the count and print all the numbers noted in a row.
\n3) This approach takes O(n*log(n))<\/code> for sorting array using merge sort, also O(n+1)<\/code> to add numbers. This takes O(n)<\/code> for checking if the current sequence is Arithmetic Progression or not for every addition. Hence total time complexity of this approach is O(n*log(n) + n2<\/sup>). This approach takes longer times to process a large number of queries, so we move to a new efficient approach.<\/p>\nEfficient Approach:<\/p>\n
\n- As we know Arithmetic Progression is always increasing or decreasing, so we sort the array so that it can be arranged in an increasing sequence.<\/li>\n
- If the array contains only a
single element<\/code>, it is already an Arithmetic Progression, so no further elements are required to make it Arithmetic Progression.<\/li>\n- If the array contains only
2 elements<\/code>, there can be three possibilities :\n\n- A number can be added in front, where the common difference between the number and the first element is the same as the difference between array elements.<\/li>\n
- A number can be added in last, where the common difference between the number and last element is the same as the difference between array elements.<\/li>\n
- A number can be added in middle, that would be the average of two elements in the array, where the sum of both elements must be even.<\/li>\n<\/ul>\n<\/li>\n
- If the array contains more than 2 elements, the following cases, can arise :\n
\n- CASE-1:<\/em><\/strong> If the current array is already an Arithmetic Progression, we can add numbers in the last and first position as we discussed in point 2. Here no middle element is added.<\/li>\n
- CASE-2:<\/em><\/strong> If the array is not an Arithmetic Progression, we calculate all possible common differences, and see for these cases :\n
\n- If there are more than 2 common differences, there is no way to convert the current array into Arithmetic Progression by adding a number.<\/li>\n
- If there are two common difference, where both appears multiple times in sequence (multiple elements have them as common difference), then there is no possible way to convert the current array into an Arithmetic Progression.<\/li>\n
- If there appears a common difference which is present only once, and other common difference appears the rest of the times. Let’s say multiple elements have
a<\/code> as common difference and there exist two elements whose difference is b<\/code>. We can convert current sequence into an arithmetic progression only and only if b<\/code> is double of a<\/code> (2b = a), hence a number can be added between elements having common difference b<\/code>, and number would be A[k]+a<\/code> or A[k+1]-a<\/code> where A[k+1]-A[k] = b.<\/li>\n<\/ol>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\nSolutions<\/h3>\n
\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645094862897-Article_249.png\")
<\/p>\n