# Check whether for all pair (X, Y) of given Array floor of X/Y is also present

Last Updated : 24 Mar, 2023

Given an array arr[] of size N and an integer K, denoting the maximum value an array element can have, the task is to check if for all possible pairs of elements (X, Y) where Xâ‰¥Y, âŒŠX/YâŒ‹ (X divided by Y with rounding down) is also present in this array.

Examples:

Input: N = 3, K = 5, arr[]={1, 2, 5}
Output: YES
Explanation: There are such pair of elements (checking all possible conditions)
âŒŠ1/1âŒ‹ = 1,  âŒŠ2/2âŒ‹ = 1, âŒŠ5/5âŒ‹ = 1
âŒŠ2/1âŒ‹ = 2, âŒŠ5/1âŒ‹ = 5, âŒŠ5/2âŒ‹ = 2
As all [X/Y] for any X and Y exists in the array. So print YES

Input: N = 4, K = 8, arr[] = {1, 3, 3, 7}
Output: NO
Explanation: As there is a pair (7, 3) where âŒŠ7/3âŒ‹ = 2 is not present in the array.

Naive Approach: A naive approach for this problem is to use nested loops and take every value for X and Y and store in a resultant array. Then later on check every element of the resultant array is present or not in the original array.

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

Efficient Approach: This problem can be solved on the basis of the following idea:

For any number x all the values in range c*x + d [where c is a positive integer and d is in range [0, x) ] will have the same floor value c when divided by x

To implement the above observation, use a map to store the elements present in the array and a prefix array to store how many elements are present till x (x in the range [1, K]). For every such x check in its multiples if such a c (as mentioned in the observation ) exists in the array using the map and the prefix sum array.

Follow the below steps to solve this problem:

• Use a hash array (say b[]) to store the elements present in the array and another prefix sum array(say a[]) as mentioned above.
• Iterate in the array b[] for i > 0 to K:
• If i is present in array arr[]:
• Check for multiples of i (say x) if the floor value of x/i is also present in the array using b[](because of the reason mentioned in observation).
• If not present then check from the prefix sum array if any element was present in the range (x-i, x]
• If present then the condition for i and that element is not satisfied. So return false. Otherwise, continue iteration.
• Otherwise, continue for the next values of i
• If all possible values are present, return true.

Follow the illustration below for a better understanding

Illustration:

Consider arr[] = {1, 2, 5}, K = 5

b[] = {0, 1, 1, 0, 0, 1} [denotes 1, 2 and 5 are present]
a[] = {0, 1, 2, 2, 2, 5} [denotes how many element till i is present]

Traverse b[] from i = 1 to 5

For i = 1:
=> Multiple = 1. 1/1 = 1. b[1] = 1, So this is present.
=> Multiple = 2. 2/1 = 2. b[2] = 1, So this is present.
=> Multiple = 3. 3/1 = 3. b[3] = 0, No element in range (2, 3].
=> Multiple = 4. 4/1 = 4. b[4] = 0, No element in range (3, 4].
=> Multiple = 5. 5/1 = 5. b[5] = 1, So this is present.

For i = 2:
=> Multiple = 1. 2/2 = 1. b[1] = 1, So this is present.
=> Multiple = 4. 4/2 = 2. b[2] = 1, So this is present.

For i = 3:
=> 3 is not present in the array. So continue iteration.

For i = 4:
=> 4 is not present in the array. So continue iteration.

For i = 5:
=> Multiple = 5. 5/5 = 5. b[1] = 1, So this is present.

So all possible elements are present for all possible pairs.

Below is the implementation of the above approach:

