Count of pairs in a given range with sum of their product and sum equal to their concatenated number

0 0 4 minutes read

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 pairs
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 Code
int 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 Y
import java.util.*;
class GFG{
 
// Function for counting pairs
static 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 Code
public 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 pairs
def 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 Code
if __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 Y
using System;
class GFG{
 
// Function for counting pairs
static 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 Code
public 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>

Output:

Time Complexity: O(log₁₀(B))
Space Complexity: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!