How to Check if a Number is Sparse

Introduction

A sparse number is one whose binary representation does not contain consecutive 1s. This article will show two ways to check if a number is sparse, a trivial one and a more efficient one.

Problem Example

Consider the following number and its binary representation:

N: 10

Binary: 00001010

The above number is sparse because it does not contain consecutive 1s.

N: 11

Binary: 00001011

The above number is not sparse because it contains two consecutive 1s.

A Trivial Way to Check if a Number is Sparse

An immediate solution to check if a number is sparse is the following:

• Apply the binary AND operator to the input number and 1
• Apply the binary AND operator to the input number shifted to the right by one position and 1
• If the results of the two previous operations are equal to each other and equal to 1 the number is not sparse
• Repeat the above until we obtain 0. If the number is not found to be not sparse in some of the repetitions, then it is sparse

You can find the above-described algorithm implemented in the code below:

    private boolean isSparseTrivialWay(int num) {
        int beforeShift;

        while (num > 0) {
            beforeShift = num & 1;
            num = num >> 1;
            int afterShift = num & 1;
            if (beforeShift == afterShift && beforeShift == 1) {
                return false;
            }
            beforeShift = afterShift;
        }
 
        return true;
    }

    @Test
    public void isSparseTrivialWayTest() throws Exception {

        assertTrue(isSparseTrivialWay(10));
        assertFalse(isSparseTrivialWay(11));

    }

Performance of the Trivial Algorithm

The time complexity of the above-described algorithm is O(Logn)

An Efficient Way to Check if a Number is Sparse

A more efficient way to check if a number is sparse is to apply the binary AND operator to the input number and the result of the shifting of the input number by one position to the right. If the result is 0 then the number is sparse. This is because all the 1s of the two binary representations of the input number will never be in the same positions if the number is sparse.

    private boolean isSparseEfficientWay(int num) {
        int current = num;
        int shifted = num >> 1;
        if ((current & shifted) == 0) {
            return true;
        }
        return false;
    }

    @Test
    public void isSparseEfficientWayTest() throws Exception {

        assertTrue(isSparseEfficientWay(10));
        assertFalse(isSparseEfficientWay(11));

    }

Performance of the Trivial Algorithm

The time complexity of the above-described algorithm is O(1)

Conclusion

This article explains two different strategies to solve the check if a number is sparse. The example code is available on GitHub.