Given two integers L and R, the task is to find the count of unordered pairs of integers (A, B) in the range [L, R] such that the ratio of A and B is the same as the ratio of the product of digits of A and the product of digits of B.
Examples:
Input: L = 10, R = 50
Output: 2
Explanation: The pairs in the range [10, 50] that follow the given condition are (15, 24) as 15 : 24 = 5 : 8 ? (1*5) : (2*4) = 5 : 8 and (18, 45) as 18 : 45 = 2 : 5 ? (1*8) : (4*5) = 8 : 20 = 2 : 5.Input: L = 1, R = 100
Output: 43
Approach: The given problem can be solved using the steps discussed below:
- Create a function to calculate the product of digits of a number.
- Iterate over all the unordered pairs of integers in the range [L, R] using a and b for each pair (a, b), a : b is equivalent to the product of digits of a : product of digits of b if and only if a * product of digits of b = b * product of digits of a.
- Using the above observation, maintain the count of the valid pairs of (a, b) in a variable cntPair such that a * product of digits of b = b * product of digits of a.
- After completing the above steps, print the value of cntPair as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the product of// digits of the given numberint getProduct(int n){ int product = 1; while (n != 0) { product = product * (n % 10); n = n / 10; } return product;}// Function to find the count of pairs// (a, b) such that a:b = (product of// digits of a):(product of digits of b)int countPairs(int L, int R){ // Stores the count of the valid pairs int cntPair = 0; // Loop to iterate over all unordered // pairs (a, b) for (int a = L; a <= R; a++) { for (int b = a + 1; b <= R; b++) { // Stores the product of // digits of a int x = getProduct(a); // Stores the product of // digits of b int y = getProduct(b); // If x!=0 and y!=0 and a:b // is equivalent to x:y if (x && y && (a * y) == (b * x)) { // Increment valid pair count cntPair++; } } } // Return Answer return cntPair;}// Driver codeint main(){ int L = 1; int R = 100; // Function Call cout << countPairs(1, 100); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find the product of// digits of the given numberpublic static int getProduct(int n){ int product = 1; while (n != 0) { product = product * (n % 10); n = n / 10; } return product;}// Function to find the count of pairs// (a, b) such that a:b = (product of// digits of a):(product of digits of b)public static int countPairs(int L, int R){ // Stores the count of the valid pairs int cntPair = 0; // Loop to iterate over all unordered // pairs (a, b) for (int a = L; a <= R; a++) { for (int b = a + 1; b <= R; b++) { // Stores the product of // digits of a int x = getProduct(a); // Stores the product of // digits of b int y = getProduct(b); // If x!=0 and y!=0 and a:b // is equivalent to x:y if (x !=0 && y != 0 && (a * y) == (b * x)) { // Increment valid pair count cntPair++; } } } // Return Answer return cntPair;}// Driver codepublic static void main(String args[]){ int L = 1; int R = 100; // Function Call System.out.println(countPairs(L, R));}}// This code is contributed by _saurabh_jaiswal. |
Python3
# Python 3 program for the above approach# Function to find the product of# digits of the given numberdef getProduct(n): product = 1 while (n != 0): product = product * (n % 10) n = n // 10 return product# Function to find the count of pairs# (a, b) such that a:b = (product of# digits of a):(product of digits of b)def countPairs(L, R): # Stores the count of the valid pairs cntPair = 0 # Loop to iterate over all unordered # pairs (a, b) for a in range(L,R+1,1): for b in range(a + 1,R+1,1): # Stores the product of # digits of a x = getProduct(a) # Stores the product of # digits of b y = getProduct(b) # If x!=0 and y!=0 and a:b # is equivalent to x:y if (x and y and (a * y) == (b * x)): # Increment valid pair count cntPair += 1 # Return Answer return cntPair# Driver codeif __name__ == '__main__': L = 1 R = 100 # Function Call print(countPairs(1, 100)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the product of // digits of the given number public static int getProduct(int n) { int product = 1; while (n != 0) { product = product * (n % 10); n = n / 10; } return product; } // Function to find the count of pairs // (a, b) such that a:b = (product of // digits of a):(product of digits of b) public static int countPairs(int L, int R) { // Stores the count of the valid pairs int cntPair = 0; // Loop to iterate over all unordered // pairs (a, b) for (int a = L; a <= R; a++) { for (int b = a + 1; b <= R; b++) { // Stores the product of // digits of a int x = getProduct(a); // Stores the product of // digits of b int y = getProduct(b); // If x!=0 and y!=0 and a:b // is equivalent to x:y if (x !=0 && y != 0 && (a * y) == (b * x)) { // Increment valid pair count cntPair++; } } } // Return Answer return cntPair; } // Driver code public static void Main(string []args) { int L = 1; int R = 100; // Function Call Console.WriteLine(countPairs(L, R)); }}// This code is contributed by AnkThon |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the product of // digits of the given number function getProduct(n) { let product = 1; while (n != 0) { product = product * (n % 10); n = Math.floor(n / 10); } return product; } // Function to find the count of pairs // (a, b) such that a:b = (product of // digits of a):(product of digits of b) function countPairs(L, R) { // Stores the count of the valid pairs let cntPair = 0; // Loop to iterate over all unordered // pairs (a, b) for (let a = L; a <= R; a++) { for (let b = a + 1; b <= R; b++) { // Stores the product of // digits of a let x = getProduct(a); // Stores the product of // digits of b let y = getProduct(b); // If x!=0 and y!=0 and a:b // is equivalent to x:y if (x && y && (a * y) == (b * x)) { // Increment valid pair count cntPair++; } } } // Return Answer return cntPair; } // Driver code let L = 1; let R = 100; // Function Call document.write(countPairs(1, 100));// This code is contributed by Potta Lokesh </script> |
Output:
43
Time Complexity: O(N2*log N) where N represents the number of integers in the given range i.e, R – L.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
