Given an integer N, the task to print the count numbers from the range [1, N] whose adjacent digits are not co-prime.
Two numbers A and B are said to be co-prime if the GCD of the two numbers is 1.
Examples:
Input: N = 30
Output: 15
Explanation: The numbers from [1, 30] which have non co-prime adjacent digits are {1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 24, 26, 28, 30}.Input: N = 10000
Output: 1361
Naive Approach: The simplest approach to solve the problem is to iterate over the range 1 to N, and for each number from the range, check if GCD of their adjacent digits is equal to 1 or not and update the answer accordingly.
Time Complexity: O(NlogN)
Auxiliary Space: O(1).
Efficient Approach: The above approach can also be optimized by using Dynamic Programming because it has overlapping subproblems and optimal substructure. The subproblems can be stored in dp[][][][] table using memoization where dp[i][bound][prev][allZeros] stores the answer from ‘i’th position to the end where bound is a boolean variable which ensures the number does not exceed N, prev stores the previous digit selected, allZeros is a boolean variable used to check if the all the digits selected till now are 0 or not.
- Define a recursive function noncoprimeCount(i, bound, prev, allZeros) by performing the following steps.
- Convert the limit N to a string so that it will be iterated only over the length of the string and not the actual limit of N.
- Check the base case, which is if the entire string is traversed completely (i == N), then return 1 as a valid number in range [1, N] has been constructed.
- If the result of the state dp[i][bound][previous][allZeros] is already computed, return the value stored in dp[i][bound][previous][allZeros].
- At the current position ‘i’ any number from [0, 9] can be placed. While placing a digit, ensure the number does not exceed ‘R’ with the help of the variable bound. Also check if the GCD of the current digit and the previous digit(which is stored in prev) is greater than 1.There are two edge cases here:
- If the current index is 0, place any digit in the first position.
- If all the digits filled until now are zeros, i.e., allZeros is true, then it is valid to place 1 in the current position despite GCD(0, 1) = 1 as it is the most significant digit. Then set the allZeros to false.
- After placing a valid digit in the current position, recursively call the noncoprimeCount function for the element at index (i + 1).
- Return the sum of all possible valid placements of digits as the answer.
- After completing the above steps, print the value of nocoprimeCount(0) as the result.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;int dp[100][2][10][2];// Function to count numbers whose// adjacent digits are not co-primeint noncoprimeCount(int i, int N, string& S, bool bound, int prev, bool allZeros){ // Base Case // If the entire string // is traversed if (i == N) return 1; int& val = dp[i][bound][prev][allZeros]; // If the subproblem has // already been computed if (val != -1) return val; int cnt = 0; for (int j = 0; j <= (bound ? (S[i] - '0') : 9); ++j) { // A digit can be placed at // the current position if: // GCD of current and previous // digits is not equal to 1 if ((__gcd(j, prev) != 1) // Current position is 0 || (i == 0) // All encountered digits // until now are 0s || allZeros == 1) { cnt += noncoprimeCount( i + 1, N, S, bound & (j == (S[i] - '0')), j, allZeros & (j == 0)); } } // Return the total // possible valid numbers return val = cnt;}// Function to count numbers whose// adjacent digits are not co-primevoid noncoprimeCountUtil(int R){ // Convert R to string. string S = to_string(R); // Length of string int N = S.length(); // Initialize dp array with -1 memset(dp, -1, sizeof dp); // Function call with initial values of // bound, allZeros, previous as 1, 1, 0 int ans = noncoprimeCount(0, N, S, 1, 0, 1); // Subtract 1 from the answer, as 0 is included cout << ans - 1 << endl;}// Driver Codeint main(){ // Input int N = 10000; // Function call noncoprimeCountUtil(N); return 0;} |
Java
import java.util.*;class GFG{static int [][][][]dp = new int[100][2][10][2];static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); }// Function to count numbers whose// adjacent digits are not co-primestatic int noncoprimeCount(int i, int N, char []S, int bound, int prev, int allZeros){ // Base Case // If the entire String // is traversed if (i == N) return 1; int val = dp[i][bound][prev][allZeros]; // If the subproblem has // already been computed if (val != -1) return val; int cnt = 0; for (int j = 0; j <= (bound!=0 ? (S[i] - '0') : 9); ++j) { // A digit can be placed at // the current position if: // GCD of current and previous // digits is not equal to 1 if ((__gcd(j, prev) != 1) // Current position is 0 || (i == 0) // All encountered digits // until now are 0s || allZeros == 1) { cnt += noncoprimeCount( i + 1, N, S, bound!=0 & (j == (S[i] - '0'))?1:0, j, (allZeros!=0 & (j == 0))?1:0); } } // Return the total // possible valid numbers return val = cnt;}// Function to count numbers whose// adjacent digits are not co-primestatic void noncoprimeCountUtil(int R){ // Convert R to String. String S = String.valueOf(R); // Length of String int N = S.length(); // Initialize dp array with -1 for (int i = 0; i < 100; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 10; k++) for (int l = 0; l < 2; l++) dp[i][j][k][l] = -1; // Function call with initial values of // bound, allZeros, previous as 1, 1, 0 int ans = noncoprimeCount(0, N, S.toCharArray(), 1, 0, 1); // Subtract 1 from the answer, as 0 is included System.out.print(ans - 1 +"\n");}// Driver Codepublic static void main(String[] args){ // Input int N = 10000; // Function call noncoprimeCountUtil(N);}}// This code contributed by shikhasingrajput |
Python3
# importing "math" for mathematical operationsimport mathdp = []# Function to count numbers whose# adjacent digits are not co-primedef noncoprimeCount(i, N, S, bound, prev, allZeros): # Base Case # If the entire string # is traversed if (i == N): return 1 val = dp[i][bound][prev][allZeros] # if the subproblem has # already been computed if (val != -1): return val cnt = 0 limit = 9 if(bound != 0): limit = ord(S[i])-48 limit += 1 for j in range(0, limit): # A digit can be placed at # the current position if: # GCD of current and previous # digits is not equal to 1 if ((math.gcd(j, prev) != 1) # Current position is 0 or (i == 0) # All encountered digits # until now are 0s or allZeros == 1): cnt += noncoprimeCount( i + 1, N, S, bound & (j == (ord(S[i]) - 48)), j, allZeros & (j == 0)) # Return the total # possible valid numbers val = cnt return val# Function to count numbers whose# adjacent digits are not co-primedef noncoprimeCountUtil(R): # Convert R to string. S = str(R) # Length of string N = len(S) # Initialize dp array with -1 for i in range(0, 100): dp.append([]) for j in range(0, 2): dp[i].append([]) for k in range(0, 10): dp[i][j].append([]) for l in range(0, 2): dp[i][j][k].append(-1) # Function call with initial values of # bound, allZeros, previous as 1, 1, 0 ans = noncoprimeCount(0, N, S, 1, 0, 1) # Subtract 1 from the answer, as 0 is included print(ans-1)# Driver Code# InputN = 10000# Function callnoncoprimeCountUtil(N)# This code is contributed by rj13to. |
C#
using System;class GFG{static int[,,,] dp = new int[100, 2, 10, 2];static int __gcd(int a, int b){ return b == 0 ? a : __gcd(b, a % b);}// Function to count numbers whose// adjacent digits are not co-primestatic int noncoprimeCount(int i, int N, char[] S, int bound, int prev, int allZeros) { // Base Case // If the entire String // is traversed if (i == N) return 1; int val = dp[i, bound, prev, allZeros]; // If the subproblem has // already been computed if (val != -1) return val; int cnt = 0; for(int j = 0; j <= (bound != 0 ? (S[i] - '0') : 9); ++j) { // A digit can be placed at // the current position if: // GCD of current and previous // digits is not equal to 1 if ((__gcd(j, prev) != 1) // Current position is 0 || (i == 0) // All encountered digits // until now are 0s || allZeros == 1) { cnt += noncoprimeCount(i + 1, N, S, bound != 0 & (j == (S[i] - '0')) ? 1 : 0, j, (allZeros != 0 & (j == 0)) ? 1 : 0); } } // Return the total // possible valid numbers return val = cnt;}// Function to count numbers whose// adjacent digits are not co-primestatic void noncoprimeCountUtil(int R) { // Convert R to String. String S = String.Join("", R); // Length of String int N = S.Length; // Initialize dp array with -1 for(int i = 0; i < 100; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 10; k++) for(int l = 0; l < 2; l++) dp[i, j, k, l] = -1; // Function call with initial values of // bound, allZeros, previous as 1, 1, 0 int ans = noncoprimeCount(0, N, S.ToCharArray(), 1, 0, 1); // Subtract 1 from the answer, as 0 is included Console.Write(ans - 1 + "\n");}// Driver Codepublic static void Main(String[] args){ // Input int N = 10000; // Function call noncoprimeCountUtil(N);}}// This code is contributed by umadevi9616 |
Javascript
// Javascript code to implement the approach var dp = new Array(100) // Function for converting // bool to Int (True -> 1, False -> 0) function boolToInt(x){ if(x){ return 1 } return 0 } // Function for finding gcd of two numbers function __gcd(x, y) { x = Math.abs(x); y = Math.abs(y); while(y) { var t = y; y = x % y; x = t; } return x; } // Function to count numbers whose // adjacent digits are not co-prime function noncoprimeCount(i, N, S, bound, prev, allZeros) { // Base Case // If the entire string // is traversed if (i == N){ return 1 } var val = dp[i][bound][prev][allZeros] // If the subproblem has // already been computed if (val != -1){ return val } var cnt = 0; for (let j = 0 ; j <= (bound == 1 ? (S[i] - '0') : 9) ; ++j) { // A digit can be placed at // the current position if: // GCD of current and previous // digits is not equal to 1 if ((__gcd(j, prev) != 1) // Current position is 0 || (i == 0) // All encountered digits // until now are 0s || allZeros == 1) { cnt += noncoprimeCount(i + 1, N, S, bound & boolToInt(j == (S[i] - '0')), j, allZeros & boolToInt(j == 0)); } } dp[i][bound][prev][allZeros] = cnt // Return the total // possible valid numbers return cnt; } // Function to count numbers whose // adjacent digits are not co-prime function noncoprimeCountUtil(R) { // Convert R to string. var S = R.toString() // Length of string var N = S.length // Initialize dp array with -1 for(let i = 0 ; i < 100 ; i++){ dp[i] = new Array(2) for(let j = 0 ; j < 2 ; j++){ dp[i][j] = new Array(10) for(let k = 0 ; k < 10 ; k++){ dp[i][j][k] = new Array(2) for(let l = 0 ; l < 2 ; l++){ dp[i][j][k][l] = -1 } } } } // Function call with initial values of // bound, allZeros, previous as 1, 1, 0 var ans = noncoprimeCount(0, N, S, 1, 0, 1); // Subtract 1 from the answer, as 0 is included console.log(ans - 1) } // Input var N = 10000; // Function call noncoprimeCountUtil(N); // This code is contributed by subhamgoyal2014. |
Output:
1361
Time Complexity: O(log10N * 2 * 10 * 2 * 10). The extra factor of 10 arises as all digits [0, 9] are being iterated in each recursive call.
Auxiliary Space: O(log10N * 2 * 10 * 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!
