|
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++
#include <bits/stdc++.h>
using namespace std;
int countZero(int N, int K)
{
int count = 0;
while (N > 0) {
if (N % K == 0)
count++;
N /= K;
}
return count;
}
int main()
{
int N = 8;
int K = 2;
cout << countZero(N, K) << endl;
return 0;
}
|
C
#include<stdio.h>
int countZero(int N, int K)
{
int count = 0;
while (N > 0) {
if (N % K == 0)
count++;
N /= K;
}
return count;
}
int main()
{
int N = 8;
int K = 2;
int ans = countZero(N,K);
printf("%d",ans);
return 0;
}
|
Java
import java.io.*;
class GFG
{
public static int countZero(int N, int K)
{
int count = 0;
while (N > 0) {
if (N % K == 0)
count++;
N /= K;
}
return count;
}
public static void main(String[] args)
{
int N = 8;
int K = 2;
System.out.println(countZero(N, K));
}
}
|
Python3
def countZero(N, K):
count = 0
while (N > 0):
if (N % K == 0):
count += 1
N //= K
return count
N = 8
K = 2
print(countZero(N, K))
|
C#
using System;
class GFG {
static int countZero(int N, int K)
{
int count = 0;
while (N > 0) {
if (N % K == 0)
count++;
N /= K;
}
return count;
}
public static void Main()
{
int N = 8;
int K = 2;
Console.Write(countZero(N, K));
}
}
|
Javascript
<script>
function countZero(N, K)
{
let count = 0;
while (N > 0) {
if (N % K == 0)
count++;
N = Math.floor(N / K);
}
return count;
}
let N = 8;
let K = 2;
document.write(countZero(N, K) + '<br>');
</script>
|
Time Complexity: O(1)
Auxiliary Space: O(1)
|
