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)
	{
		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.

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.

New Comment





Categories
Relative Post