Given an integer N, the task is to find the smallest number K such that bitwise AND of all the numbers in range [N, N-K] is 0, i.e. N & (N – 1) & (N – 2) &… (N – K) = 0.
Examples:
Input: N = 17
Output: 2
Explanation:
17&16 = 16
16&15 = 0
Since, we need to find the smallest K, So we stop here.
K = N – 15 = 17 – 15 = 2
Input: N = 4
Output: 1
Explanation:
4&3 = 0
Since, we need to find the smallest k, So we stop here.
Naive Approach: The simplest approach to solve the problem is to start with given number and take bitwise AND with one number less than the current number till the cumulative bitwise AND is not equal to 0. Follow the steps below to solve this problem:
- Declare a variable cummAnd that stores the commutative bitwise AND and initialize it with n.
- Declare a variable i and initialize it with n – 1.
- Run a loop while cummAnd not equal to 0:
- cummAnd = cummAnd & i.
- Decrement i by 1.
- Finally, print n – i.
Below is the implementation of the following approach:
C++
// C++ program to find smallest value of K// such that bitwise AND of numbers// in range [N, N-K] is 0#include <iostream>using namespace std;// Function is to find the largest no which gives the// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.int findSmallestNumK(int n){ int cummAnd = n; int i = n - 1; // Since, we need the largest no, // we start from n itself, till 0 while (cummAnd != 0) { cummAnd = cummAnd & i; if (cummAnd == 0) { return i; } i--; } return -1;}// Driver Codeint main(){ int N = 17; int lastNum = findSmallestNumK(N); int K = lastNum == -1 ? lastNum : N - lastNum; cout << K << "\n"; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function is to find the largest no which gives the // sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0. public static int findSmallestNumK(int n) { int cummAnd = n; int i = n - 1; // Since, we need the largest no, // we start from n itself, till 0 while (cummAnd != 0) { cummAnd = cummAnd & i; if (cummAnd == 0) { return i; } i--; } return -1; } // Driver Code public static void main(String[] args) { int N = 17; int lastNum = findSmallestNumK(N); int K = lastNum == -1 ? lastNum : N - lastNum; System.out.println(K); }}// This code is contributed by Potta Lokesh |
Python3
# Python3 program to find smallest value of K# such that bitwise AND of numbers# in range [N, N-K] is 0# Function is to find the largest no which gives the# sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.def findSmallestNumK(n): cummAnd = n i = n - 1 # Since, we need the largest no, # we start from n itself, till 0 while (cummAnd != 0): cummAnd = cummAnd & i if (cummAnd == 0): return i i -= 1 return -1# Driver Codeif __name__ == '__main__': N = 17 lastNum = findSmallestNumK(N); K = lastNum if lastNum == -1 else N - lastNum print(K)# This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;class GFG{// Function is to find the largest no which gives the// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.public static int findSmallestNumK(int n){ int cummAnd = n; int i = n - 1; // Since, we need the largest no, // we start from n itself, till 0 while (cummAnd != 0) { cummAnd = cummAnd & i; if (cummAnd == 0) { return i; } i--; } return -1;}// Driver codestatic void Main(){ int N = 17; int lastNum = findSmallestNumK(N); int K = lastNum == -1 ? lastNum : N - lastNum; Console.WriteLine(K);}}// This code is contributed by abhinavjain194 |
Javascript
<script> // JavaScript program for the above approach // Function is to find the largest no which gives the // sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0. function findSmallestNumK(n) { let cummAnd = n; let i = n - 1; // Since, we need the largest no, // we start from n itself, till 0 while (cummAnd != 0) { cummAnd = cummAnd & i; if (cummAnd == 0) { return i; } i--; } return -1; } // Driver Code let N = 17; let lastNum = findSmallestNumK(N); let K = lastNum == -1 ? lastNum : N - lastNum; document.write(K + "<br>"); // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: This problem can be solved by using the properties of bitwise AND operator i.e If both the bits are set then only the result will be non-zero. So, we have to find the largest power of 2, which is less than or equal to N(let say X). Follow the steps below to solve this problem:
- The log2(n) function gives the power of 2, which is equal to n.
- Since, its return type is double. So we use floor function to get the largest power of 2, which is less than or equal to n and store it into X.
- X = (1 << X) – 1.
- Finally, print N – X.
Below is the implementation of the following approach:
C++
// C++ program to find smallest value of K// such that bitwise AND of numbers// in range [N, N-K] is 0#include <bits/stdc++.h>using namespace std;// Function is to find the largest no which gives the// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.int findSmallestNumK(int n){ // find largest power of 2 // less than or equal to n int larPowOfTwo = floor(log2(n)); larPowOfTwo = 1 << larPowOfTwo; return larPowOfTwo - 1;}// Driver Codeint main(){ int N = 17; int lastNum = findSmallestNumK(N); int K = lastNum == -1 ? lastNum : N - lastNum; cout << K << "\n"; return 0;} |
C
// C program to find smallest value of K// such that bitwise AND of numbers// in range [N, N-K] is 0#include <math.h> //for log2#include <stdio.h>// Function is to find the largest no which gives the// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.int findSmallestNumK(int n){ // find largest power of 2 // less than or equal to n int larPowOfTwo = floor(log2(n)); larPowOfTwo = 1 << larPowOfTwo; return larPowOfTwo - 1;}// Driver Codeint main(){ int N = 17; int lastNum = findSmallestNumK(N); int K = lastNum == -1 ? lastNum : N - lastNum; printf("%d\n", K); return 0;}// This code is contributed by phalashi. |
Java
// Java program to find smallest value of K// such that bitwise AND of numbers// in range [N, N-K] is 0import java.io.*;class GFG { // Function is to find the largest no which gives the // sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0. static int findSmallestNumK(int n) { // find largest power of 2 // less than or equal to n int larPowOfTwo = (int)Math.floor(Math.log(n) / Math.log(2)); larPowOfTwo = 1 << larPowOfTwo; return larPowOfTwo - 1; } // Driver Code public static void main(String[] args) { int N = 17; int lastNum = findSmallestNumK(N); int K = lastNum == -1 ? lastNum : N - lastNum; System.out.println(K); }}// This code is contributed by rishavmahato348. |
Python3
# Python program to find smallest value of K# such that bitwise AND of numbers# in range [N, N-K] is 0# Function is to find the largest no which gives the# sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.import mathdef findSmallestNumK( n): # find largest power of 2 # less than or equal to n larPowOfTwo = math.floor(math.log2(n)) larPowOfTwo = 1 << larPowOfTwo return larPowOfTwo - 1# Driver CodeN = 17lastNum = findSmallestNumK(N)K = lastNum if (lastNum == -1 ) else N - lastNumprint(K)# this code is contributed by shivanisinghss2110 |
C#
// C# program to find smallest value of K// such that bitwise AND of numbers// in range [N, N-K] is 0using System;class GFG{// Function is to find the largest no which gives the// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.static int findSmallestNumK(int n){ // Find largest power of 2 // less than or equal to n int larPowOfTwo = (int)Math.Floor(Math.Log(n) / Math.Log(2)); larPowOfTwo = 1 << larPowOfTwo; return larPowOfTwo - 1;}// Driver Codepublic static void Main(){ int N = 17; int lastNum = findSmallestNumK(N); int K = lastNum == -1 ? lastNum : N - lastNum; Console.Write(K);}}// This code is contributed by subhammahato348 |
Javascript
<script>// JavaScript program to find smallest value of K// such that bitwise AND of numbers// in range [N, N-K] is 0// Function is to find the largest no which gives the// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.function findSmallestNumK(n) { // find largest power of 2 // less than or equal to n var larPowOfTwo = Math.floor(Math.log(n) / Math.log(2)); larPowOfTwo = 1 << larPowOfTwo; return larPowOfTwo - 1; }// Driver Code var N = 17; var lastNum = findSmallestNumK(N); var K = lastNum == -1 ? lastNum : N - lastNum; document.write(K); // This code is contributed by shivanisinghss2110</script> |
Output
2
Time Complexity: O(log N)
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
