Given three numbers N, K, and B, the task is to check if N contains only K as digits in Base B.
Examples:
Input: N = 13, B = 3, K = 1
Output: Yes
Explanation:
13 base 3 is 111 which contain all one’s(K).Input: N = 5, B = 2, K = 1
Output: No
Explanation:
5 base 2 is 101 which doesn’t contains all one’s (K).
Naive Approach: A simple solution is to convert the given number N to base B and one by one check if all its digits are K or not.
Time Complexity: O(D), where D is the number of digits in number N
Auxiliary Space: O(1)
Efficient Approach: The key observation in the problem is that any number with all digits as K in base B can be represented as:
These terms are in the form of the Geometric Progression with the first term as K and the common ratio as B.
Sum of G.P. Series:
Therefore, the number in base B with all digits as K is:
Hence, just check if this sum equals N or not. If it’s equal then print “Yes” otherwise print “No”.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; // Function to print the number of digits int findNumberOfDigits( int n, int base) { // Calculate log using base change // property and then take its floor // and then add 1 int dig = ( floor ( log (n) / log (base)) + 1); // Return the output return (dig); } // Function that returns true if n contains // all one's in base b int isAllKs( int n, int b, int k) { int len = findNumberOfDigits(n, b); // Calculate the sum int sum = k * (1 - pow (b, len)) / (1 - b); if (sum == n) { return (sum); } } // Driver code int main() { // Given number N int N = 13; // Given base B int B = 3; // Given digit K int K = 1; // Function call if (isAllKs(N, B, K)) { cout << "Yes" ; } else { cout << "No" ; } } // This code is contributed by vikas_g |
C
// C implementation of the approach #include <stdio.h> #include <math.h> // Function to print the number of digits int findNumberOfDigits( int n, int base) { // Calculate log using base change // property and then take its floor // and then add 1 int dig = ( floor ( log (n) / log (base)) + 1); // Return the output return (dig); } // Function that returns true if n contains // all one's in base b int isAllKs( int n, int b, int k) { int len = findNumberOfDigits(n, b); // Calculate the sum int sum = k * (1 - pow (b, len)) / (1 - b); if (sum == n) { return (sum); } } // Driver code int main( void ) { // Given number N int N = 13; // Given base B int B = 3; // Given digit K int K = 1; // Function call if (isAllKs(N, B, K)) { printf ( "Yes" ); } else { printf ( "No" ); } return 0; } // This code is contributed by vikas_g |
Java
// Java implementation of above approach import java.util.*; class GFG{ // Function to print the number of digits static int findNumberOfDigits( int n, int base) { // Calculate log using base change // property and then take its floor // and then add 1 int dig = (( int )Math.floor(Math.log(n) / Math.log(base)) + 1 ); // Return the output return dig; } // Function that returns true if n contains // all one's in base b static boolean isAllKs( int n, int b, int k) { int len = findNumberOfDigits(n, b); // Calculate the sum int sum = k * ( 1 - ( int )Math.pow(b, len)) / ( 1 - b); return sum == n; } // Driver code public static void main(String[] args) { // Given number N int N = 13 ; // Given base B int B = 3 ; // Given digit K int K = 1 ; // Function call if (isAllKs(N, B, K)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by offbeat |
Python3
# Python3 program for the above approach import math # Function to print the number of digits def findNumberOfDigits(n, base): # Calculate log using base change # property and then take its floor # and then add 1 dig = (math.floor(math.log(n) / math.log(base)) + 1 ) # Return the output return dig # Function that returns true if n contains # all one's in base b def isAllKs(n, b, k): len = findNumberOfDigits(n, b) # Calculate the sum sum = k * ( 1 - pow (b, len )) / ( 1 - b) return sum = = N # Driver code # Given number N N = 13 # Given base B B = 3 # Given digit K K = 1 # Function call if (isAllKs(N, B, K)): print ( "Yes" ) else : print ( "No" ) |
C#
// C# implementation of above approach using System; class GFG{ // Function to print the number of digits static int findNumberOfDigits( int n, int bas) { // Calculate log using base change // property and then take its floor // and then add 1 int dig = (( int )Math.Floor(Math.Log(n) / Math.Log(bas)) + 1); // Return the output return dig; } // Function that returns true if n contains // all one's in base b static bool isAllKs( int n, int b, int k) { int len = findNumberOfDigits(n, b); // Calculate the sum int sum = k * (1 - ( int )Math.Pow(b, len)) / (1 - b); return sum == n; } // Driver code public static void Main() { // Given number N int N = 13; // Given base B int B = 3; // Given digit K int K = 1; // Function call if (isAllKs(N, B, K)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by vikas_g |
Javascript
<script> // Javascript implementation of the approach // Function to print the number of digits function findNumberOfDigits(n, base) { // Calculate log using base change // property and then take its floor // and then add 1 var dig = (Math.floor(Math.log(n) / Math.log(base)) + 1); // Return the output return (dig); } // Function that returns true if n contains // all one's in base b function isAllKs(n, b, k) { var len = findNumberOfDigits(n, b); // Calculate the sum var sum = k * (1 - Math.pow(b, len)) / (1 - b); if (sum == n) { return (sum); } } // Driver code // Given number N var N = 13; // Given base B var B = 3; // Given digit K var K = 1; // Function call if (isAllKs(N, B, K)) { document.write( "Yes" ); } else { document.write( "No" ); } // This code is contributed by rrrtnx. </script> |
Yes
Time Complexity: O(log(D)), where D is the number of digits in number N
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!