# Count the number of elements in an array that can only divisible by even numbers except 1

Given an array arr[ ] of size N, count the number of elements in an array that have only contain even divisors (1 <= arr[ i ] <= 1014 and N <= 105)

Example:

`Input: {2, 4, 6, 8, 10}Output: 3Explanation : 2, 4, 8 only contain even divisors so output is 3, and 6 has odd divisor 3, 10 has odd divisor 5.`

Approach:

If a number contains only even divisors which means that number should be in the form only the power of 2 .

• Just traverse array arr [ ] and check if arr[i] & arr[i] — 1 is zero then number can be changed in the form of power of 2 and increase the count by 1
• Print the count as an output.

Below is the implementation of the above approach:

C++

`// C++ program to count the number //of elements in an array that have//only contain even divisors #include <bits/stdc++.h> using namespace std;   // function to count the number //of elements in an array that have//only contain even divisors void containEvenDivisor(long long int arr[],                          int N) {   	int count = 0;      for (int i = 0; i < N; i++) {           // Check if the number is         // not a power of two         if (a[i] > 1 && (arr[i] & (arr[i] - 1)) == 0)        {          //increase the count by one          count++;        }    }   	  	//print count as an output  	cout << count << endl;}   // Driver Code int main() {     long long int arr[] = {2, 4, 6, 8, 10};  	int N = sizeof(arr) / sizeof(arr);     // Function Call    containEvenDivisor(arr, N);     return 0; }Output: 3`

Time Complexity: O(N)

Space Complexity: O(N)

--

--