Given a positive integer N, the task is to find the number of all N-digit numbers whose adjacent digits have equal Greatest Common Divisor(GCD).
Examples:
Input: N = 2
Output: 90
Explanation:
All 2-digit numbers satisfy the condition as there is only one pair of digits and there are 90 2-digit numbers.Input: N = 3
Output: 457
Naive Approach: The simplest approach to solve the given problem is to generate all possible N-digit numbers and count those numbers whose adjacent digits have equal GCD. After checking for all the numbers, print the value of the count as the resultant total count of numbers.
Time Complexity: O(N *10N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using Dynamic Programming because the above problem has Overlapping subproblems and an Optimal substructure. The subproblems can be stored in dp[][][] table memoization where dp[index][prev][gcd] stores the answer from the indexth position till the end, where prev is used to store the previous digit of the number and gcd is the GCD between existing adjacent digits in the number. Follow the steps below to solve the problem:
- Initialize a global multidimensional array dp[100][10][10] with all values as -1 that stores the result of each recursive call.
- Define a recursive function, say countOfNumbers(index, prev, gcd, N) and performing the following steps:
- If the value of the index as (N + 1), then return 1 as a valid N-digit number has been formed.
- If the result of the state dp[index][prev][gcd] is already computed, return this value dp[index][prev][gcd].
- If the current index is 1, then any digit from [1- 9] can be placed.
- If the current index is greater than 1, any digit from [0-9] can be placed.
- If the index is greater than 2, a digit can be placed if the gcd of the current digit and the previous digit is equal to the GCD of already existing adjacent digits.
- After making a valid placement of digits, recursively call the countOfNumbers function for (index + 1).
- Return the sum of all possible valid placements of digits as the answer.
- Print the value returned by the function countOfNumbers(1, 0, 0, N) as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int dp[100][10][10];// Recursive function to find the count// of all the N-digit numbers whose// adjacent digits having equal GCDint countOfNumbers(int index, int prev, int gcd, int N){ // If index is N+1 if (index == N + 1) return 1; int& val = dp[index][prev][gcd]; // If the state has already // been computed if (val != -1) return val; // Stores the total count of all // N-digit numbers val = 0; // If index = 1, any digit from // [1-9] can be placed. // If N = 0, 0 can be placed as well if (index == 1) { for (int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // Update the value val val += countOfNumbers( index + 1, digit, gcd, N); } } // If index is 2, then any digit // from [0-9] can be placed else if (index == 2) { for (int digit = 0; digit <= 9; ++digit) { val += countOfNumbers( index + 1, digit, __gcd(prev, digit), N); } } // Otherwise any digit from [0-9] can // be placed if the GCD of current // and previous digit is gcd else { for (int digit = 0; digit <= 9; ++digit) { // Check if GCD of current // and previous digit is gcd if (__gcd(digit, prev) == gcd) { val += countOfNumbers( index + 1, digit, gcd, N); } } } // Return the total count return val;}// Function to find the count of all// the N-digit numbers whose adjacent// digits having equal GCDint countNumbers(int N){ // Initialize dp array with -1 memset(dp, -1, sizeof dp); // Function Call to find the // resultant count return countOfNumbers(1, 0, 0, N);}// Driver Codeint main(){ int N = 2; cout << countNumbers(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{static int[][][] dp = new int[100][10][10];static int _gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return _gcd(a-b, b); return _gcd(a, b-a); }// Recursive function to find the count// of all the N-digit numbers whose// adjacent digits having equal GCDstatic int countOfNumbers(int index, int prev, int gcd, int N){ // If index is N+1 if (index == N + 1) return 1; int val = dp[index][prev][gcd]; // If the state has already // been computed if (val != -1) return val; // Stores the total count of all // N-digit numbers val = 0; // If index = 1, any digit from // [1-9] can be placed. // If N = 0, 0 can be placed as well if (index == 1) { for (int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // Update the value val val += countOfNumbers( index + 1, digit, gcd, N); } } // If index is 2, then any digit // from [0-9] can be placed else if (index == 2) { for (int digit = 0; digit <= 9; ++digit) { val += countOfNumbers( index + 1, digit, _gcd(prev, digit), N); } } // Otherwise any digit from [0-9] can // be placed if the GCD of current // and previous digit is gcd else { for (int digit = 0; digit <= 9; ++digit) { // Check if GCD of current // and previous digit is gcd if (_gcd(digit, prev) == gcd) { val += countOfNumbers( index + 1, digit, gcd, N); } } } // Return the total count return val;}// Function to find the count of all// the N-digit numbers whose adjacent// digits having equal GCDstatic int countNumbers(int N){ int i, j, k; // Initialize dp array with -1 for(i = 0; i < 100; i++) { for(j = 0; j < 10; j++) { for(k = 0; k < 10; k++) { dp[i][j][k] = -1; } } } // Function Call to find the // resultant count return countOfNumbers(1, 0, 0, N);} public static void main(String[] args) { int N = 2; System.out.println(countNumbers(N)); }}// This code is contributed by target_2 |
Python3
# Python3 program for the above approachdp = [[[-1 for i in range(10)] for j in range(10)] for k in range(100)]from math import gcd# Recursive function to find the count# of all the N-digit numbers whose# adjacent digits having equal GCDdef countOfNumbers(index, prev, gcd1, N): # If index is N+1 if (index == N + 1): return 1 val = dp[index][prev][gcd1] # If the state has already # been computed if (val != -1): return val # Stores the total count of all # N-digit numbers val = 0 # If index = 1, any digit from # [1-9] can be placed. # If N = 0, 0 can be placed as well if (index == 1): digit = 0 if N == 1 else 1 while(digit <= 9): # Update the value val val += countOfNumbers(index + 1, digit, gcd1, N) digit += 1 # If index is 2, then any digit # from [0-9] can be placed elif (index == 2): for digit in range(10): val += countOfNumbers(index + 1, digit, gcd(prev, digit), N) # Otherwise any digit from [0-9] can # be placed if the GCD of current # and previous digit is gcd else: for digit in range(10): # Check if GCD of current # and previous digit is gcd if (gcd(digit, prev) == gcd): val += countOfNumbers(index + 1, digit, gcd1, N) # Return the total count return val# Function to find the count of all# the N-digit numbers whose adjacent# digits having equal GCDdef countNumbers(N): # Function Call to find the # resultant count return countOfNumbers(1, 0, 0, N)# Driver Codeif __name__ == '__main__': N = 2 print(countNumbers(N))# This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;public class GFG{ static int[,,] dp = new int[100, 10, 10]; static int _gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return _gcd(a-b, b); return _gcd(a, b-a); } // Recursive function to find the count // of all the N-digit numbers whose // adjacent digits having equal GCD static int countOfNumbers(int index, int prev, int gcd, int N) { // If index is N+1 if (index == N + 1) return 1; int val = dp[index,prev,gcd]; // If the state has already // been computed if (val != -1) return val; // Stores the total count of all // N-digit numbers val = 0; // If index = 1, any digit from // [1-9] can be placed. // If N = 0, 0 can be placed as well if (index == 1) { for (int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // Update the value val val += countOfNumbers( index + 1, digit, gcd, N); } } // If index is 2, then any digit // from [0-9] can be placed else if (index == 2) { for (int digit = 0; digit <= 9; ++digit) { val += countOfNumbers( index + 1, digit, _gcd(prev, digit), N); } } // Otherwise any digit from [0-9] can // be placed if the GCD of current // and previous digit is gcd else { for (int digit = 0; digit <= 9; ++digit) { // Check if GCD of current // and previous digit is gcd if (_gcd(digit, prev) == gcd) { val += countOfNumbers( index + 1, digit, gcd, N); } } } // Return the total count return val; } // Function to find the count of all // the N-digit numbers whose adjacent // digits having equal GCD static int countNumbers(int N) { int i, j, k; // Initialize dp array with -1 for(i = 0; i < 100; i++) { for(j = 0; j < 10; j++) { for(k = 0; k < 10; k++) { dp[i,j,k] = -1; } } } // Function Call to find the // resultant count return countOfNumbers(1, 0, 0, N); } // Driver code static public void Main () { int N = 2; Console.Write(countNumbers(N)); }}// This code is contributed by shubham singh |
Javascript
<script>// Javascript program for the above approachlet dp = new Array(100).fill(0).map(() => new Array(10).fill(0).map(() => new Array(10).fill(-1)));// Recursive function to find the count// of all the N-digit numbers whose// adjacent digits having equal GCDfunction countOfNumbers(index, prev, gcd, N){ // If index is N+1 if (index == N + 1) return 1; let val = dp[index][prev][gcd]; // If the state has already // been computed if (val != -1) return val; // Stores the total count of all // N-digit numbers val = 0; // If index = 1, any digit from // [1-9] can be placed. // If N = 0, 0 can be placed as well if (index == 1) { for (let digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // Update the value val val += countOfNumbers( index + 1, digit, gcd, N); } } // If index is 2, then any digit // from [0-9] can be placed else if (index == 2) { for (let digit = 0; digit <= 9; ++digit) { val += countOfNumbers( index + 1, digit, __gcd(prev, digit), N); } } // Otherwise any digit from [0-9] can // be placed if the GCD of current // and previous digit is gcd else { for (let digit = 0; digit <= 9; ++digit) { // Check if GCD of current // and previous digit is gcd if (__gcd(digit, prev) == gcd) { val += countOfNumbers( index + 1, digit, gcd, N); } } } // Return the total count return val;}// Function to find the count of all// the N-digit numbers whose adjacent// digits having equal GCDfunction countNumbers(N){ // Function Call to find the // resultant count return countOfNumbers(1, 0, 0, N);}function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); } let N = 2;document.write(countNumbers(N));// This code is contributed by gfgking.</script> |
Output:
90
Time Complexity: O(N * 1000)
Auxiliary Space: O(N * 10 * 10)
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!
