Count of pairs satisfying the given condition

0 0 4 minutes read

Given two integers A and B, the task is to calculate the number of pairs (a, b) such that 1 ? a ? A, 1 ? b ? B and the equation (a * b) + a + b = concat(a, b) is true where conc(a, b) is the concatenation of a and b (for example, conc(12, 23) = 1223, conc(100, 11) = 10011). Note that a and b should not contain any leading zeroes.

Examples:

Input: A = 1, B = 12
Output: 1
There exists only one pair (1, 9) satisfying
the equation ((1 * 9) + 1 + 9 = 19)

Input: A = 2, B = 8
Output: 0
There doesn’t exist any pair satisfying the equation.

Approach: It can be observed that the above (a * b + a + b = conc(a, b)) will only be satisfied when the digits of an integer ? b contains only 9. Simply, calculate the number of digits (? b) containing only 9 and multiply with the integer a.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of
// pairs satisfying the equation
int countPair(int a, int b)
{
    // Converting integer b to string
    // by using to_string function
    string s = to_string(b);
 
    // Loop to check if all the digits
    // of b are 9 or not
    int i;
    for (i = 0; i < s.length(); i++) {
 
        // If '9' doesn't appear
        // then break the loop
        if (s[i] != '9')
            break;
    }
 
    int result;
 
    // If all the digits of b contain 9
    // then multiply a with string length
    // else multiply a with string length - 1
    if (i == s.length())
        result = a * s.length();
    else
        result = a * (s.length() - 1);
 
    // Return the number of pairs
    return result;
}
 
// Driver code
int main()
{
    int a = 5, b = 101;
 
    cout << countPair(a, b);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
 
// Function to return the number of
// pairs satisfying the equation
static int countPair(int a, int b)
{
    // Converting integer b to String
    // by using to_String function
    String s = String.valueOf(b);
 
    // Loop to check if all the digits
    // of b are 9 or not
    int i;
    for (i = 0; i < s.length(); i++)
    {
 
        // If '9' doesn't appear
        // then break the loop
        if (s.charAt(i) != '9')
            break;
    }
 
    int result;
 
    // If all the digits of b contain 9
    // then multiply a with String length
    // else multiply a with String length - 1
    if (i == s.length())
        result = a * s.length();
    else
        result = a * (s.length() - 1);
 
    // Return the number of pairs
    return result;
}
 
// Driver code
public static void main(String[] args)
{
    int a = 5, b = 101;
 
    System.out.print(countPair(a, b));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach
 
# Function to return the number of
# pairs satisfying the equation
def countPair(a, b):
     
    # Converting integer b to string
    # by using to_function
    s = str(b)
 
    # Loop to check if all the digits
    # of b are 9 or not
    i = 0
    while i < (len(s)):
 
        # If '9' doesn't appear
        # then break the loop
        if (s[i] != '9'):
            break
        i += 1
 
    result = 0
 
    # If all the digits of b contain 9
    # then multiply a with length
    # else multiply a with length - 1
    if (i == len(s)):
        result = a * len(s)
    else:
        result = a * (len(s) - 1)
 
    # Return the number of pairs
    return result
 
# Driver code
a = 5
b = 101
 
print(countPair(a, b))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the number of
// pairs satisfying the equation
static int countPair(int a, int b)
{
    // Converting integer b to String
    // by using to_String function
    String s = String.Join("", b);
 
    // Loop to check if all the digits
    // of b are 9 or not
    int i;
    for (i = 0; i < s.Length; i++)
    {
 
        // If '9' doesn't appear
        // then break the loop
        if (s[i] != '9')
            break;
    }
 
    int result;
 
    // If all the digits of b contain 9
    // then multiply a with String length
    // else multiply a with String length - 1
    if (i == s.Length)
        result = a * s.Length;
    else
        result = a * (s.Length - 1);
 
    // Return the number of pairs
    return result;
}
 
// Driver code
public static void Main(String[] args)
{
    int a = 5, b = 101;
 
    Console.Write(countPair(a, b));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the number of
// pairs satisfying the equation
function countPair(a, b)
{
     
    // Converting integer b to string
    // by using to_string function
    var s = (b.toString());
 
    // Loop to check if all the digits
    // of b are 9 or not
    var i;
    for(i = 0; i < s.length; i++)
    {
         
        // If '9' doesn't appear
        // then break the loop
        if (s[i] != '9')
            break;
    }
 
    var result;
 
    // If all the digits of b contain 9
    // then multiply a with string length
    // else multiply a with string length - 1
    if (i == s.length)
        result = a * s.length;
    else
        result = a * (s.length - 1);
 
    // Return the number of pairs
    return result;
}
 
// Driver code
var a = 5, b = 101;
document.write(countPair(a, b));
 
// This code is contributed by rutvik_56
 
</script>

Output:

Time Complexity: O(b)

Auxiliary Space: 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!