Given two numbers A and B, the task is to find the count of pairs (X, Y) in range [A, B], such that (X * Y) + (X + Y) is equal to the number formed by concatenation of X and Y
Examples:
Input: A = 1, B = 9
Output: 9
Explanation:
The pairs (1, 9), (2, 9), (3, 9), (4, 9), (5, 9), (6, 9), (7, 9), (8, 9) and (9, 9) are the required pairs.
Input: A = 4, B = 10
Output: 7
Explanation: The pairs (4, 9), (5, 9), (6, 9), (7, 9), (8, 9), (9, 9) and (10, 9) satisfy the required condition.
Approach :
We can observe that any number of the form [9, 99, 999, 9999, ….] satisfies the condition with all other values.
Illustration:
If Y = 9, the required condition is satisfied for all values of X.
{1*9 + (1 + 9) = 19, 2*9 + (2 + 9) = 29, ……….. 11*9 + (11 + 9) = 119 …..
Similarly, for Y = 99, 1*99 + 1 + 99 = 199, 2*99 + 2 + 99 = 299, ………
Hence, follow the steps below to solve the problems:
- Count the number of possible values of Y of the form {9, 99, 999, 9999, ….} in range [A, B] and store in countY
- Count the number of possible values of X in the range [A, B] as countX
countX = (B - A + 1)
- The required count will be the product of possible count of X and Y, i.e.
answer = countX * countY
Below is the implementation of the above approach:
C++
// C++ program to count// all the possible pairs// with X*Y + (X + Y) equal to// number formed by// concatenating X and Y#include <bits/stdc++.h>using namespace std;// Function for counting pairsint countPairs(int A, int B){ int countY = 0, countX = (B - A) + 1, next_val = 9; // Count possible values // of Y while (next_val <= B) { if (next_val >= A) { countY += 1; } next_val = next_val * 10 + 9; } return (countX * countY);}// Driver Codeint main(){ int A = 1; int B = 16; cout << countPairs(A, B); return 0;} |
Java
// Java program to count// all the possible pairs// with X*Y + (X + Y) equal to// number formed by// concatenating X and Yimport java.util.*;class GFG{// Function for counting pairsstatic int countPairs(int A, int B){ int countY = 0, countX = (B - A) + 1, next_val = 9; // Count possible values // of Y while (next_val <= B) { if (next_val >= A) { countY += 1; } next_val = next_val * 10 + 9; } return (countX * countY);}// Driver Codepublic static void main(String args[]){ int A = 1; int B = 16; System.out.print(countPairs(A, B));}}// This code is contributed by Code_Mech |
Python3
# Python3 program to count# all the possible pairs# with X*Y + (X + Y) equal to# number formed by# concatenating X and Y# Function for counting pairsdef countPairs(A, B): countY = 0 countX = (B - A) + 1 next_val = 9 # Count possible values # of Y while (next_val <= B): if (next_val >= A): countY += 1 next_val = next_val * 10 + 9 return (countX * countY)# Driver Codeif __name__ == '__main__': A = 1 B = 16 print(countPairs(A, B))# This code is contributed by mohit kumar 29 |
C#
// C# program to count// all the possible pairs// with X*Y + (X + Y) equal to// number formed by// concatenating X and Yusing System;class GFG{// Function for counting pairsstatic int countPairs(int A, int B){ int countY = 0, countX = (B - A) + 1, next_val = 9; // Count possible values // of Y while (next_val <= B) { if (next_val >= A) { countY += 1; } next_val = next_val * 10 + 9; } return (countX * countY);}// Driver Codepublic static void Main(){ int A = 1; int B = 16; Console.Write(countPairs(A, B));}}// This code is contributed by Akanksha_Rai |
Javascript
<script>// javascript program to count// all the possible pairs// with X*Y + (X + Y) equal to// number formed by// concatenating X and Y // Function for counting pairs function countPairs(A , B) { var countY = 0, countX = (B - A) + 1, next_val = 9; // Count possible values // of Y while (next_val <= B) { if (next_val >= A) { countY += 1; } next_val = next_val * 10 + 9; } return (countX * countY); } // Driver Code var A = 1; var B = 16; document.write(countPairs(A, B));// This code is contributed by todaysgaurav </script> |
16
Time Complexity: O(log10(B))
Space Complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