## C++

 `// C++ code to implement the above approach ` ` `  `#include ` `using` `namespace` `std; ` ` `  `// Function to check whether X/Y is present or not ` `int` `solve(``int` `n, ``int` `c, ``int` `arr[]) ` `{ ` `    ``// Creating hash array ` `    ``// and prefix sum array ` `    ``vector<``int``> a(c + 1, 0), b(c + 1, 0); ` `    ``for` `(``int` `i = 0; i < n; i++) { ` `        ``a[arr[i]]++; ` `        ``b[arr[i]]++; ` `    ``} ` ` `  `    ``// Performing prefix sum. ` `    ``for` `(``int` `i = 1; i <= c; i++) { ` `        ``a[i] += a[i - 1]; ` `    ``} ` `    ``for` `(``int` `i = 1; i <= c; i++) { ` ` `  `        ``// Taking original array elements ` `        ``if` `(b[i] > 0) { ` `            ``for` `(``int` `j = i - 1; j <= c; j += i) { ` ` `  `                ``// If element already exist ` `                ``// it will give 1 hence true case ` `                ``// if doesnt exist ` `                ``// we will move forward ` `                ``if` `(b[(j + 1) / i] == 0) { ` ` `  `                    ``// we will take two indices ` `                    ``// to check  whether item ` `                    ``// is present. ` `                    ``// If any element is present ` `                    ``// between then a[id1]!=ad[id2] ` `                    ``int` `id1 = j; ` `                    ``int` `id2 = j + i; ` `                    ``id2 = min(id2, c); ` `                    ``if` `(a[id1] != a[id2]) { ` `                        ``return` `false``; ` `                    ``} ` `                ``} ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// If all above cases turns true ` `    ``return` `true``; ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``int` `N = 3, K = 5; ` `    ``int` `arr[] = { 1, 2, 5 }; ` `    ``bool` `flag = solve(N, K, arr); ` `    ``if` `(flag) ` `        ``cout << ``"Yes"``; ` `    ``else` `        ``cout << ``"No"``; ` `    ``return` `0; ` `}`

## Java

 `// Java code to implement the above approach ` ` `  `import` `java.io.*; ` ` `  `class` `GFG { ` ` `  `    ``// Function to check whether X/Y is present or not ` `    ``static` `boolean` `solve(``int` `n, ``int` `c, ``int` `arr[]) ` `    ``{ ` `        ``// Creating hash array ` `        ``// and prefix sum array ` `        ``int``[] a = ``new` `int``; ` `        ``int``[] b = ``new` `int``; ` `        ``for` `(``int` `i = ``0``; i < n; i++) { ` `            ``a[arr[i]]++; ` `            ``b[arr[i]]++; ` `        ``} ` ` `  `        ``// Performing prefix sum. ` `        ``for` `(``int` `i = ``1``; i <= c; i++) { ` `            ``a[i] += a[i - ``1``]; ` `        ``} ` `        ``for` `(``int` `i = ``1``; i <= c; i++) { ` ` `  `            ``// Taking original array elements ` `            ``if` `(b[i] > ``0``) { ` `                ``for` `(``int` `j = i - ``1``; j <= c; j += i) { ` ` `  `                    ``// If element already exist ` `                    ``// it will give 1 hence true case ` `                    ``// if doesnt exist ` `                    ``// we will move forward ` `                    ``if` `(b[(j + ``1``) / i] == ``0``) { ` ` `  `                        ``// we will take two indices ` `                        ``// to check  whether item ` `                        ``// is present. ` `                        ``// If any element is present ` `                        ``// between then a[id1]!=ad[id2] ` `                        ``int` `id1 = j; ` `                        ``int` `id2 = j + i; ` `                        ``id2 = Math.min(id2, c); ` `                        ``if` `(a[id1] != a[id2]) { ` `                            ``return` `false``; ` `                        ``} ` `                    ``} ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``// If all above cases turns true ` `        ``return` `true``; ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `N = ``3``, K = ``5``; ` `        ``int` `arr[] = { ``1``, ``2``, ``5` `}; ` `        ``boolean` `flag = solve(N, K, arr); ` `        ``if` `(flag) ` `            ``System.out.println(``"Yes"``); ` `        ``else` `            ``System.out.println(``"No"``); ` `    ``} ` `} ` ` `  `// This code is contributed by hrithikgarg03188.`

