Given an array arr[] consisting of N integers, the task is to count the number of integers in the range [1, arr[i]] that does not contain any odd divisors.
Examples:
Input: arr[] = {15, 16, 20, 35}
Output: 3 4 4 5
Explanation:
Numbers with no odd divisors from 1 to arr[0] ( = 15), are 2, 4, 8. Therefore, the count is 3.
Similarly, for arr[1] (= 16), arr[2] (= 20), arr[3] (= 35) the count is 4, 4 and 5 respectively.Input: arr[] = {24}
Output: 4
Naive Approach: The simplest approach is to traverse the array and for each array element arr[i], check if a number has any odd divisors in the range [1, arr[i]] or not. If it doesn’t have any odd divisors, increment the count. Otherwise, proceed to the next integer. Finally, print the count obtained for each array element arr[i].
Time Complexity: O(N*max(arr[i]))
Auxiliary Space: O(1)
Efficient Approach: The optimal idea is based on the following observation:
Observation:
Any number can be represented in the form of p1x1 * p2x2 *- – -*pNxN, where pi is a prime number and xi is its power. If the number doesn’t have any odd divisor, then it should not contain any odd prime factor.
Therefore, the problem reduces to finding the count of integers in the range 1 to N such that those numbers are a power of two, which can be done in log(N) time complexity by repeatedly checking for power of two such that 2i ? N and increasing count in every step.
Follow the steps below to solve the problem:
- Traverse the array arr[] and perform the following operations:
- Initialize two variables, say powerOfTwo, to check the maximum power of 2 which is less than arr[i] and another variable, say count, to store the count of integers in the range [1, arr[i]] having no odd divisors.
- Find for each array element, the value of powerOfTwo and count.
- Print them as the answer for each array element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count integers in the// range 1 to N having no odd divisorsvoid oddDivisors(int arr[], int N){ // Traverse the array for (int i = 0; i < N; i++) { // Stores the nearest power // of two less than arr[i] int powerOfTwo = 2; // Stores the count of integers // with no odd divisor for each query int count = 0; // Iterate until powerOfTwo is // less than or equal to arr[i] while (powerOfTwo <= arr[i]) { count++; powerOfTwo = 2 * powerOfTwo; } // Print the answer for // the current element cout << count << " "; } return;}// Driver Codeint main(){ // Given array int arr[] = { 15, 16, 20, 35 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); oddDivisors(arr, N); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{// Function to count integers in the// range 1 to N having no odd divisorsstatic void oddDivisors(int arr[], int N){ // Traverse the array for (int i = 0; i < N; i++) { // Stores the nearest power // of two less than arr[i] int powerOfTwo = 2; // Stores the count of integers // with no odd divisor for each query int count = 0; // Iterate until powerOfTwo is // less than or equal to arr[i] while (powerOfTwo <= arr[i]) { count++; powerOfTwo = 2 * powerOfTwo; } // Print the answer for // the current element System.out.print(count + " "); } return;}// Driver Codepublic static void main(String args[]){ // Given array int arr[] = { 15, 16, 20, 35 }; // Size of the array int N = arr.length; oddDivisors(arr, N);}}// This code is contributed by sanjoy_62. |
Python3
# Python3 program for the above approach# Function to count integers in the# range 1 to N having no odd divisorsdef oddDivisors(arr, N) : # Traverse the array for i in range(N) : # Stores the nearest power # of two less than arr[i] powerOfTwo = 2; # Stores the count of integers # with no odd divisor for each query count = 0; # Iterate until powerOfTwo is # less than or equal to arr[i] while (powerOfTwo <= arr[i]) : count += 1; powerOfTwo = 2 * powerOfTwo; # Print the answer for # the current element print(count, end = " ");# Driver Codeif __name__ == "__main__" : # Given array arr = [ 15, 16, 20, 35 ]; # Size of the array N = len(arr); oddDivisors(arr, N); # This code is contributed by AnkThon |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to count integers in the// range 1 to N having no odd divisorsstatic void oddDivisors(int[] arr, int N){ // Traverse the array for (int i = 0; i < N; i++) { // Stores the nearest power // of two less than arr[i] int powerOfTwo = 2; // Stores the count of integers // with no odd divisor for each query int count = 0; // Iterate until powerOfTwo is // less than or equal to arr[i] while (powerOfTwo <= arr[i]) { count++; powerOfTwo = 2 * powerOfTwo; } // Print the answer for // the current element Console.Write(count + " "); } return;}// Driver Codepublic static void Main(String[] args){ // Given array int[] arr = { 15, 16, 20, 35 }; // Size of the array int N = arr.Length; oddDivisors(arr, N);}}// This code is contributed by sanjoy_62. |
Javascript
<script>// JavaScript program to implement // the above approach // Function to count integers in the // range 1 to N having no odd divisors function oddDivisors(arr , N) { // Traverse the array for (i = 0; i < N; i++) { // Stores the nearest power // of two less than arr[i] var powerOfTwo = 2; // Stores the count of integers // with no odd divisor for each query var count = 0; // Iterate until powerOfTwo is // less than or equal to arr[i] while (powerOfTwo <= arr[i]) { count++; powerOfTwo = 2 * powerOfTwo; } // Print the answer for // the current element document.write(count + " "); } return; } // Driver Code // Given array var arr = [ 15, 16, 20, 35 ]; // Size of the array var N = arr.length; oddDivisors(arr, N);// This code contributed by aashish1995 </script> |
3 4 4 5
Time Complexity: O(N * log(max(arr[i]))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
