Java 中的稀疏数

在本教程中，我们将讨论Java 中的稀疏数。稀疏数是指其二进制表示中不包含两个或两个以上连续设置位（1）的数字。让我们通过一些例子来理解它。

示例 1

输入

int n = 12

输出：12 不是稀疏数。

解释：这是因为 12 的二进制表示是 1100，其中包含两个连续的设置位。

示例 2

输入

int n = 10

输出：10 是稀疏数。

解释：这是因为 10 的二进制表示是 1010，其中不包含两个连续的设置位。

示例 3

输入

int n = 0

输出：0 是稀疏数。

解释：这是因为 0 的二进制表示是 0，其中不包含两个连续的设置位。

示例 4

输入

int n = 1

输出：1 是稀疏数。

解释：这是因为 1 的二进制表示是 1，其中不包含两个连续的设置位。

使用 ArrayList 的方法

我们可以将数字的二进制表示存储在 ArrayList 中，然后遍历该 ArrayList 来检查 ArrayList 中的两个连续元素是否包含 1。如果它们包含两个连续的 1，则该数字不是稀疏数；否则，它是一个稀疏数。请看以下程序。

文件名：SparseNumber.java

输出

The Spare numbers lying between 1 to 20 are: 
1 2 4 5 8 9 10 16 17 18 20

复杂度分析：上述程序的 time complexity 为 O(D)。该程序的 space complexity 为 O(D)，因为我们使用了大小为 D 的 ArrayList，其中 D 是数字 n 的二进制表示中存在的总位数。

程序的 time 和 space complexity 可以进一步降低。以下方法展示了相同的概念。

方法：使用右移运算符

我们可以使用右移运算符来计算稀疏数。我们知道两个连续的位永远不能同时设置（为 1），我们将使用此属性来计算稀疏数。让我们通过一个例子来理解。

12 = 00001100（二进制表示），如果右移 1 位，我们得到 00000110，则 00001100 & 00000110 = 00000100，等于 4（大于零）。如果我们取一个其两个连续位未设置的数字，然后将其右移一位，则结果为零。

10 = 00001010（二进制表示），如果右移 1 位，我们得到 00000101，则 00001010 & 00000101 = 0。因此，我们看到，如果我们取一个连续位未设置的数字，然后对其与右移一位后的数字进行按位与 (&) 操作，我们将得到 0。

文件名：SparseNumber1.java

输出

The Spare numbers lying between 1 to 20 are: 
1 2 4 5 8 9 10 16 17 18 20

复杂度分析：程序的 time 和 space complexity 都是常数，即 O(1)。