Posted on by Kalkicode
Code Mathematics

Find all numbers having digit product equal to k in 1 to N

The given problem revolves around finding all the numbers in the range from 1 to N whose digit product is equal to a given value, K. The digit product of a number is the product of its individual digits. For example, the digit product of 123 is 1 * 2 * 3 = 6.

Problem Statement

Given a range of numbers from 1 to N and a value K, the task is to find and list all the numbers within this range whose digit product is equal to K.

Example

Let's take a couple of examples to understand the problem better.

Example A

• Given: N = 100, K = 40
• We need to find numbers from 1 to 100 whose digit product is 40.
• The numbers that satisfy this condition are 58 and 85, as 5 * 8 = 40 and 8 * 5 = 40.

Example B

• Given: N = 80, K = 0
• We need to find numbers from 1 to 80 whose digit product is 0.
• All numbers multiplied by 0 have a digit product of 0. Therefore, all numbers from 10 to 80 will satisfy this condition.

Idea to Solve

1. Loop through the range from 1 to N.
2. For each number, calculate its digit product.
3. If the digit product matches K, add that number to the result.

Pseudocode

``````function findDigitProduct(num):
n = num
product = 1
while n != 0 and product > 0:
product *= (n % 10)
n = n / 10
return product

function digitProductInRange(n, k):
result = []
for i in range(1, n + 1):
if findDigitProduct(i) == k:
result.append(i)
return result

# Example usage
N = 100
K = 40
result = digitProductInRange(N, K)
print(result)``````

Algorithm Explanation

1. The `findDigitProduct` function calculates the digit product of a given number.
2. The `digitProductInRange` function iterates through the range from 1 to N.
3. For each number, it calls the `findDigitProduct` function to calculate the digit product.
4. If the calculated digit product matches K, the number is added to the `result` list.
5. Finally, the `result` list is returned, containing all numbers whose digit product is K.

Code Solution

``````/*
Java program for
Find all numbers having digit product equal to k in 1 to N
*/
public class Product
{
public int findProduct(int num)
{
int n = num;
int product = 1;
// Calculate digit product
while (n != 0 && product > 0)
{
product *= (n % 10);
n = n / 10;
}
return product;
}
public void digitProduct(int n, int k)
{
if (n < 0)
{
return;
}
boolean result = false;
System.out.print("\n Given k " + k);
System.out.print("\n Product of number digit from (1 to " +
n + ") is \n");
for (int i = 0; i <= n; ++i)
{
if (findProduct(i) == k)
{
System.out.print("  " + i);
result = true;
}
}
if (result == false)
{
// When no result
System.out.print(" None ");
}
}
public static void main(String[] args)
{
// Test A
int k = 40;
int n = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
// Test B
k = 0;
n = 80;
/*
k = 0
n = 80
------------
1 ✕ 0 = 0
2 ✕ 0 = 0
3 ✕ 0 = 0
4 ✕ 0 = 0
5 ✕ 0 = 0
6 ✕ 0 = 0
7 ✕ 0 = 0
8 ✕ 0 = 0
------------
[10  20  30  40  50  60  70  80]
*/
}
}``````

Output

`````` Given k 40
Product of number digit from (1 to 100) is
58  85
Given k 0
Product of number digit from (1 to 80) is
10  20  30  40  50  60  70  80``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program for
Find all numbers having digit product equal to k in 1 to N
*/
class Product
{
public: int findProduct(int num)
{
int n = num;
int product = 1;
// Calculate digit product
while (n != 0 && product > 0)
{
product *= (n % 10);
n = n / 10;
}
return product;
}
void digitProduct(int n, int k)
{
if (n < 0)
{
return;
}
bool result = false;
cout << "\n Given k " << k;
cout << "\n Product of number digit from (1 to "
<< n << ") is \n";
for (int i = 0; i <= n; ++i)
{
if (this->findProduct(i) == k)
{
cout << "  " << i;
result = true;
}
}
if (result == false)
{
// When no result
cout << " None ";
}
}
};
int main()
{
// Test A
int k = 40;
int n = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
// Test B
k = 0;
n = 80;
/*
k = 0
n = 80
------------
1 ✕ 0 = 0
2 ✕ 0 = 0
3 ✕ 0 = 0
4 ✕ 0 = 0
5 ✕ 0 = 0
6 ✕ 0 = 0
7 ✕ 0 = 0
8 ✕ 0 = 0
------------
[10  20  30  40  50  60  70  80]
*/
return 0;
}``````

Output

