Given a number N, the task is to find the number of pairs (A, B) in the range [1, N] such that the last digit of A is equal to the first digit of B, and the first digit of A is equal to the last digit of B.
Examples:
Input: N = 25
Output: 17
Explanation:
The pairs are:
(1, 1), (1, 11), (2, 2), (2, 22), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9), (11, 1), (11, 11), (12, 21), (21, 12), (22, 2), (22, 22)
Input: N = 100
Output: 108
Approach: For each pair of integers (i, j)(0 ? i, j ? 9), let us define ci, j (1 ? k ? N) which is the count of the first digit of k is equal to i, and the last digit is equal to j. By using ci, j, the answer for the problem can be calculated by ?i=09 ?j=09 ci, j * cj, i .
Below is the implementation of the above approach:
CPP
// C++ program to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to Count of pairs (A, B) in range 1 to N int pairs(int n) { vector<vector<int> > c(10, vector<int>(10, 0)); int tmp = 1; // count C i, j for (int i = 1; i <= n; i++) { if (i >= tmp * 10) tmp *= 10; c[i / tmp][i % 10]++; } // Calculate number of pairs long long ans = 0; for (int i = 1; i < 10; i++) for (int j = 1; j < 10; j++) ans += (long long)c[i][j] * c[j][i]; return ans; } // Driver code int main() { int n = 25; // Function call cout << pairs(n); return 0; } |
Java
// Java program to implement the above approach class GFG{ // Function to Count of pairs (A, B) in range 1 to N static int pairs(int n) { int [][]c = new int[10][10]; int tmp = 1; // count C i, j for (int i = 1; i <= n; i++) { if (i >= tmp * 10) tmp *= 10; c[i / tmp][i % 10]++; } // Calculate number of pairs int ans = 0; for (int i = 1; i < 10; i++) for (int j = 1; j < 10; j++) ans += c[i][j] * c[j][i]; return ans; } // Driver code public static void main(String[] args) { int n = 25; // Function call System.out.print(pairs(n)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement the above approach # Function to Count of pairs (A, B) in range 1 to N def pairs(n): c = [[0 for i in range(10)] for i in range(10)] tmp = 1 # count C i, j for i in range(1, n + 1): if (i >= tmp * 10): tmp *= 10 c[i // tmp][i % 10] += 1 # Calculate number of pairs ans = 0 for i in range(1, 10): for j in range(1, 10): ans += c[i][j] * c[j][i] return ans # Driver code if __name__ == '__main__': n = 25 # Function call print(pairs(n)) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement the above approach using System; class GFG{ // Function to Count of pairs (A, B) in range 1 to N static int pairs(int n) { int [,]c = new int[10, 10]; int tmp = 1; // count C i, j for (int i = 1; i <= n; i++) { if (i >= tmp * 10) tmp *= 10; c[i / tmp, i % 10]++; } // Calculate number of pairs int ans = 0; for (int i = 1; i < 10; i++) for (int j = 1; j < 10; j++) ans += c[i, j] * c[j, i]; return ans; } // Driver code public static void Main(String[] args) { int n = 25; // Function call Console.Write(pairs(n)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program for the above approach // Function to Count of pairs (A, B) in range 1 to N function pairs(n) { let c = new Array(10); for (var i = 0; i < c.length; i++) { c[i] = new Array(2); } for (var i = 0; i < c.length; i++) { for (var j = 0; j < c.length; j++) { c[i][j] = 0; } } let tmp = 1; // count C i, j for (let i = 1; i <= n; i++) { if (i >= tmp * 10) tmp *= 10; c[(Math.floor(i / tmp))][i % 10]++; } // Calculate number of pairs let ans = 0; for (let i = 1; i < 10; i++) for (let j = 1; j < 10; j++) ans += c[i][j] * c[j][i]; return ans; } // Driver code let n = 25; // Function call document.write(pairs(n)); </script> |
17
Time Complexity: O(N)
Auxiliary Space: O(10*10)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
