Select Page

# Check if Array can be generated where no element is Geometric mean of neighbours

Animesh Dey
Published: May 17, 2022

Given two integers P and N denoting the frequency of positive and negative values, the task is to check if you can construct an array using P positive elements and N negative elements having the same absolute value (i.e. if you use X, then negative integer will be -X) such that no element is the geometric mean of its neighbours.

Examples:

Input: P = 3, N = 2
Output: True
Explanation: it is possible to create an array : X, X, -X, -X, X

Input: P = 4, N = 0
Output: False

Approach: Below is the observation for the approach:

B is said to be the geometric mean of A and C if B2 = A*C.
Since B2 is always positive, So, either B = X or B = -X and B2 = X2 because X*X = X2 and (-X)*(-X) = X2.

Hence, the Predecessor and Successor have always opposite sign.
So the array will have a pattern like {X, X, -X, -X, X, X}

Based on the above observation the solution can be derived as:

• If the difference between P and N is greater than 2 then the above arrangement is not possible.
• If the difference is exactly 2 then:
• If they occur odd times each, the arrangement won’t be possible as there will be a segment like {X, -X, X} or {-X, X, -X}.
• Otherwise, the arrangement is possible
• If the difference is less than 2, then the arrangement is always possible.

Below is the implementation of the above approach:

## C++

 ` ` `#include ``#define ll long long``using` `namespace` `std;`` ` `bool` `checkGM(``int` `P, ``int` `N)``{``    ``    ``    ``if` `(``abs``(P - N) >= 3)``        ``return` `false``;``    ``if` `(``abs``(P - N) == 2) {``        ``if` `(P & 1)``            ``return` `false``;``        ``else``            ``return` `true``;``    ``}``    ``return` `true``;``}`` ` `int` `main()``{``    ``ll P = 3, N = 2;`` ` `    ``    ``bool` `ans = checkGM(P, N);``    ``if` `(ans)``        ``cout << ``"True"``;``    ``else``        ``cout << ``"False"``;``    ``return` `0;``}`

Time Complexity: O(1)
Auxiliary Space: O(1)

Source: www.geeksforgeeks.org