`````` Given k 40
Product of number digit from (1 to 100) is
58  85
Given k 0
Product of number digit from (1 to 80) is
10  20  30  40  50  60  70  80``````
``````// Include namespace system
using System;
/*
Csharp program for
Find all numbers having digit product equal to k in 1 to N
*/
public class Product
{
public int findProduct(int num)
{
int n = num;
int product = 1;
// Calculate digit product
while (n != 0 && product > 0)
{
product *= (n % 10);
n = n / 10;
}
return product;
}
public void digitProduct(int n, int k)
{
if (n < 0)
{
return;
}
Boolean result = false;
Console.Write("\n Given k " + k);
Console.Write("\n Product of number digit from (1 to " +
n + ") is \n");
for (int i = 0; i <= n; ++i)
{
if (this.findProduct(i) == k)
{
Console.Write("  " + i);
result = true;
}
}
if (result == false)
{
// When no result
Console.Write(" None ");
}
}
public static void Main(String[] args)
{
// Test A
int k = 40;
int n = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
// Test B
k = 0;
n = 80;
/*
k = 0
n = 80
------------
1 ✕ 0 = 0
2 ✕ 0 = 0
3 ✕ 0 = 0
4 ✕ 0 = 0
5 ✕ 0 = 0
6 ✕ 0 = 0
7 ✕ 0 = 0
8 ✕ 0 = 0
------------
[10  20  30  40  50  60  70  80]
*/
}
}``````

Output

`````` Given k 40
Product of number digit from (1 to 100) is
58  85
Given k 0
Product of number digit from (1 to 80) is
10  20  30  40  50  60  70  80``````
``````package main
import "fmt"
/*
Go program for
Find all numbers having digit product equal to k in 1 to N
*/

func findProduct(num int) int {
var n int = num
var product int = 1
// Calculate digit product
for (n != 0 && product > 0) {
product *= (n % 10)
n = n / 10
}
return product
}
func digitProduct(n, k int) {
if n < 0 {
return
}
var result bool = false
fmt.Print("\n Given k ", k)
fmt.Print("\n Product of number digit from (1 to ",
n, ") is \n")
for i := 0 ; i <= n ; i++ {
if findProduct(i) == k {
fmt.Print("  ", i)
result = true
}
}
if result == false {
// When no result
fmt.Print(" None ")
}
}
func main() {

// Test A
var k int = 40
var n int = 100
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
digitProduct(n, k)
// Test B
k = 0
n = 80
/*
k = 0
n = 80
------------
1 ✕ 0 = 0
2 ✕ 0 = 0
3 ✕ 0 = 0
4 ✕ 0 = 0
5 ✕ 0 = 0
6 ✕ 0 = 0
7 ✕ 0 = 0
8 ✕ 0 = 0
------------
[10  20  30  40  50  60  70  80]
*/
digitProduct(n, k)
}``````

Output

`````` Given k 40
Product of number digit from (1 to 100) is
58  85
Given k 0
Product of number digit from (1 to 80) is
10  20  30  40  50  60  70  80``````
``````<?php
/*
Php program for
Find all numbers having digit product equal to k in 1 to N
*/
class Product
{
public	function findProduct(\$num)
{
\$n = \$num;
\$product = 1;
// Calculate digit product
while (\$n != 0 && \$product > 0)
{
\$product *= (\$n % 10);
\$n = (int)(\$n / 10);
}
return \$product;
}
public	function digitProduct(\$n, \$k)
{
if (\$n < 0)
{
return;
}
\$result = false;
echo("\n Given k ".\$k);
echo("\n Product of number digit from (1 to ".\$n.
") is \n");
for (\$i = 0; \$i <= \$n; ++\$i)
{
if (\$this->findProduct(\$i) == \$k)
{
echo("  ".\$i);
\$result = true;
}
}
if (\$result == false)
{
// When no result
echo(" None ");
}
}
}

function main()
{
// Test A
\$k = 40;
\$n = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
// Test B
\$k = 0;
\$n = 80;
/*
k = 0
n = 80
------------
1 ✕ 0 = 0
2 ✕ 0 = 0
3 ✕ 0 = 0
4 ✕ 0 = 0
5 ✕ 0 = 0
6 ✕ 0 = 0
7 ✕ 0 = 0
8 ✕ 0 = 0
------------
[10  20  30  40  50  60  70  80]
*/
}
main();``````

Output

