Check whether a number has consecutive 0’s in the given base or not

0 0 9 minutes read

Given a decimal number N, the task is to check if a number has consecutive zeroes or not after converting the number to its K-based notation.

Examples:

Input: N = 4, K = 2
Output: No
4 in base 2 is 100, As there are consecutive 2 thus the answer is No.

Input: N = 15, K = 8
Output: Yes
15 in base 8 is 17, As there are no consecutive 0 so the answer is Yes.

Approach: First convert the number N into base K and then simply check if the number has consecutive zeroes or not.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
#include<bits/stdc++.h>
using namespace std;
 
 
 
// Function to convert N into base K
int toK(int N, int K)
{
 
// Weight of each digit
    int w = 1;
    int s = 0;
    while (N != 0)
     {
        int r = N % K;
        N = N/K;
        s = r * w + s;
        w *= 10;
     }
    return s;
 
}
 
// Function to check for consecutive 0
bool check(int N)
{
 
// Flag to check if there are consecutive 
    // zero or not
    bool fl = false;
    while (N != 0)
    {
 
        int r = N % 10;
        N = N/10;
 
        // If there are two consecutive zero 
        // then returning False
        if (fl == true and r == 0)
            return false;
        if (r > 0)
            {
            fl = false;
            continue;
            }
        fl = true;
 
    }
     return true;
         
}
 
// We first convert to given base, then
// check if the converted number has two
// consecutive 0s or not
void hasConsecutiveZeroes(int N, int K)
{
    int z = toK(N, K);
    if (check(z))
       cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
}
 
     
 
// Driver code
int main()
{
int N = 15;
int K = 8;
hasConsecutiveZeroes(N, K);
 
}
// This code is contributed by
// Surendra_Gangwar

Java

// Java implementation of the above approach
import java.util.*;
 
class GFG 
{ 
 
// Function to convert N into base K
static int toK(int N, int K)
{
 
    // Weight of each digit
    int w = 1;
    int s = 0;
    while (N != 0)
    {
        int r = N % K;
        N = N / K;
        s = r * w + s;
        w *= 10;
    }
    return s;
 
}
 
// Function to check for consecutive 0
static boolean check(int N)
{
 
    // Flag to check if there are consecutive 
    // zero or not
    boolean fl = false;
    while (N != 0)
    {
 
        int r = N % 10;
        N = N / 10;
 
        // If there are two consecutive zero 
        // then returning False
        if (fl == true && r == 0)
            return false;
        if (r > 0)
        {
            fl = false;
            continue;
        }
        fl = true;
    }
    return true;
}
 
// We first convert to given base, then
// check if the converted number has two
// consecutive 0s or not
static void hasConsecutiveZeroes(int N, int K)
{
    int z = toK(N, K);
    if (check(z))
        System.out.println("Yes");
    else
        System.out.println("No");
}
 
// Driver code
public static void main(String[] args)
{
    int N = 15;
    int K = 8;
    hasConsecutiveZeroes(N, K);
}
}
 
// This code is contributed by Princi Singh

Python3

# Python implementation of the above approach
 
# We first convert to given base, then
# check if the converted number has two
# consecutive 0s or not
def hasConsecutiveZeroes(N, K):
    z = toK(N, K)
    if (check(z)):
        print("Yes")
    else:
        print("No")
 
# Function to convert N into base K
def toK(N, K):
 
    # Weight of each digit
    w = 1
    s = 0
    while (N != 0):
        r = N % K
        N = N//K
        s = r * w + s
        w* = 10
    return s
 
# Function to check for consecutive 0
def check(N):
 
    # Flag to check if there are consecutive 
    # zero or not
    fl = False
    while (N != 0):
        r = N % 10
        N = N//10
 
        # If there are two consecutive zero 
        # then returning False
        if (fl == True and r == 0):
            return False
        if (r > 0):
            fl = False
            continue
        fl = True
    return True
 
# Driver code
N, K = 15, 8
hasConsecutiveZeroes(N, K)

C#

// C# implementation of the above approach
using System;
 
