Number of Beautiful Pairs

This problem requires you to find all the pairs of indices in an array where the first digit of the number at the first index and the last digit of the number at the second index are coprime numbers. Coprime numbers are those where the greatest common divisor (gcd) is 1.

We can solve this problem by using two nested loops to go through all possible pairs of numbers in the array. For each pair, we extract the first digit of the number at the first index and the last digit of the number at the second index, then we calculate the gcd of these two numbers. If the gcd is 1, it means the pair is beautiful and we increase the counter of beautiful pairs.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import math
from typing import List

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        beautiful_pairs = 0
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                first_digit = int(str(nums[i])[0])
                last_digit = int(str(nums[j])[-1])
                if math.gcd(first_digit, last_digit) == 1:
                    beautiful_pairs += 1
        return beautiful_pairs

This function uses the math.gcd() function to calculate the gcd of the first digit of the number at the first index and the last digit of the number at the second index. If the gcd is 1, it increases the counter of beautiful pairs. It repeats this for all possible pairs of numbers in the array. After going through all the pairs, it returns the count of beautiful pairs.

The string conversion for first and last digits is done to handle the cases when the numbers have more than one digit. In Python, indexing a string with -1 gives the last character, and with 0 gives the first character. Thus, converting numbers to strings allows us to easily access the first and last digits.

Why do i get error AttributeError: ‘module’ object has no attribute ‘gcd’ in python?

The error message is indicating that Python cannot find the function gcd within the math module. This is likely because you’re using a Python version less than 3.5, as the math.gcd function was introduced in Python 3.5.

If upgrading Python to a newer version is not an option, you can implement your own gcd function, such as:

1
2
3
4
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Then you can use this function in your code instead of math.gcd.

So your Python code will become:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
from typing import List

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        beautiful_pairs = 0
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                first_digit = int(str(nums[i])[0])
                last_digit = int(str(nums[j])[-1])
                if self.gcd(first_digit, last_digit) == 1:
                    beautiful_pairs += 1
        return beautiful_pairs

    def gcd(self, a, b):
        while b != 0:
            a, b = b, a % b
        return a

In this code, self.gcd(first_digit, last_digit) calls the custom gcd method defined in the Solution class.

can anyone please tell what is wrong with this code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  int firstd(int n) {
    while (n > 10) {
      n /= 10;
    }
    return n;
  }
  int coprime(int a, int b) {
    int max = Math.min(a, b), h = 0;
    for (int i = 1; i <= max; i++) {
      if (a % i == 0 && b % i == 0) {
        h = i;
      }
    }
    return h;
  }
  public int countBeautifulPairs(int[] nums) {
    int c = 0;
    for (int i = 0; i < nums.length - 1; i++) {
      int fd = firstd(nums[i]);
      for (int j = i + 1; j < nums.length; j++) {

        int ld = nums[j] % 10;
        if (coprime(fd, ld) == 1) {
          c++;
        }
      }
    }
    return c;
  }
}

Your code seems mostly correct, but the coprime method is inefficient and might be causing issues for larger inputs.

In your coprime method, you iterate from 1 to Math.min(a, b), check if a and b are divisible by the current number i, and update h if they are. If a and b are large, this operation could be quite time-consuming.

Also, it doesn’t seem that your method would return the correct result if a and b are coprime. This is because if a and b are coprime, your method should return 1 (as 1 is the greatest common divisor), but as per your code it might not.

I would suggest replacing the coprime method with a method to calculate the greatest common divisor (gcd) using the Euclidean algorithm, which is more efficient:

1
2
3
4
5
6
7
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

Then, in your countBeautifulPairs method, you could use gcd(fd, ld) == 1 to check if fd and ld are coprime:

1
2
3
if (gcd(fd, ld) == 1) {
    c++;
}

This should give you the same result but in a more efficient and correct way.

can anyone tell me why this code not working????

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public: int countBeautifulPairs(vector & nums) {
    int n = nums.size();
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      int y;
      if (nums[i] >= 10)
        y = nums[i] / 10;
      else
        y = nums[i] % 10;
      for (int j = i + 1; j < n; j++) {

        int x = nums[j] % 10;
        if (__gcd(x, y) == 1)
          cnt++;
      }
    }
    return cnt;

  }
};

In the code provided, you’re trying to find the first digit of the numbers using:

1
2
3
4
if (nums[i] >= 10)
    y = nums[i] / 10;
else
    y = nums[i] % 10;

However, this code will only get the first digit of a two-digit number. For numbers with more than two digits, it will not return the first digit. For instance, for the number 123, your code will return 12 instead of 1.

Here’s how you could modify the code to correctly get the first digit of numbers:

1
2
3
int y = nums[i];
while(y >= 10)
    y /= 10;

So, your modified code would look like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countBeautifulPairs(vector<int>& nums) {
        int n = nums.size();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int y = nums[i];
            while(y >= 10)
                y /= 10;
            for (int j = i + 1; j < n; j++) {
                int x = nums[j] % 10;
                if (__gcd(x, y) == 1)
                    cnt++;
            }
        }
        return cnt;
    }
};

This should fix your problem and correctly count the number of beautiful pairs in the given array.

[31,25,72,79,74] why the answer is 7? why not 9?