## Python3

 `# Python code to implement the above approach ` ` `  `# Function to check whether X / Y is present or not ` `def` `solve(n, c, arr): ` `   `  `    ``# Creating hash array ` `    ``# and prefix sum array ` `    ``a ``=` `[] ` `    ``b ``=` `[] ` `    ``a ``=` `[``0` `for` `i ``in` `range``(c ``+` `1``)] ` `    ``b ``=` `[``0` `for` `i ``in` `range``(c ``+` `1``)] ` `    ``for` `i ``in` `range``(``0``, n): ` `        ``a[arr[i]] ``+``=` `1` `        ``b[arr[i]] ``+``=` `1` ` `  `    ``# Performing prefix sum. ` `    ``for` `i ``in` `range``(``0``, c ``+` `1``): ` `        ``a[i] ``+``=` `a[i ``-` `1``] ` ` `  `    ``for` `i ``in` `range``(``0``, c ``+` `1``): ` `       `  `        ``# Taking original array elements ` `        ``if` `b[i] > ``0``: ` `            ``for` `j ``in` `range``(i ``-` `1``, c ``+` `1``, i): ` `               `  `                ``# If element already exist ` `                ``# it will give 1 hence true case ` `                ``# if doesnt exist ` `                ``# we will move forward ` `                ``if` `b[(j ``+` `1``) ``/` `i] ``=``=` `0``: ` `                   `  `                    ``# we will take two indices ` `                    ``# to check  whether item ` `                    ``# is present. ` `                    ``# If any element is present ` `                    ``# between then a[id1]!= ad[id2] ` `                    ``id1 ``=` `j ` `                    ``id2 ``=` `j ``+` `i ` `                    ``id2 ``=` `min``(id2, c) ` `                    ``if` `a[id1] !``=` `a[id2]: ` `                        ``return` `False` `        ``# If all above cases turns true ` `        ``return` `True` ` `  `# Driver Code ` `if` `__name__ ``=``=` `"__main__"``: ` `    ``N ``=` `3` `    ``K ``=` `5` `    ``arr ``=` `[``1``, ``2``, ``5``] ` `    ``flag ``=` `solve(N, K, arr) ` `    ``if` `(flag ``=``=` `True``): ` `        ``print``(``"Yes"``) ` `    ``else``: ` `        ``print``(``"No"``) ` ` `  `# This code is contributed by Rohit Pradhan`

## C#

 `// C# code to implement the above approach ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Function to check whether X/Y is present or not ` `    ``static` `bool` `solve(``int` `n, ``int` `c, ``int``[] arr) ` `    ``{ ` `        ``// Creating hash array ` `        ``// and prefix sum array ` `        ``int``[] a = ``new` `int``; ` `        ``int``[] b = ``new` `int``; ` `        ``for` `(``int` `i = 0; i < n; i++) { ` `            ``a[arr[i]]++; ` `            ``b[arr[i]]++; ` `        ``} ` ` `  `        ``// Performing prefix sum. ` `        ``for` `(``int` `i = 1; i <= c; i++) { ` `            ``a[i] += a[i - 1]; ` `        ``} ` `        ``for` `(``int` `i = 1; i <= c; i++) { ` ` `  `            ``// Taking original array elements ` `            ``if` `(b[i] > 0) { ` `                ``for` `(``int` `j = i - 1; j <= c; j += i) { ` ` `  `                    ``// If element already exist ` `                    ``// it will give 1 hence true case ` `                    ``// if doesnt exist ` `                    ``// we will move forward ` `                    ``if` `(b[(j + 1) / i] == 0) { ` ` `  `                        ``// we will take two indices ` `                        ``// to check  whether item ` `                        ``// is present. ` `                        ``// If any element is present ` `                        ``// between then a[id1]!=ad[id2] ` `                        ``int` `id1 = j; ` `                        ``int` `id2 = j + i; ` `                        ``id2 = Math.Min(id2, c); ` `                        ``if` `(a[id1] != a[id2]) { ` `                            ``return` `false``; ` `                        ``} ` `                    ``} ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``// If all above cases turns true ` `        ``return` `true``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `N = 3, K = 5; ` `        ``int``[] arr = { 1, 2, 5 }; ` `        ``bool` `flag = solve(N, K, arr); ` `        ``if` `(flag) ` `            ``Console.Write(``"Yes"``); ` `        ``else` `            ``Console.Write(``"No"``); ` `    ``} ` `} ` ` `  `// This code is contributed by sanjoy_62.`

## Javascript

 ``

Output

`Yes`

Time Complexity : O(K * LogK)
Auxiliary Space: O(K)

Previous
Next
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}