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 <bits/stdc++.h>

#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