Let’s break down the array [31, 25, 72, 79, 74] and check the beautiful pairs:

A pair (i, j) is called beautiful if the first digit of nums[i] and the last digit of nums[j] are coprime. Coprime numbers are numbers that have no common divisor other than 1.

(31, 25) => First digit of 31 is 3, last digit of 25 is 5. 3 and 5 are coprime. So, this pair is beautiful.
(31, 72) => First digit of 31 is 3, last digit of 72 is 2. 3 and 2 are coprime. So, this pair is beautiful.
(31, 79) => First digit of 31 is 3, last digit of 79 is 9. 3 and 9 are not coprime (they share a divisor of 3). So, this pair is not beautiful.
(31, 74) => First digit of 31 is 3, last digit of 74 is 4. 3 and 4 are coprime. So, this pair is beautiful.
(25, 72) => First digit of 25 is 2, last digit of 72 is 2. 2 and 2 are not coprime (they share a divisor of 2). So, this pair is not beautiful.
(25, 79) => First digit of 25 is 2, last digit of 79 is 9. 2 and 9 are coprime. So, this pair is beautiful.
(25, 74) => First digit of 25 is 2, last digit of 74 is 4. 2 and 4 are not coprime (they share a divisor of 2). So, this pair is not beautiful.
(72, 79) => First digit of 72 is 7, last digit of 79 is 9. 7 and 9 are coprime. So, this pair is beautiful.
(72, 74) => First digit of 72 is 7, last digit of 74 is 4. 7 and 4 are coprime. So, this pair is beautiful.
(79, 74) => First digit of 79 is 7, last digit of 74 is 4. 7 and 4 are coprime. So, this pair is beautiful.

So, as you see, out of 10 pairs, 7 pairs are beautiful (satisfy the condition). Hence, the answer is 7, not 9.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int countBeautifulPairs(vector < int > & nums) {
  int cnt[10] = {}, res = 0;
  for (int i = 0; i < nums.size(); ++i) {
    for (int n = 1; n < 10; ++n)
      if (gcd(n, nums[i] % 10) == 1)
        res += cnt[n];
    while (nums[i] >= 10)
      nums[i] /= 10;
    ++cnt[nums[i]];
  }
  return res;
}

This is a great approach using a count array and the gcd function to solve the problem in a less complex manner. Let’s go through the function step by step.

int cnt[10] = {} initializes an array of size 10 with all elements being 0. The index of this array corresponds to the first digit of the numbers in nums.
res is the result, which counts the number of beautiful pairs.
We start iterating over the nums array. For each number, we do the following:
In the inner loop for (int n = 1; n < 10; ++n), we iterate through 1 to 9 (all possible first digits). We then check if n and the last digit of the current number (nums[i] % 10) are coprime (i.e., gcd(n, nums[i] % 10) == 1). If they are, we add the count of n from the count array to res. This means that for each n which is coprime with the last digit of nums[i], we add the number of such n that we have encountered so far (since those would form a beautiful pair with the current number).
The next step (while (nums[i] >= 10) nums[i] /= 10;) is to extract the first digit of the current number nums[i]. We do this by continuously dividing nums[i] by 10 until it is less than 10. Then the value of nums[i] is the first digit of the original number.
We then increment the count of this first digit in the count array (++cnt[nums[i]];), so we remember how many numbers have this first digit.
We continue this process for all the numbers in nums. In the end, res will be the total number of beautiful pairs in nums.

By using this approach, the algorithm goes through the nums array only once, counting the beautiful pairs on the go. This makes the time complexity linear (O(n)), which is more efficient compared to the brute-force approach.

The while loop takes O(log10(nums[i]))O(log_{10}(nums[i]))O(log 10 (nums[i])) time

Yes, you’re right. The original solution where we use a while loop to isolate the first digit of a number has a complexity of O(log10(nums[i])), because with each iteration we’re effectively dividing the number by 10.

That being said, please note that the log10 operation here is bounded by the maximum possible number of digits in the input, which is a small, constant number for our problem (at most 4, given the constraint that 1 <= nums[i] <= 9999).

Hence, although we say O(log10(nums[i])), this operation doesn’t significantly affect our overall time complexity, which remains O(n) where n is the number of elements in the input array ’nums’.

Hey, how many coprimes will be in [31,25,72,79,74] can you please list them ?

Sure, in the array [31,25,72,79,74], we would first determine the first digit of each number (which in this case are 3, 2, 7, 7, 7 respectively), and the last digit of each number (which are 1, 5, 2, 9, 4).

Here are the beautiful pairs (i.e., pairs where the first digit of the first number and the last digit of the second number are coprime):

(31, 25): 3 (first digit of 31) and 5 (last digit of 25) are coprime.
(31, 72): 3 (first digit of 31) and 2 (last digit of 72) are coprime.
(31, 79): 3 (first digit of 31) and 9 (last digit of 79) are coprime.
(25, 79): 2 (first digit of 25) and 9 (last digit of 79) are coprime.
(72, 79): 7 (first digit of 72) and 9 (last digit of 79) are coprime.
(79, 74): 7 (first digit of 79) and 4 (last digit of 74) are coprime.
(72, 74): 7 (first digit of 72) and 4 (last digit of 74) are coprime.

So, there are 7 beautiful pairs in this array.