Count number of 0s in base K representation of a number
Given a number N, the task is to find the number of zero’s in base K representation of the given number, where K > 1.
Examples:
Input: N = 10, K = 3
Output: 1
Explanation: Base 3 representation of 10 is 101.
Hence the number of 0’s in 101 is 1.Input: N = 8, K = 2
Output: 3
Explanation: Base 2 representation of 8 is 1000.
Hence the number of 0’s in 1000 is 3.
Approach: This problem can be solved by converting the number into base K form.
The pseudocode for converting a number N of base 10 to base K :
allDigits = “”
While N > 0:
digit = N%k
allDigits.append(digit)
N /= k
number_in_base_K = reversed(allDigits)
Follow the steps mentioned below to implement the approach:
- Start forming the K base number as shown in the above pseudocode.
- Instead of forming the number only check in each pass of the loop is the current digit being formed is 0 or not to.
- Return the total count of 0s.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to count the number of zeros // in K base representation of N int countZero( int N, int K) { // Making a variable to store count int count = 0; // Looping till n becomes 0 while (N > 0) { // Check if the current digit // is 0 or not. if (N % K == 0) count++; N /= K; } return count; } // Driver code int main() { int N = 8; int K = 2; // Function call cout << countZero(N, K) << endl; return 0; } // This code is contributed by Ashish Kumar |
C
// C code to implement the approach #include<stdio.h> // Function to count the number of zeros // in K base representation of N int countZero( int N, int K) { // Making a variable to store count int count = 0; // Looping till n becomes 0 while (N > 0) { // Check if the current digit // is 0 or not. if (N % K == 0) count++; N /= K; } return count; } // Driver code int main() { int N = 8; int K = 2; // Function call int ans = countZero(N,K); printf ( "%d" ,ans); return 0; } // This code is contributed by ashishsingh13122000. |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to count the number of zeros // in K base representation of N public static int countZero( int N, int K) { // Making a variable to store count int count = 0 ; // Looping till n becomes 0 while (N > 0 ) { // Check if the current digit // is 0 or not. if (N % K == 0 ) count++; N /= K; } return count; } // Driver Code public static void main(String[] args) { int N = 8 ; int K = 2 ; // Function call System.out.println(countZero(N, K)); } } // This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach # Function to count the number of zeros # in K base representation of N def countZero(N, K): # Making a variable to store count count = 0 # Looping till n becomes 0 while (N > 0 ): # Check if the current digit # is 0 or not. if (N % K = = 0 ): count + = 1 N / / = K return count # Driver code N = 8 K = 2 # Function call print (countZero(N, K)) # This code is contributed by shinjanpatra |
C#
// C# code to implement the approach using System; class GFG { // Function to count the number of zeros // in K base representation of N static int countZero( int N, int K) { // Making a variable to store count int count = 0; // Looping till n becomes 0 while (N > 0) { // Check if the current digit // is 0 or not. if (N % K == 0) count++; N /= K; } return count; } // Driver Code public static void Main() { int N = 8; int K = 2; // Function call Console.Write(countZero(N, K)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to count the number of zeros // in K base representation of N function countZero(N, K) { // Making a variable to store count let count = 0; // Looping till n becomes 0 while (N > 0) { // Check if the current digit // is 0 or not. if (N % K == 0) count++; N = Math.floor(N / K); } return count; } // Driver code let N = 8; let K = 2; // Function call document.write(countZero(N, K) + '<br>' ); // This code is contributed by Potta Lokesh </script> |
3
Time Complexity: O(1)
Auxiliary Space: O(1)