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
- Loop through the range from 1 to N.
- For each number, calculate its digit product.
- 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
- The
findDigitProduct
function calculates the digit product of a given number. - The
digitProductInRange
function iterates through the range from 1 to N. - For each number, it calls the
findDigitProduct
function to calculate the digit product. - If the calculated digit product matches K, the number is added to the
result
list. - 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)
{
Product task = new Product();
// Test A
int k = 40;
int n = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
task.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]
*/
task.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
// 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()
{
Product *task = new Product();
// Test A
int k = 40;
int n = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
task->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]
*/
task->digitProduct(n, k);
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)
{
Product task = new Product();
// Test A
int k = 40;
int n = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
task.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]
*/
task.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
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()
{
$task = new Product();
// Test A
$k = 40;
$n = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
$task->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]
*/
$task->digitProduct($n, $k);
}
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()
{
var task = new Product();
// Test A
var k = 40;
var n = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
task.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]
*/
task.digitProduct(n, k);
}
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() :
task = Product()
# Test A
k = 40
n = 100
# k = 40
# n = 100
# ----------
# 5 ✕ 8 = 40
# 8 ✕ 5 = 40
# -----------
# [58 84]
task.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]
task.digitProduct(n, k)
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()
task = Product.new()
# Test A
k = 40
n = 100
# k = 40
# n = 100
# ----------
# 5 ✕ 8 = 40
# 8 ✕ 5 = 40
# -----------
# [58 84]
task.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]
task.digitProduct(n, k)
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]
*/
task.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]
*/
task.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
/*
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()
{
let task: Product = Product();
// Test A
var k: Int = 40;
var n: Int = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
task.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]
*/
task.digitProduct(n, k);
}
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
{
val task: Product = Product();
// Test A
var k: Int = 40;
var n: Int = 100;
/*
k = 40
n = 100
----------
5 ✕ 8 = 40
8 ✕ 5 = 40
-----------
[58 84]
*/
task.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]
*/
task.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
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.
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.
New Comment