Find pairs in two arrays such that when multiplied becomes a perfect square

Question

Given two integer arrays like this:-

int[] a = { 2, 6, 10, 13, 17,18 };
int[] b = { 3, 7, 8, 9, 11, 15 };

How can I find pairs from these two arrays such that when multiplied they become perfect square?

For eg, in above arrays {2,8} & {18,8} are two pairs.

Right now my approach is brute-force, where I am looping through both arrays like this:-

int count = 0;
for (int i = 0; i < arr1.Length; i++)
{
    for (int j = 0; j < arr2.Length; j++)
    {
         var x = arr1[i] * arr2[j];
         long s = (long)Math.Sqrt(x);
         if (x == s * s)
               count += 1;                   
     }
}

How can I do this efficiently?

This seems more an exam/competition, but we will try to help because you provided a code... — matiaslauriti, May 19 '17 at 14:54
@matiaslauriti - Correct, interview question. I am bad in algorithms being from a non-CS background :( — Rahul Singh, May 19 '17 at 14:56
I wouldn't use the `Math.Sqrt()` method for determining the "perfect squareness". Please look at [this](http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer) question. There's a good answer explaining a fast method. It's java however, but it shouldn't be a problem to move it in the C# world. — dymanoid, May 19 '17 at 14:58

גלעד ברקן · Accepted Answer · 2017-05-21T13:18:06.770

7

Any two numbers where the count of each prime factor in the number is even, would form a valid pair. Otherwise, any number with an odd count of one or more prime factors could only pair with another number with the exact same factors having an odd count. This means all we would need to store for each number is which of its prime factors have an odd count. This could be hashed.

a = { 2, 6, 10, 13, 17,18 }; 
b = { 3, 7, 8, 9, 11, 15 };

Hash the shorter array where the key is the combination of prime factors with odd count and the value is the corresponding list of indexes in the array:

a = {
  2: [0,5],
  2-3: [1], 
  2-5: [2], 
  13: [3],
  17: [4]
}

Traverse the second array and exactly match the prime-factor-with-odd-count-combination:

b[0] -> 3, no match
b[1] -> 7, no match
b[2] -> 2, match with a[0] and a[5] -> 2 * 8 and 18 * 8 are perfect squares
b[3] -> None, no match
b[4] -> 11, no match
b[5] -> 3-5, no match

edited May 21 '17 at 13:18

answered May 19 '17 at 15:03

גלעד ברקן

23,602
3
25
61

@RahulSingh for counting prime factors or what to do with the hash after? – גלעד ברקן May 19 '17 at 15:43
Counting prime factors can be done with a modified sieve of Eratosthenes. – maraca May 19 '17 at 17:05
@גלעדברקן -If possible, nd need to understand logic with example (maybe with the arrays which I have shared). – Rahul Singh May 21 '17 at 07:45
@RahulSingh added an example. – גלעד ברקן May 21 '17 at 13:13
@RahulSingh ehrm I added the code for it already a day ago and upvoted this answer. This hides some of the complexity like how to factorize each number? – maraca May 21 '17 at 13:17
Don't need to hash the counts. Take the square factors out of each number and then just look for matches. – Matt Timmermans Feb 14 '20 at 13:51

maraca · Answer 2 · 2017-05-21T13:31:13.077

For ordered (only matters for the detection of the max) arrays with integers > 0 with the help of a modified sieve of Eratosthenes, I think the complexity is O(max * log(max) * log(log(max)) + n) and there is O(max) extra space required (which can be a huge improvement or very bad depending on n and max compared to the standard O(n^2) with O(1) space and no dependency on max):

long total = 0;
int max = (a[a.length - 1] > b[b.length - 1] ? a[a.length - 1] : b[b.length - 1]) + 1;
int[] sieve = new int[max], anti = new int[max], count = new int[max];
for (int i = 1; i < max; i++) {
    sieve[i] = i; // using numbers and divide by prime instead of booleans
    anti[i] = 1; // number by which i has to be multiplied to get the smallest square
}
for (int i = 2; i < max; i++) {
    if (sieve[i] == i) { // i is prime
        for (int j = i; j < max; j += i) {
            boolean odd = false;
            do {
                odd = !odd;
                sieve[j] /= i;
            } while (sieve[j] % i == 0);
            if (odd)
                anti[j] *= i;
        }
    } // if you know the max over all the calls the above has only to be done once
} // except for resetting count and total, so we would get O(n) because max is constant
for (int i = 0; i < a.length; i++)
    count[anti[a[i]]]++; // hash map for count is better than array if n < max
for (int i = 0; i < b.length; i++)
    total += count[anti[b[i]]];

A square number will be mapped to 1 and others to the product of primes with odd exponents in the factorization of the number. In your example every number is mapped to itself except for 8 => 2, 9 => 1, 18 => 2. Other interesting numbers below 18 (not square or mapping to itself): 12 => 3. When iterating over a the algorithm increases the count of 2 once when visiting 2 and once when visiting 18. The total will be increased by 2 when the iteration over b visits 8, the only matches between the two arrays and therefore the end result.

Thanks for the explanation. – Rahul Singh May 21 '17 at 18:35 — Rahul Singh, May 21 '17 at 18:35

score 0 · Answer 3 · answered May 19 '17 at 14:57

0

I managed to simplify it using LINQ:

int[] arr1 = { 2, 6, 10, 13, 17, 18 };
int[] arr2 = { 3, 7, 8, 9, 11, 15 };
int count = arr1.Sum(t => (from t1 in arr2 select t*t1 into x let s = (long) Math.Sqrt(x) where x == s*s select x).Count());

answered May 19 '17 at 14:57

ThePerplexedOne

2,920
15
30

If he is in an interview and he is not used to C#, then, this answers is useless for him, but good point with LINQ – matiaslauriti May 19 '17 at 14:58
6

All you have done is converted the two loops into a _Linq_ query. It is still inefficient cz we are looping through every element. – Rahul Singh May 19 '17 at 15:00
You're using arrays, of course there's going to be iteration. You can't really avoid it. – ThePerplexedOne May 19 '17 at 15:02
linq is not necessarily a simplification. It strongly depends on the point of view what is seen as simple – Mong Zhu May 20 '17 at 22:24

score 0 · Answer 4 · answered May 19 '17 at 15:05

0

I would check whether you have any decimal place after drawing the root left. If not then you have your perfect squareroot:

void Main()
{
    int[] arr1 = { 2, 6, 10, 13, 17, 18 };
    int[] arr2 = { 3, 7, 8, 9, 11, 15 };

    List<string> PairList = new List<string>();

    for (int i = 0; i < arr1.Length; i++)
    {
        for (int j = 0; j < arr2.Length; j++)
        {
            if (Math.Sqrt(arr1[i] * arr2[j]) % 1 == 0)
            {
                PairList.Add(String.Format("{0} & {1}", arr1[i] , arr2[j]));
            }           
        }
    }

    PairList.Dump();
}

answered May 19 '17 at 15:05

Mong Zhu

23,309
10
44
76

Still it is `O(n*n)` – Rahul Singh May 19 '17 at 15:06
are you sure that you sholdn't use < Double.Epsilon instead of equality? – Dmitry Pavlushin May 19 '17 at 15:06
@DmitryPavlushin thanx for pointing this out. But does it make a big difference? – Mong Zhu May 20 '17 at 22:22
@RahulSingh that is true it is still a horrible runtime. – Mong Zhu May 20 '17 at 22:22

Find pairs in two arrays such that when multiplied becomes a perfect square

4 Answers4

Linked

Related