600. Non-negative Integers without Consecutive Ones

leetcode hard

#bit-manipulation#csharp#hard#leetcode#search

Task

Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц.

Пример:

Input: n = 5

Output: 5

Explanation:

Here are the non-negative integers <= 5 with their corresponding binary representations:

0 : 0

1 : 1

2 : 10

3 : 11

4 : 100

5 : 101

Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.

C# solution

matched/original

public class Solution {
    public int FindIntegers(int num) {
        int count = 0;
        for (int i = 0; i <= num; i++) {
            if (Check(i)) {
                count++;
            }
        }
        return count;
    }
    public bool Check(int n) {
        int i = 31;
        while (i > 0) {
            if ((n & (1 << i)) != 0 && (n & (1 << (i - 1))) != 0) {
                return false;
            }
            i--;
        }
        return true;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindIntegers(int num) {
        int count = 0;
        for (int i = 0; i <= num; i++) {
            if (Check(i)) {
                count++;
            }
        }
        return count;
    }
    public bool Check(int n) {
        int i = 31;
        while (i > 0) {
            if ((n & (1 << i)) != 0 && (n & (1 << (i - 1))) != 0) {
                return false;
            }
            i--;
        }
        return true;
    }
}

Java solution

matched/original

public class Solution {
    public int findIntegers(int num) {
        int count = 0;
        for (int i = 0; i <= num; i++) {
            if (check(i)) {
                count++;
            }
        }
        return count;
    }

    public boolean check(int n) {
        int i = 31;
        while (i > 0) {
            if ((n & (1 << i)) != 0 && (n & (1 << (i - 1))) != 0) {
                return false;
            }
            i--;
        }
        return true;
    }
}

JavaScript solution

matched/original

var findIntegers = function(num) {
    let count = 0;
    for (let i = 0; i <= num; i++) {
        if (check(i)) {
            count++;
        }
    }
    return count;
};

function check(n) {
    let i = 31;
    while (i > 0) {
        if ((n & (1 << i)) !== 0 && (n & (1 << (i - 1))) !== 0) {
            return false;
        }
        i--;
    }
    return true;
}

Python solution

matched/original

class Solution:
    def findIntegers(self, num: int) -> int:
        def check(n):
            i = 31
            while i > 0:
                if (n & (1 << i)) != 0 and (n & (1 << (i - 1))) != 0:
                    return False
                i -= 1
            return True

        count = 0
        for i in range(num + 1):
            if check(i):
                count += 1
        return count

Go solution

matched/original

func findIntegers(num int) int {
    count := 0
    for i := 0; i <= num; i++ {
        if check(i) {
            count++
        }
    }
    return count
}

func check(n int) bool {
    i := 31
    for i > 0 {
        if (n&(1<<i) != 0) && (n&(1<<(i-1)) != 0) {
            return false
        }
        i--
    }
    return true
}

Explanation

Algorithm

Простой метод заключается в переборе всех чисел от 1 до num. Для каждого текущего выбранного числа проверяем все соседние позиции, чтобы выяснить, содержит ли число две последовательные единицы. Если не содержит, увеличиваем количество чисел без последовательных единиц.

Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x.

В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц.

😎