600. Non-negative Integers without Consecutive Ones

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;
    }
}

#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;
    }
}

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;
    }
}

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;
}

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

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
}

Algorithm

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

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

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

😎