# Maximum set of number from the first N natural numbers whose Bitwise AND is positive

Given a positive integer **N**, the task is to find the maximum set of numbers from the first **N** natural numbers whose Bitwise AND is positive

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:N = 7Output:4Explanation:

The set of numbers from the first N(= 7) natural numbers whose Bitwise AND is positive is {4, 5, 6, 7}, which is of maximum length.

Input:N = 16Output:8

**Approach:** The given problem can be solved based on the observation that that **2 ^{N }and (2^{N} – 1)**, results in

**0**. Therefore, the maximum length of the set must not include both

**2**in the same set. The maximum subarray with non-zero AND value can be found out as:

^{N}and (2^{N}– 1)- Find the maximum power of 2 less than or equal to
**N**and if**N**is a power of 2, the answer should be**N/2**, for example, when N is**16**, the maximum subarray with non-zero AND value is**8**. - Otherwise, the answer is the length between the
**N**and the largest power of 2 less than or equal to**N**.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the maximum set of` `// number whose Bitwise AND is positive` `int` `maximumSizeOfSet(` `int` `N)` `{` ` ` `// Base Case` ` ` `if` `(N == 1)` ` ` `return` `1;` ` ` `// Store the power of 2 less than` ` ` `// or equal to N` ` ` `int` `temp = 1;` ` ` `while` `(temp * 2 <= N) {` ` ` `temp *= 2;` ` ` `}` ` ` `// N is power of 2` ` ` `if` `(N & (N - 1) == 0)` ` ` `return` `N / 2;` ` ` `else` ` ` `return` `N - temp + 1;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 7;` ` ` `cout << maximumSizeOfSet(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `class` `GFG{` `// Function to find the maximum set of` `// number whose Bitwise AND is positive` `public` `static` `int` `maximumSizeOfSet(` `int` `N)` `{` ` ` ` ` `// Base Case` ` ` `if` `(N == ` `1` `)` ` ` `return` `1` `;` ` ` `// Store the power of 2 less than` ` ` `// or equal to N` ` ` `int` `temp = ` `1` `;` ` ` `while` `(temp * ` `2` `<= N) {` ` ` `temp *= ` `2` `;` ` ` `}` ` ` `// N is power of 2` ` ` `if` `((N & (N - ` `1` `)) == ` `0` `)` ` ` `return` `N / ` `2` `;` ` ` `else` ` ` `return` `N - temp + ` `1` `;` `}` `// Driver Code` `public` `static` `void` `main(String args[])` `{` ` ` `int` `N = ` `7` `;` ` ` `System.out.println(maximumSizeOfSet(N));` `}` `}` `// This code is contributed by gfgking.` |

## Python3

`# python program for the above approach` `# Function to find the maximum set of` `# number whose Bitwise AND is positive` `def` `maximumSizeOfSet(N):` ` ` `# Base Case` ` ` `if` `(N ` `=` `=` `1` `):` ` ` `return` `1` ` ` `# Store the power of 2 less than` ` ` `# or equal to N` ` ` `temp ` `=` `1` ` ` `while` `(temp ` `*` `2` `<` `=` `N):` ` ` `temp ` `*` `=` `2` ` ` `# N is power of 2` ` ` `if` `(N & (N ` `-` `1` `) ` `=` `=` `0` `):` ` ` `return` `N ` `/` `/` `2` ` ` `else` `:` ` ` `return` `N ` `-` `temp ` `+` `1` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `N ` `=` `7` ` ` `print` `(maximumSizeOfSet(N))` `# This code is contributed by rakeshsahni` |

## C#

`// C# program for the above approach` `using` `System;` `public` `class` `GFG {` ` ` `static` `int` `maximumSizeOfSet(` `int` `N)` ` ` `{` ` ` `// Base Case` ` ` `if` `(N == 1)` ` ` `return` `1;` ` ` `// Store the power of 2 less than` ` ` `// or equal to N` ` ` `int` `temp = 1;` ` ` `while` `(temp * 2 <= N) {` ` ` `temp *= 2;` ` ` `}` ` ` `// N is power of 2` ` ` `if` `((N & (N - 1)) == 0)` ` ` `return` `N / 2;` ` ` `else` ` ` `return` `N - temp + 1;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `int` `N = 7;` ` ` `Console.WriteLine(maximumSizeOfSet(N));` ` ` `}` `}` `// This code is contributed by dwivediyash` |

## Javascript

`<script>` ` ` `// JavaScript program for the above approach` ` ` `// Function to find the maximum set of` ` ` `// number whose Bitwise AND is positive` ` ` `const maximumSizeOfSet = (N) => {` ` ` `// Base Case` ` ` `if` `(N == 1)` ` ` `return` `1;` ` ` `// Store the power of 2 less than` ` ` `// or equal to N` ` ` `let temp = 1;` ` ` `while` `(temp * 2 <= N) {` ` ` `temp *= 2;` ` ` `}` ` ` `// N is power of 2` ` ` `if` `(N & (N - 1) == 0)` ` ` `return` `parseInt(N / 2);` ` ` `else` ` ` `return` `N - temp + 1;` ` ` `}` ` ` `// Driver Code` ` ` `let N = 7;` ` ` `document.write(maximumSizeOfSet(N));` ` ` `// This code is contributed by rakeshsahni` `</script>` |

**Output:**

4

**Time Complexity:** O(log N)**Auxiliary Space:** O(1)