Given an array arr[], the task is to count the pairs in the array such that arr[i]/arr[j] is a Pandigital Fraction.
A fraction N/D is called a Pandigital Fraction if the fraction
contains all the digits from 0 to 9.
contains all the digits from 0 to 9. Examples:
Input: arr = [ 12345, 67890, 123, 4567890 ]
Output: 3
Explanation:
The fractions are 12345/67890, 12345/4567890, and 123/4567890Input: arr = [ 12345, 6789 ]
Output: 0
Approach: The idea is to iterate over every possible pair of the array using two nested loops and for every pair concatenate arr[i] and arr[j] into a single number and check if the concatenation of arr[i] and arr[j] is a Pandigital number in base 10 then increment the count.
Below is the implementation of the above approach:
C++
#include <cmath> #include <cstring> #include <iostream> using namespace std; // Function to concatenate two numbers into one long long numConcat(long long num1, long long num2) { // Find number of digits in num2 int digits = to_string(num2).length(); // Add zeroes to the end of num1 num1 = num1 * pow(10, digits); // Add num2 to num1 num1 += num2; return num1; } // Return true if n is pandigital else return false. int checkPanDigital(long long n) { string str = to_string(n); int b = 10; // Checking length is less than base if (str.length() < b) { return 0; } int hash[b]; memset(hash, 0, sizeof(hash)); // Traversing each digit of the number for (int i = 0; i < str.length(); i++) { // If digit is integer if (str[i] >= '0' && str[i] <= '9') { hash[str[i] - '0'] = 1; } // If digit is alphabet else if (str[i] - 'A' <= b - 11) { hash[str[i] - 'A' + 10] = 1; } } // Checking hash array, if any index is unmarked for (int i = 0; i < b; i++) { if (hash[i] == 0) { return 0; } } return 1; } // Returns true if N is a Pandigital Fraction Number bool isPandigitalFraction(long long N, long long D) { long long join = numConcat(N, D); return checkPanDigital(join) == 1; } // Returns number pandigital fractions in the array int countPandigitalFraction(long long v[], int n) { // iterate over all pair of strings int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (isPandigitalFraction(v[i], v[j])) { count++; } } } return count; } // Driver Code int main() { long long arr[] = { 12345, 67890, 123, 4567890 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countPandigitalFraction(arr, n) << endl; return 0; } |
Java
import java.util.Arrays; public class Main { // Function to concatenate two numbers into one static long numConcat(long num1, long num2) { // Find number of digits in num2 int digits = Long.toString(num2).length(); // Add zeroes to the end of num1 num1 = num1 * (long) Math.pow(10, digits); // Add num2 to num1 num1 += num2; return num1; } // Return true if n is pandigital else return false. static int checkPanDigital(long n) { String str = Long.toString(n); int b = 10; // Checking length is less than base if (str.length() < b) { return 0; } int[] hash = new int[b]; Arrays.fill(hash, 0); // Traversing each digit of the number for (int i = 0; i < str.length(); i++) { // If digit is integer if (str.charAt(i) >= '0' && str.charAt(i) <= '9') { hash[str.charAt(i) - '0'] = 1; } // If digit is alphabet else if (str.charAt(i) - 'A' <= b - 11) { hash[str.charAt(i) - 'A' + 10] = 1; } } // Checking hash array, if any index is unmarked for (int i = 0; i < b; i++) { if (hash[i] == 0) { return 0; } } return 1; } // Returns true if N is a Pandigital Fraction Number static boolean isPandigitalFraction(long N, long D) { long join = numConcat(N, D); return checkPanDigital(join) == 1; } // Returns number pandigital fractions in the array static int countPandigitalFraction(long[] v, int n) { // iterate over all pair of strings int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (isPandigitalFraction(v[i], v[j])) { count++; } } } return count; } // Driver Code public static void main(String[] args) { long[] arr = {12345, 67890, 123, 4567890}; int n = arr.length; System.out.println(countPandigitalFraction(arr, n)); } } |
Python3
# Python3 implementation of the # above approach import math # Function to concatenate # two numbers into one def numConcat(num1, num2): # Find number of digits in num2 digits = len(str(num2)) # Add zeroes to the end of num1 num1 = num1 * (10**digits) # Add num2 to num1 num1 += num2 return num1 # Return true if n is pandigit # else return false. def checkPanDigital(n): n = str(n) b = 10 # Checking length is # less than base if (len(n) < b): return 0; hash = [0] * b; # Traversing each digit # of the number. for i in range(len(n)): # If digit is integer if (n[i] >= '0' and \ n[i] <= '9'): hash[ord(n[i]) - ord('0')] = 1; # If digit is alphabet elif (ord(n[i]) - ord('A') <= \ b - 11): hash[ord(n[i]) - \ ord('A') + 10] = 1; # Checking hash array, if any index is # unmarked. for i in range(b): if (hash[i] == 0): return 0; return 1; # Returns true if N is a # Pandigital Fraction Number def isPandigitalFraction(N, D): join = numConcat(N, D) return checkPanDigital(join) # Returns number pandigital fractions # in the array def countPandigitalFraction(v, n) : # iterate over all # pair of strings count = 0 for i in range(0, n) : for j in range (i + 1, n) : if (isPandigitalFraction(v[i], v[j])) : count = count + 1 return count # Driver Code if __name__ == "__main__": arr = [ 12345, 67890, 123, 4567890 ] n = len(arr) print(countPandigitalFraction(arr, n)) |
C#
// C# code to implement the approach using System; using System.Linq; class GFG { static void Main(string[] args) { // Input array of integers long[] arr = { 12345, 67890, 123, 4567890 }; int n = arr.Length; // Count the number of pandigital fractions int count = CountPandigitalFraction(arr, n); Console.WriteLine(count); } // Function to concatenate two numbers into one static long NumConcat(long num1, long num2) { // Find number of digits in num2 int digits = num2.ToString().Length; // Add zeroes to the end of num1 num1 *= (long)Math.Pow(10, digits); // Add num2 to num1 num1 += num2; return num1; } // Return true if n is pandigital else return false. static bool CheckPanDigital(long n) { string str = n.ToString(); int b = 10; // Checking length is less than base if (str.Length < b) { return false; } int[] hash = new int[b]; // Traversing each digit of the number foreach(char ch in str) { // If digit is integer if (ch >= '0' && ch <= '9') { hash[ch - '0'] = 1; } // If digit is alphabet else if (ch - 'A' <= b - 11) { hash[ch - 'A' + 10] = 1; } } // Checking hash array, if any index is unmarked foreach(int val in hash) { if (val == 0) { return false; } } return true; } // Returns true if N is a Pandigital Fraction Number static bool IsPandigitalFraction(long N, long D) { long join = NumConcat(N, D); return CheckPanDigital(join); } // Returns number pandigital fractions in the array static int CountPandigitalFraction(long[] v, int n) { // Iterate over all pairs of integers int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (IsPandigitalFraction(v[i], v[j])) { count++; } } } return count; } } |
Javascript
// Function to concatenate two numbers into one function numConcat(num1, num2) { // Find number of digits in num2 let digits = num2.toString().length; // Add zeroes to the end of num1 num1 = num1 * Math.pow(10, digits); // Add num2 to num1 num1 += num2; return num1; } // Return true if n is pandigital else return false. function checkPanDigital(n) { n = n.toString(); let b = 10; // Checking length is less than base if (n.length < b) { return 0; } let hash = new Array(b).fill(0); // Traversing each digit of the number for (let i = 0; i < n.length; i++) { // If digit is integer if (n[i] >= '0' && n[i] <= '9') { hash[n.charCodeAt(i) - '0'.charCodeAt(0)] = 1; } // If digit is alphabet else if (n.charCodeAt(i) - 'A'.charCodeAt(0) <= b - 11) { hash[n.charCodeAt(i) - 'A'.charCodeAt(0) + 10] = 1; } } // Checking hash array, if any index is unmarked for (let i = 0; i < b; i++) { if (hash[i] == 0) { return 0; } } return 1; } // Returns true if N is a Pandigital Fraction Number function isPandigitalFraction(N, D) { let join = numConcat(N, D); return checkPanDigital(join); } // Returns number pandigital fractions in the array function countPandigitalFraction(v, n) { // iterate over all pair of strings let count = 0; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { if (isPandigitalFraction(v[i], v[j])) { count++; } } } return count; } // Driver Code let arr = [12345, 67890, 123, 4567890]; let n = arr.length; console.log(countPandigitalFraction(arr, n)); |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(1), As constant extra space is used.
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!