`````` Given k 40
Product of number digit from (1 to 100) is
58  85
Given k 0
Product of number digit from (1 to 80) is
10  20  30  40  50  60  70  80``````
``````/*
Node JS program for
Find all numbers having digit product equal to k in 1 to N
*/
class Product
{
findProduct(num)
{
var n = num;
var product = 1;
// Calculate digit product
while (n != 0 && product > 0)
{
product *= (n % 10);
n = parseInt(n / 10);
}
return product;
}
digitProduct(n, k)
{
if (n < 0)
{
return;
}
var result = false;
process.stdout.write("\n Given k " + k);
process.stdout.write("\n Product of number digit from (1 to " +
n + ") is \n");
for (var i = 0; i <= n; ++i)
{
if (this.findProduct(i) == k)
{
process.stdout.write("  " + i);
result = true;
}
}
if (result == false)
{
// When no result
process.stdout.write(" None ");
}
}
}

function main()
{
// Test A
var k = 40;
var n = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
// Test B
k = 0;
n = 80;
/*
k = 0
n = 80
------------
1 ✕ 0 = 0
2 ✕ 0 = 0
3 ✕ 0 = 0
4 ✕ 0 = 0
5 ✕ 0 = 0
6 ✕ 0 = 0
7 ✕ 0 = 0
8 ✕ 0 = 0
------------
[10  20  30  40  50  60  70  80]
*/
}
main();``````

Output

`````` Given k 40
Product of number digit from (1 to 100) is
58  85
Given k 0
Product of number digit from (1 to 80) is
10  20  30  40  50  60  70  80``````
``````#    Python 3 program for
#    Find all numbers having digit product equal to k in 1 to N
class Product :
def findProduct(self, num) :
n = num
product = 1
#  Calculate digit product
while (n != 0 and product > 0) :
product *= (n % 10)
n = int(n / 10)

return product

def digitProduct(self, n, k) :
if (n < 0) :
return

result = False
print("\n Given k ", k, end = "")
print("\n Product of number digit from (1 to ",
n ,") is ")
i = 0
while (i <= n) :
if (self.findProduct(i) == k) :
print("  ", i, end = "")
result = True

i += 1

if (result == False) :
#  When no result
print(" None ", end = "")

def main() :
#  Test A
k = 40
n = 100
#    k = 40
#    n = 100
#    ----------
#    5 ✕ 8 = 40
#    8 ✕ 5 = 40
#    -----------
#    [58 84]
#  Test B
k = 0
n = 80
#    k = 0
#    n = 80
#    ------------
#    1 ✕ 0 = 0
#    2 ✕ 0 = 0
#    3 ✕ 0 = 0
#    4 ✕ 0 = 0
#    5 ✕ 0 = 0
#    6 ✕ 0 = 0
#    7 ✕ 0 = 0
#    8 ✕ 0 = 0
#    ------------
#    [10  20  30  40  50  60  70  80]

if __name__ == "__main__": main()``````

Output

`````` Given k  40
Product of number digit from (1 to  100 ) is
58   85
Given k  0
Product of number digit from (1 to  80 ) is
10   20   30   40   50   60   70   80``````
``````#    Ruby program for
#    Find all numbers having digit product equal to k in 1 to N
class Product
def findProduct(num)
n = num
product = 1
#  Calculate digit product
while (n != 0 && product > 0)
product *= (n % 10)
n = n / 10
end

return product
end

def digitProduct(n, k)
if (n < 0)
return
end

result = false
print("\n Given k ", k)
print("\n Product of number digit from (1 to ", n ,") is \n")
i = 0
while (i <= n)
if (self.findProduct(i) == k)
print("  ", i)
result = true
end

i += 1
end

if (result == false)
#  When no result
print(" None ")
end

end

end

def main()
#  Test A
k = 40
n = 100
#    k = 40
#    n = 100
#    ----------
#    5 ✕ 8 = 40
#    8 ✕ 5 = 40
#    -----------
#    [58 84]
#  Test B
k = 0
n = 80
#    k = 0
#    n = 80
#    ------------
#    1 ✕ 0 = 0
#    2 ✕ 0 = 0
#    3 ✕ 0 = 0
#    4 ✕ 0 = 0
#    5 ✕ 0 = 0
#    6 ✕ 0 = 0
#    7 ✕ 0 = 0
#    8 ✕ 0 = 0
#    ------------
#    [10  20  30  40  50  60  70  80]
end

main()``````

Output