class GFG 
{ 
 
// Function to convert N into base K
static int toK(int N, int K)
{
 
    // Weight of each digit
    int w = 1;
    int s = 0;
    while (N != 0)
    {
        int r = N % K;
        N = N / K;
        s = r * w + s;
        w *= 10;
    }
    return s;
}
 
// Function to check for consecutive 0
static Boolean check(int N)
{
 
    // Flag to check if there are consecutive 
    // zero or not
    Boolean fl = false;
    while (N != 0)
    {
 
        int r = N % 10;
        N = N / 10;
 
        // If there are two consecutive zero 
        // then returning False
        if (fl == true && r == 0)
            return false;
        if (r > 0)
        {
            fl = false;
            continue;
        }
        fl = true;
    }
    return true;
}
 
// We first convert to given base, then
// check if the converted number has two
// consecutive 0s or not
static void hasConsecutiveZeroes(int N, int K)
{
    int z = toK(N, K);
    if (check(z))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 15;
    int K = 8;
    hasConsecutiveZeroes(N, K);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of the above approach
 
// Function to convert N into base K
function toK(N, K)
{
     
    // Weight of each digit
    let w = 1;
    let s = 0;
     
    while (N != 0)
    {
        let r = N % K;
        N = parseInt(N / K);
        s = r * w + s;
        w *= 10;
    }
    return s;
}
 
// Function to check for consecutive 0
function check(N)
{
     
    // Flag to check if there are consecutive 
    // zero or not
    let fl = false;
     
    while (N != 0)
    {
        let r = N % 10;
        N = parseInt(N/10);
 
        // If there are two consecutive zero 
        // then returning False
        if (fl == true && r == 0)
            return false;
        if (r > 0)
        {
            fl = false;
            continue;
        }
        fl = true;
    }
     return true;
}
 
// We first convert to given base, then
// check if the converted number has two
// consecutive 0s or not
function hasConsecutiveZeroes(N, K)
{
    let z = toK(N, K);
    if (check(z))
       document.write("Yes");
    else
      document.write("No");
}
 
// Driver code
let N = 15;
let K = 8;
 
hasConsecutiveZeroes(N, K);
 
// This code is contributed by souravmahato348
 
</script>

PHP

<?php
// PHP implementation of the above approach
 
// We first convert to given base, 
// then check if the converted number 
// has two consecutive 0s or not
function hasConsecutiveZeroes($N, $K)
{
    $z = toK($N, $K);
    if (check($z))
        print("Yes");
    else
        print("No");
}
 
// Function to convert N into base K
function toK($N, $K)
{
    // Weight of each digit
    $w = 1;
    $s = 0;
    while ($N != 0)
    {
        $r = $N % $K;
        $N = (int)($N / $K);
        $s = $r * $w + $s;
        $w *= 10;
    }
    return $s;
}
 
// Function to check for consecutive 0
function check($N)
{
    // Flag to check if there are 
    // consecutive zero or not
    $fl = false;
    while ($N != 0)
    {
        $r = $N % 10;
        $N = (int)($N / 10);
 
        // If there are two consecutive 
        // zero then returning false
        if ($fl == true and $r == 0)
            return false;
        if ($r > 0)
        {
            $fl = false;
            continue;
        }
        $fl = true;
    }
    return true;
}
 
// Driver code
$N = 15;
$K = 8;
hasConsecutiveZeroes($N, $K);
 
// This code is contributed by mits
?>

Output

Yes

Time Complexity: O(log_kn + log₁₀n), where n and k represents the value of the given integers.
Auxiliary Space: O(1), no extra space is required, so it is a constant.

Approach: 2

Here is another approach to solve the same problem:

Start with the given number N and initialize a variable called count to 0.
Convert N to base K by continuously dividing N by K and appending the remainder to the right of the result until N becomes 0. Let’s call the result of this conversion s.
Traverse through the string s and check each character. If the character is ‘0’, increment count by 1. If the character is not ‘0’, reset count to 0.
If count becomes 2 or more during the traversal, then the number N has consecutive 0s in base K. Otherwise, it does not.

Here is the code of above approach:

C++

#include <iostream>
#include <string>
 
using namespace std;
 
bool hasConsecutiveZeroes(int N, int K) {
    // Convert N to base K
    string s = "";
    while (N > 0) {
        s = to_string(N % K) + s;
        N /= K;
    }
 
    // Traverse through the converted string and check for consecutive 0s
    int count = 0;
    for (char c : s) {
        if (c == '0') {
            count++;
            if (count >= 2) {
                return false;
            }
        } else {
            count = 0;
        }
    }
 
    return true;
}
 
int main() {
    int N = 15;
    int K = 8;
    if (hasConsecutiveZeroes(N, K)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Java

import java.util.*;
 
public class Main {
  static boolean hasConsecutiveZeroes(int N, int K) {
    // Convert N to base K
    String s = "";
    while (N > 0) {
        s = Integer.toString(N % K) + s;
        N /= K;
    }
 
    // Traverse through the converted string and check for consecutive 0s
    int count = 0;
    for (char c : s.toCharArray()) {
        if (c == '0') {
            count++;
            if (count >= 2) {
                return false;
            }
        } else {
            count = 0;
        }
    }
 
    return true;
}
 
public static void main(String[] args) {
    int N = 15;
    int K = 8;
    if (hasConsecutiveZeroes(N, K)) {
        System.out.println("Yes");
    } else {
        System.out.println("No");
    }
}
}

Python3

def hasConsecutiveZeroes(N, K):
    # Convert N to base K
    s = ""
    while N > 0:
        s = str(N % K) + s
        N //= K
 
    # Traverse through the converted string and check for consecutive 0s
    count = 0
    for c in s:
        if c == '0':
            count += 1
            if count >= 2:
                return False
        else:
            count = 0
 
    return True
 
N = 15
K = 8
if hasConsecutiveZeroes(N, K):
    print("Yes")
else:
    print("No")

C#

using System;
 
public class ConsecutiveZeroesCheck
{
    public static bool HasConsecutiveZeroes(int N, int K)
    {
        // Convert N to base K
        string s = "";
        while (N > 0)
        {
            s = (N % K).ToString() + s;
            N /= K;
        }
 
        // Traverse through the converted string and check for consecutive 0s
        int count = 0;
        foreach (char c in s)
        {
            if (c == '0')
            {
                count++;
                if (count >= 2)
                {
                    return false;
                }
            }
            else
            {
                count = 0;
            }
        }
 
        return true;
    }
 
    public static void Main(string[] args)
    {
        int N = 15;
        int K = 8;
 
        if (HasConsecutiveZeroes(N, K))
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }
}

Javascript

/**
 * This function checks if the number N in base K has consecutive 0s.
 *
 * @param n The number to check.
 * @param k The base to convert N to.
 *
 * @returns True if N in base K has consecutive 0s, False otherwise.
 */
function hasConsecutiveZeroes(n, k) {
 
    // Convert N to base K.
    // The variable `s` will store the converted string.
    let s = "";
    while (n > 0) {
        // Append the remainder of N divided by K to the string `s`.
        s += String(n % k);
        // Get the quotient of N divided by K.
        n = Math.floor(n / k);
    }
 
    // Traverse through the converted string and check for consecutive 0s.
    // The variable `count` will keep track of the number of consecutive 0s.
    let count = 0;
    for (const c of s) {
        // If the current character is a 0, increment `count`.
        if (c === "0") {
            count++;
        } else {
            // If the current character is not a 0, reset `count` to 0.
            count = 0;
        }
 
        // If `count` is greater than or equal to 2, return False.
        if (count >= 2) {
            return false;
        }
    }
 
    // If `count` is less than 2, return True.
    return true;
}
 
/**
 * This is the main entry point of the program.
 *
 * It takes two integers N and K as input and prints "Yes" if N in base K has consecutive 0s,
 * and "No" otherwise.
 */
    const n = 15;
    const k = 8;
    if (hasConsecutiveZeroes(n, k)) {
        console.log("Yes");
    } else {
        console.log("No");
    }

Output

Yes

Time Complexity: O(logN + length of the string).
Auxiliary Space: O(logN) , because it also requires storing the converted number as a string.

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 zambiatek!