Given an integer N, the task is to check if the product of every consecutive set of digits is distinct or not.
Examples:
Input: N = 234
Output: Yes
Set Product {2} 2 {2, 3} 2 * 3 = 6 {2, 3, 4} 2 * 3 * 4 = 24 {3} 3 {3, 4} 3 * 4 = 12 {4} 4 All the products are distinct.
Input: N = 1234
Output: No
Set {1, 2} and {2} both the same product i.e. 2.
Approach: Store the product of digits of every contiguous subsequence in a set. If the product to be inserted is already present in the set at any point then the answer is “No” else all the product are distinct in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if the product// of every digit of a contiguous subsequence// is distinctbool productsDistinct(int N){ // To store the given number as a string string s = ""; // Append all the digits // starting from the end while (N) { s += (char)(N % 10 + '0'); N /= 10; } // Reverse the string to get // the original number reverse(s.begin(), s.end()); // Store size of the string int sz = s.size(); // Set to store product of // each contiguous subsequence set<int> se; // Find product of every // contiguous subsequence for (int i = 0; i < sz; i++) { int product = 1; for (int j = i; j < sz; j++) { product *= (int)(s[j] - '0'); // If current product already // exists in the set if (se.find(product) != se.end()) return false; else se.insert(product); } } return true;}// Driver codeint main(){ int N = 2345; if (productsDistinct(N)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Function that returns true if // the product of every digit of a // contiguous subsequence is distinctstatic boolean productsDistinct(int N){ // To store the given number // as a string String s = ""; // Append all the digits // starting from the end while (N > 0) { s += (char)(N % 10 + '0'); N /= 10; } // Reverse the string to get // the original number s = reverse(s); // Store size of the string int sz = s.length(); // Set to store product of // each contiguous subsequence HashSet<Integer> se = new HashSet<Integer>(); // Find product of every // contiguous subsequence for (int i = 0; i < sz; i++) { int product = 1; for (int j = i; j < sz; j++) { product *= (int)(s.charAt(j) - '0'); // If current product already // exists in the set if (se.contains(product)) return false; else se.add(product); } } return true;}static String reverse(String input){ char[] a = input.toCharArray(); int l, r; r = a.length - 1; for (l = 0; l < r; l++, r--) { // Swap values of l and r char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);} // Driver codepublic static void main(String[] args) { int N = 2345; if (productsDistinct(N)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed // by PrinciRaj1992 |
Python3
# Python 3 implementation of the approach# Function that returns true if the product# of every digit of a contiguous subsequence# is distinctdef productsDistinct(A): A = str(A) n = len(A) hs = set() for i in range(n): prod = 1 for j in range(i, n): prod = prod * int(A[j]) if(prod in hs): return False else: hs.add(prod) return True# Driver codeif __name__ == '__main__': N = 2345 if (productsDistinct(N)): print("Yes") else: print("No")# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG {// Function that returns true if // the product of every digit of a // contiguous subsequence is distinctstatic Boolean productsDistinct(int N){ // To store the given number // as a string String s = ""; // Append all the digits // starting from the end while (N > 0) { s += (char)(N % 10 + '0'); N /= 10; } // Reverse the string to get // the original number s = reverse(s); // Store size of the string int sz = s.Length; // Set to store product of // each contiguous subsequence HashSet<int> se = new HashSet<int>(); // Find product of every // contiguous subsequence for (int i = 0; i < sz; i++) { int product = 1; for (int j = i; j < sz; j++) { product *= (int)(s[j] - '0'); // If current product already // exists in the set if (se.Contains(product)) return false; else se.Add(product); } } return true;}static String reverse(String input){ char[] a = input.ToCharArray(); int l, r; r = a.Length - 1; for (l = 0; l < r; l++, r--) { // Swap values of l and r char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("",a);} // Driver codepublic static void Main(String[] args) { int N = 2345; if (productsDistinct(N)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if the product// of every digit of a contiguous subsequence// is distinct// Javascript implementation of the approach// Function that returns true if the product// of every digit of a contiguous subsequence// is distinctfunction productsDistinct(N) { // To store the given number as a string const s = N.toString(); // Store size of the string const sz = s.length; // Set to store product of // each contiguous subsequence const products = new Set(); // Find product of every // contiguous subsequence for (let i = 0; i < sz; i++) { let product = 1; for (let j = i; j < sz; j++) { product *= Number(s[j]); // If current product already exists in the set if (products.has(product)) return false; else products.add(product); } } return true;}// Driver codeconst N = 2345;if (productsDistinct(N)) document.write("Yes");else document.write("No");</script> |
Output:
Yes
Time Complexity: O((log10N)2*log(log10N))
Auxiliary Space: O((log10N)2)
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!
