# Count of numbers which can be made power of 2 by given operation

Given a array **arr[]**, the task is to count the numbers which can be made **power of 2** with the following operation: **1** can be added to any element atmost once if its not already a power of 2.

**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:arr[] = {2, 3, 7, 9, 15}Output:4

3, 7 and 15 can be made a power of 2 by adding 1, and 2 is already a power of 2

Input:arr[] = {5, 6, 9, 3, 1}Output:2

**Approach:** Traverse the array and check if the current element is a power of 2, if it is then update **count = count + 1**. If its not a power of 2 then check for one element greater i.e. **arr[i] + 1**. To check if an element is a power of 2:

**Naive method**is to repeatedly**divide**the element by**2**until it gives either**0**or**1**as the remainder. if the remainder is**1**then its a power of 2 else its not a power of 2.**Efficient method:**If**X & (X – 1) = 0**then**X**is a power of two.

Say,**X = 16 = 10000**and**X – 1 = 15 = 01111**then**X & (X – 1) = 10000 & 01111 = 0**i.e.**X = 16**is a power of 2.

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function that returns true if x is a power of 2` `bool` `isPowerOfTwo(` `int` `x)` `{` ` ` `if` `(x == 0)` ` ` `return` `false` `;` ` ` `// If x & (x-1) = 0 then x is a power of 2` ` ` `if` `(!(x & (x - 1)))` ` ` `return` `true` `;` ` ` `else` ` ` `return` `false` `;` `}` `// Function to return the required count` `int` `countNum(` `int` `a[], ` `int` `n)` `{` ` ` `int` `count = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `// If a[i] or (a[i]+1) is a power of 2` ` ` `if` `(isPowerOfTwo(a[i]) || isPowerOfTwo(a[i] + 1))` ` ` `count++;` ` ` `}` ` ` `return` `count;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `arr[] = { 5, 6, 9, 3, 1 };` ` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `cout << countNum(arr, n);` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the approach` `import` `java.util.*;` `class` `GFG` `{` `// Function that returns true if x is a power of 2` `static` `boolean` `isPowerOfTwo(` `int` `x)` `{` ` ` `if` `(x == ` `0` `)` ` ` `return` `false` `;` ` ` `// If x & (x-1) = 0 then x is a power of 2` ` ` `if` `((x & (x - ` `1` `)) == ` `0` `)` ` ` `return` `true` `;` ` ` `else` ` ` `return` `false` `;` `}` `// Function to return the required count` `static` `int` `countNum(` `int` `a[], ` `int` `n)` `{` ` ` `int` `count = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` `// If a[i] or (a[i]+1) is a power of 2` ` ` `if` `(isPowerOfTwo(a[i]) || isPowerOfTwo(a[i] + ` `1` `))` ` ` `count++;` ` ` `}` ` ` `return` `count;` `}` `// Driver code` `public` `static` `void` `main(String args[])` `{` ` ` `int` `arr[] = { ` `5` `, ` `6` `, ` `9` `, ` `3` `, ` `1` `};` ` ` `int` `n = arr.length;` ` ` `System.out.println(countNum(arr, n));` `}` `}` `// This code is contributed by` `// Sahil_Shelangia` |

## Python3

`# Python 3 implementation of the approach` `# Function that returns true if x` `# is a power of 2` `def` `isPowerOfTwo(x):` ` ` `if` `(x ` `=` `=` `0` `):` ` ` `return` `False` ` ` `# If x & (x-1) = 0 then x is a power of 2` ` ` `if` `((x & (x ` `-` `1` `)) ` `=` `=` `0` `):` ` ` `return` `True` ` ` `else` `:` ` ` `return` `False` `# Function to return the required count` `def` `countNum(a, n):` ` ` `count ` `=` `0` ` ` `for` `i ` `in` `range` `(` `0` `, n, ` `1` `):` ` ` ` ` `# If a[i] or (a[i]+1) is a power of 2` ` ` `if` `(isPowerOfTwo(a[i]) ` `or` ` ` `isPowerOfTwo(a[i] ` `+` `1` `)):` ` ` `count ` `+` `=` `1` ` ` `return` `count` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `arr ` `=` `[` `5` `, ` `6` `, ` `9` `, ` `3` `, ` `1` `]` ` ` `n ` `=` `len` `(arr)` ` ` `print` `(countNum(arr, n))` `# This code is contributed by` `# Sanjit_Prasad` |

## C#

`// C# implementation of the approach` `using` `System;` `class` `GFG` `{` `// Function that returns true if x is a power of 2` `static` `bool` `isPowerOfTwo(` `int` `x)` `{` ` ` `if` `(x == 0)` ` ` `return` `false` `;` ` ` `// If x & (x-1) = 0 then x is a power of 2` ` ` `if` `((x & (x - 1)) == 0)` ` ` `return` `true` `;` ` ` `else` ` ` `return` `false` `;` `}` `// Function to return the required count` `static` `int` `countNum(` `int` `[] a, ` `int` `n)` `{` ` ` `int` `count = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `{` ` ` `// If a[i] or (a[i]+1) is a power of 2` ` ` `if` `(isPowerOfTwo(a[i]) || isPowerOfTwo(a[i] + 1))` ` ` `count++;` ` ` `}` ` ` `return` `count;` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` `int` `[] arr = { 5, 6, 9, 3, 1 };` ` ` `int` `n = arr.Length;` ` ` `Console.WriteLine(countNum(arr, n));` `}` `}` `// This code is contributed by` `// Mukul Singh` |

## PHP

`<?php` `// PHP implementation of the approach` `// Function that returns true if x is` `// a power of 2` `function` `isPowerOfTwo( ` `$x` `)` `{` ` ` `if` `(` `$x` `== 0)` ` ` `return` `false;` ` ` `// If x & (x-1) = 0 then x is a` ` ` `// power of 2` ` ` `if` `(!(` `$x` `& (` `$x` `- 1)))` ` ` `return` `true;` ` ` `else` ` ` `return` `false;` `}` `// Function to return the required count` `function` `countNum(` `$a` `, ` `$n` `)` `{` ` ` `$cnt` `= 0;` ` ` `for` `( ` `$i` `= 0; ` `$i` `< ` `$n` `; ` `$i` `++)` ` ` `{` ` ` `// If a[i] or (a[i]+1) is a power of 2` ` ` `if` `(isPowerOfTwo(` `$a` `[` `$i` `]) ||` ` ` `isPowerOfTwo(` `$a` `[` `$i` `] + 1))` ` ` `$cnt` `++;` ` ` `}` ` ` `return` `$cnt` `;` `}` `// Driver Code` `$arr` `= ` `array` `( 5, 6, 9, 3, 1 );` `$n` `= ` `count` `(` `$arr` `);` `echo` `countNum(` `$arr` `, ` `$n` `);` `// This code is contributed by 29AjayKumar` `?>` |

## Javascript

`<script>` `// Javascript implementation of the approach` ` ` `// Function that returns true if x is a power of 2` `function` `isPowerOfTwo(x)` `{` ` ` `if` `(x == 0)` ` ` `return` `false` `;` ` ` ` ` `// If x & (x-1) = 0 then x is a power of 2` ` ` `if` `((x & (x - 1)) == 0)` ` ` `return` `true` `;` ` ` `else` ` ` `return` `false` `;` `}` `// Function to return the required count` `function` `countNum(a, n)` `{` ` ` `let count = 0;` ` ` ` ` `for` `(let i = 0; i < n; i++)` ` ` `{` ` ` ` ` `// If a[i] or (a[i]+1) is a power of 2` ` ` `if` `(isPowerOfTwo(a[i]) ||` ` ` `isPowerOfTwo(a[i] + 1))` ` ` `count++;` ` ` `}` ` ` `return` `count;` `}` `// Driver code` `let arr = [ 5, 6, 9, 3, 1 ];` `let n = arr.length;` `document.write(countNum(arr, n));` `// This code is contributed by unknown2108` `</script>` |

**Output:**

2