Horje
Find longest range from numbers in range [1, N] having positive bitwise AND

Given a number N, the task is to find the longest range of integers [L, R] such that 1 ≤ L ≤ R ≤ N and the bitwise AND of all the numbers in that range is positive.

Examples:

Input: N = 7
Output: 4 7
Explanation: Check and from 1 to 7
Bitwise AND operations:
from 1 to 7 is 0 
from 2 to 7 is 0
from 3 to 7 is 0
from 4 to 7 is 4
Therefore, maximum range comes out from L = 4 to R = 7. 

Input: K = 16
Output: 8 15

 

Approach: The problem can be solved based on the following mathematical observation. If 2K is the closest exponent of 2 greater than N then the maximum range will be either of the two:

  • From 2(K – 2) to (2(K – 1) – 1) [both value inclusive] or,
  • From 2(K – 1) to N

Because these ranges confirm that all the numbers in the range will have the most significant bit set for all of them. If the ranges vary for powers of 2 then the bitwise AND of the range will become 0.

Below is the implementation of the above approach.

C++

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the closest exponent of 2
// which is greater than K
int minpoweroftwo(int K)
{
    int count = 0;
    while (K > 0) {
        count++;
        K = K >> 1;
    }
    return count;
}
 
// Function to find the longest range
void findlongestrange(int N)
{
 
    int K = minpoweroftwo(N);
    int y = N + 1 - pow(2, K - 1);
    int z = (pow(2, K - 1) - pow(2, K - 2));
 
    if (y >= z) {
        cout << pow(2, K - 1) << " " << N;
    }
    else {
        cout << pow(2, K - 2) << " "
            << pow(2, K - 1) - 1;
    }
}
 
// Driver code
int main()
{
    int N = 16;
    findlongestrange(N);
    return 0;
}

C

// C code to implement above approach
#include <math.h>
#include <stdio.h>
 
// Function to find the closest exponent of 2
// which is greater than K
int minpoweroftwo(int K)
{
    int count = 0;
    while (K > 0) {
        count++;
        K = K >> 1;
    }
    return count;
}
 
// Function to find the longest range
void findlongestrange(int N)
{
 
    int K = minpoweroftwo(N);
    int y = N + 1 - pow(2, K - 1);
    int z = (pow(2, K - 1) - pow(2, K - 2));
 
    if (y >= z) {
        printf("%d %d", (int)pow(2, K - 1), N);
    }
    else {
        printf("%d %d", (int)pow(2, K - 2),
               (int)pow(2, K - 1)-1);
    }
}
 
// Driver code
int main()
{
    int N = 16;
    findlongestrange(N);
    return 0;
}

Java

// Java code to implement above approach
 
class GFG {
 
    // Function to find the closest exponent of 2
    // which is greater than K
    static int minpoweroftwo(int K) {
        int count = 0;
        while (K > 0) {
            count++;
            K = K >> 1;
        }
        return count;
    }
 
    // Function to find the longest range
    static void findlongestrange(int N) {
 
        int K = minpoweroftwo(N);
        int y = (int) (N + 1 - Math.pow(2, K - 1));
        int z = (int) (Math.pow(2, K - 1) - Math.pow(2, K - 2));
 
        if (y >= z) {
            System.out.println(Math.pow(2, K - 1) + " " + N);
        } else {
            System.out.print((int) Math.pow(2, K - 2));
            System.out.print(" ");
            System.out.print((int) Math.pow(2, K - 1) - 1);
        }
    }
 
    // Driver code
    public static void main(String args[]) {
        int N = 16;
        findlongestrange(N);
    }
}
 
// This code is contributed by gfgking.

Python3

# Python code to implement above approach
 
# Function to find the closest exponent of 2
# which is greater than K
def minpoweroftwo(K):
    count = 0;
    while (K > 0):
        count += 1;
        K = K >> 1;
 
    return count;
 
# Function to find the longest range
def findlongestrange(N):
    K = minpoweroftwo(N);
    y = int(N + 1 - pow(2, K - 1));
    z = int(pow(2, K - 1) - pow(2, K - 2));
 
    if (y >= z):
        print(pow(2, K - 1) , " " , N);
    else:
        print(pow(2, K - 2));
        print(" ");
        print(pow(2, K - 1) - 1);
 
# Driver code
if __name__ == '__main__':
    N = 16;
    findlongestrange(N);
 
# This code is contributed by 29AjayKumar

C#

// C# code to implement above approach
using System;
class GFG {
 
  // Function to find the closest exponent of 2
  // which is greater than K
  static int minpoweroftwo(int K)
  {
    int count = 0;
    while (K > 0) {
      count++;
      K = K >> 1;
    }
    return count;
  }
 
  // Function to find the longest range
  static void findlongestrange(int N)
  {
 
    int K = minpoweroftwo(N);
    int y = (int)(N + 1 - Math.Pow(2, K - 1));
    int z = (int)(Math.Pow(2, K - 1)
                  - Math.Pow(2, K - 2));
 
    if (y >= z) {
      Console.Write(Math.Pow(2, K - 1) + " " + N);
    }
    else {
      Console.Write((int)Math.Pow(2, K - 2));
      Console.Write(" ");
      Console.Write((int)Math.Pow(2, K - 1) - 1);
    }
  }
 
  // Driver code
  public static void Main()
  {
    int N = 16;
    findlongestrange(N);
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
        // JavaScript code for the above approach
 
        // Function to find the closest exponent of 2
        // which is greater than K
        function minpoweroftwo(K) {
            let count = 0;
            while (K > 0) {
                count++;
                K = K >> 1;
            }
            return count;
        }
 
        // Function to find the longest range
        function findlongestrange(N)
        {
            let K = minpoweroftwo(N);
            let y = N + 1 - Math.pow(2, K - 1);
            let z = (Math.pow(2, K - 1) - Math.pow(2, K - 2));
 
            if (y >= z) {
                document.write(Math.pow(2, K - 1) + " " + N);
            }
            else {
                document.write(Math.pow(2, K - 2) + " "
                    + (Math.pow(2, K - 1) - 1));
            }
        }
 
        // Driver code
        let N = 16;
        findlongestrange(N);
 
  // This code is contributed by Potta Lokesh
    </script>

 
 

Output

8 15

 

Time Complexity: O(logN)
Auxiliary Space: O(1)

 


 


Reffered: https://www.geeksforgeeks.org

Bit Magic

Related
Binary numbers of N digits Binary numbers of N digits
Generate all binary numbers in range [L, R] with same length Generate all binary numbers in range [L, R] with same length
Convert all numbers in range [L, R] to binary number Convert all numbers in range [L, R] to binary number
PHP Program to Check if Two Numbers are Bit Rotations of Each Other or Not PHP Program to Check if Two Numbers are Bit Rotations of Each Other or Not
Javascript Program to Check if two numbers are bit rotations of each other or not Javascript Program to Check if two numbers are bit rotations of each other or not

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 16



 

Horje