`````` Given k 40
Product of number digit from (1 to 100) is
58  85
Given k 0
Product of number digit from (1 to 80) is
10  20  30  40  50  60  70  80``````
``````/*
Scala program for
Find all numbers having digit product equal to k in 1 to N
*/
class Product()
{
def findProduct(num: Int): Int = {
var n: Int = num;
var product: Int = 1;
// Calculate digit product
while (n != 0 && product > 0)
{
product *= (n % 10);
n = n / 10;
}
return product;
}
def digitProduct(n: Int, k: Int): Unit = {
if (n < 0)
{
return;
}
var result: Boolean = false;
print("\n Given k " + k);
print("\n Product of number digit from (1 to " + n + ") is \n");
var i: Int = 0;
while (i <= n)
{
if (findProduct(i) == k)
{
print("  " + i);
result = true;
}
i += 1;
}
if (result == false)
{
// When no result
print(" None ");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Product = new Product();
// Test A
var k: Int = 40;
var n: Int = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
// Test B
k = 0;
n = 80;
/*
k = 0
n = 80
------------
1 ✕ 0 = 0
2 ✕ 0 = 0
3 ✕ 0 = 0
4 ✕ 0 = 0
5 ✕ 0 = 0
6 ✕ 0 = 0
7 ✕ 0 = 0
8 ✕ 0 = 0
------------
[10  20  30  40  50  60  70  80]
*/
}
}``````

Output

`````` Given k 40
Product of number digit from (1 to 100) is
58  85
Given k 0
Product of number digit from (1 to 80) is
10  20  30  40  50  60  70  80``````
``````/*
Swift 4 program for
Find all numbers having digit product equal to k in 1 to N
*/
class Product
{
func findProduct(_ num: Int) -> Int
{
var n: Int = num;
var product: Int = 1;
// Calculate digit product
while (n  != 0 && product > 0)
{
product *= (n % 10);
n = n / 10;
}
return product;
}
func digitProduct(_ n: Int, _ k: Int)
{
if (n < 0)
{
return;
}
var result: Bool = false;
print("\n Given k ", k, terminator: "");
print("\n Product of number digit from (1 to ", n ,") is ");
var i: Int = 0;
while (i <= n)
{
if (self.findProduct(i) == k)
{
print("  ", i, terminator: "");
result = true;
}
i += 1;
}
if (result == false)
{
// When no result
print(" None ", terminator: "");
}
}
}
func main()
{
// Test A
var k: Int = 40;
var n: Int = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
// Test B
k = 0;
n = 80;
/*
k = 0
n = 80
------------
1 ✕ 0 = 0
2 ✕ 0 = 0
3 ✕ 0 = 0
4 ✕ 0 = 0
5 ✕ 0 = 0
6 ✕ 0 = 0
7 ✕ 0 = 0
8 ✕ 0 = 0
------------
[10  20  30  40  50  60  70  80]
*/
}
main();``````

Output

`````` Given k  40
Product of number digit from (1 to  100 ) is
58   85
Given k  0
Product of number digit from (1 to  80 ) is
10   20   30   40   50   60   70   80``````
``````/*
Kotlin program for
Find all numbers having digit product equal to k in 1 to N
*/
class Product
{
fun findProduct(num: Int): Int
{
var n: Int = num;
var product: Int = 1;
// Calculate digit product
while (n != 0 && product > 0)
{
product *= (n % 10);
n = n / 10;
}
return product;
}
fun digitProduct(n: Int, k: Int): Unit
{
if (n < 0)
{
return;
}
var result: Boolean = false;
print("\n Given k " + k);
print("\n Product of number digit from (1 to " +
n + ") is \n");
var i: Int = 0;
while (i <= n)
{
if (this.findProduct(i) == k)
{
print("  " + i);
result = true;
}
i += 1;
}
if (result == false)
{
// When no result
print(" None ");
}
}
}
fun main(args: Array < String > ): Unit
{
// Test A
var k: Int = 40;
var n: Int = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
// Test B
k = 0;
n = 80;
/*
k = 0
n = 80
------------
1 ✕ 0 = 0
2 ✕ 0 = 0
3 ✕ 0 = 0
4 ✕ 0 = 0
5 ✕ 0 = 0
6 ✕ 0 = 0
7 ✕ 0 = 0
8 ✕ 0 = 0
------------
[10  20  30  40  50  60  70  80]
*/
}``````

Output

`````` Given k 40
Product of number digit from (1 to 100) is
58  85
Given k 0
Product of number digit from (1 to 80) is
10  20  30  40  50  60  70  80``````

Time Complexity

• For each number in the range, the `findDigitProduct` function takes O(log N) time, where N is the value of the number.
• Since we're iterating through the range of N numbers, the overall time complexity is O(N * log N).

This time complexity is acceptable for most practical cases but can become slow for very large values of N.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post