kapil16garg
Published in

kapil16garg

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: 3
Explanation : 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[0]);

// Function Call
containEvenDivisor(arr, N);

return 0;
}
Output: 3

Time Complexity: O(N)

Space Complexity: O(N)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kapilgarg

Kapilgarg

Just talk about programming and new tech