Given a number N, the task is to check if the all sub-numbers of this number have distinct digit product.
Note:
- An N digit number has N*(N+1)/2 sub-numbers. For example, all possible sub-numbers of 975 are 9, 7, 5, 97, 75, 975.
- Digit product of a number is product of its digits.
Examples:
Input : N = 324 Output : YES Sub-numbers of 324 are 3, 2, 4, 32, 24 and 324 and digit products are 3, 2, 4, 6, 8 and 24 respectively. All the digit products are different. Input : N = 323 Output : NO Sub-numbers of 323 are 3, 2, 3, 32, 23 and 323 and digit products are 3, 2, 3, 6, 6 and 18 respectively. Digit products 3 and 6 have occurred twice.
Approach :
- Make a digit array i.e., an array with its elements as digits of given number N.
- Now finding sub-numbers of N is similar to finding all possible subarrays of the digit array.
- Maintain a list of digit products of these subarrays.
- If any digit product has appeared more than once, print NO.
- Else print YES.
Below is the implementation of the above approach :
C++
// C++ program to check if all sub-numbers// have distinct Digit product#include<bits/stdc++.h>using namespace std;// Function to calculate product of// digits between given indexesint digitProduct(int digits[], int start, int end){ int pro = 1; for (int i = start; i <= end; i++) { pro *= digits[i]; } return pro;}// Function to check if all sub-numbers// have distinct Digit productbool isDistinct(int N){ string s = to_string(N); // Length of number N int len = s.length(); // Digit array int digits[len]; // set to maintain digit products unordered_set<int> products; for (int i = 0; i < len; i++) { digits[i] = s[i]-'0'; } // Finding all possible subarrays for (int i = 0; i < len; i++) { for (int j = i; j < len; j++) { int val = digitProduct(digits, i, j); if (products.find(val)!=products.end()) return false; else products.insert(val); } } return true;}// Driver codeint main(){ int N = 324; if (isDistinct(N)) cout << "YES"; else cout << "NO"; return 0;} |
Java
// Java program to check if all sub-numbers// have distinct Digit productimport java.io.*;import java.util.*;public class GFG { // Function to calculate product of // digits between given indexes static int digitProduct(int[] digits, int start, int end) { int pro = 1; for (int i = start; i <= end; i++) { pro *= digits[i]; } return pro; } // Function to check if all sub-numbers // have distinct Digit product static boolean isDistinct(int N) { String s = "" + N; // Length of number N int len = s.length(); // Digit array int[] digits = new int[len]; // List to maintain digit products ArrayList<Integer> products = new ArrayList<>(); for (int i = 0; i < len; i++) { digits[i] = Integer.parseInt("" + s.charAt(i)); } // Finding all possible subarrays for (int i = 0; i < len; i++) { for (int j = i; j < len; j++) { int val = digitProduct(digits, i, j); if (products.contains(val)) return false; else products.add(val); } } return true; } // Driver code public static void main(String args[]) { int N = 324; if (isDistinct(N)) System.out.println("YES"); else System.out.println("NO"); }} |
Python3
# Python3 program to check if all # sub-numbers have distinct Digit product # Function to calculate product of # digits between given indexes def digitProduct(digits, start, end): pro = 1 for i in range(start, end + 1): pro *= digits[i] return pro # Function to check if all sub-numbers # have distinct Digit product def isDistinct(N): s = str(N) # Length of number N length = len(s) # Digit array digits = [None] * length # set to maintain digit products products = set() for i in range(0, length): digits[i] = int(s[i]) # Finding all possible subarrays for i in range(0, length): for j in range(i, length): val = digitProduct(digits, i, j) if val in products: return False else: products.add(val) return True# Driver Codeif __name__ == "__main__": N = 324 if isDistinct(N) == True: print("YES") else: print("NO") # This code is contributed # by Rituraj Jain |
C#
// C# program to check if all sub-numbers// have distinct Digit productusing System;using System.Collections;using System.Collections.Generic;public class GFG { // Function to calculate product of // digits between given indexes static int digitProduct(int[] digits, int start, int end) { int pro = 1; for (int i = start; i <= end; i++) { pro *= digits[i]; } return pro; } // Function to check if all sub-numbers // have distinct Digit product static bool isDistinct(int N) { string s = N.ToString(); // Length of number N int len = s.Length; // Digit array int[] digits = new int[len]; // List to maintain digit products ArrayList products = new ArrayList(); for (int i = 0; i < len; i++) { digits[i] = s[i]-'0'; } // Finding all possible subarrays for (int i = 0; i < len; i++) { for (int j = i; j < len; j++) { int val = digitProduct(digits, i, j); if (products.Contains(val)) return false; else products.Add(val); } } return true; } // Driver code public static void Main() { int N = 324; if (isDistinct(N)) Console.WriteLine("YES"); else Console.WriteLine("NO"); }}// This code is contributed by ihritik |
PHP
<?PHP// PHP program to check if all sub-numbers// have distinct Digit product// Function to calculate product of// digits between given indexesfunction digitProduct($digits, $start, $end){ $pro = 1; for ($i = $start; $i <= $end; $i++) { $pro *= $digits[$i]; } return $pro;}// Function to check if all sub-numbers// have distinct Digit productfunction isDistinct($N){ $s ="$N"; // Length of number N $len = sizeof($s); // Digit array $digits=array(); // to maintain digit products $products=array(); for ($i = 0; $i < $len; $i++) { $digits[$i] = $s[$i]-'0'; } // Finding all possible subarrays for ($i = 0; $i < $len; $i++) { for ($j = $i; $j < $len; $j++) { $val = digitProduct($digits, $i, $j); if (in_array($val,$products)) return false; else array_push($products,$val); } } return true;}// Driver code$N = 324;if (isDistinct($N)) echo "YES";else echo "NO"; // This code is contributed by ihritik ?> |
Javascript
<script>// Javascript program to check if all sub-numbers// have distinct Digit product// Function to calculate product of// digits between given indexesfunction digitProduct(digits, start, end){ let pro = 1; for (let i = start; i <= end; i++) { pro *= digits[i]; } return pro;}// Function to check if all sub-numbers// have distinct Digit productfunction isDistinct(N){ let s ="N"; // Length of number N let len = s.length; // Digit array let digits = new Array(); // to maintain digit products let products = new Array(); for (let i = 0; i < len; i++) { digits[i] = s[i].charCodeAt(0) - '0'.charCodeAt(0); } // Finding all possible subarrays for (let i = 0; i < len; i++) { for (let j = i; j < len; j++) { let val = digitProduct(digits, i, j); if (products.includes(val)) return false; else products.push(val); } } return true;}// Driver codelet N = 324;if (isDistinct(N)) document.write("YES");else document.write("NO"); // This code is contributed by gfgking</script> |
YES
- Complexity Analysis:
- Time Complexity: O(|N|2)
- Auxiliary Space: O(|N|2)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More here on that Topic: geeksforgeeks.org/check-if-all-sub-numbers-have-distinct-digit-product/ […]
… [Trackback]
[…] Read More here on that Topic: geeksforgeeks.org/check-if-all-sub-numbers-have-distinct-digit-product/ […]