Count of elements having odd number of divisors in index range [L, R] for Q queries

0 0 9 minutes read

Given an array arr[] of N positive integers and the number of queries Q, each query contains two numbers L and R. The task is to count the number of elements in the array having an odd number of divisors from index L to R.

Examples:

Input: arr[] = [2, 4, 5, 6, 9], Q = 3, Query[][] = { {0, 2}, {1, 3}, {1, 4} }
Output: 1 1 2
Explanation:
1st query: in 2 4 5 only 4 has an odd number of divisors.
2nd query: in 4 5 6 only 4 has an odd number of divisors.
3rd query: in 4 5 6 9 only 4, 9 has an odd number of divisors.

Input: arr[] = [1, 16, 5, 4, 9], Q = 2, Query[][] = { {1, 3}, {0, 2} }
Output: 2 1

Naive Approach: The naive approach is to iterate over the array from L to R for each query and count the elements in the range [L, R] having odd numbers of divisors. If yes then count that element for that query.

Below is the implementation of the above approach:

C++14

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of elements
// in the array having an odd number of
// divisors from index L to R
int OddDivisorsCount(int arr[], int N, int L, int R)
{
    int count = 0;
    for (int i = L; i <= R; i++) {
        int divisors = 0;
        for (int j = 1; j <= sqrt(arr[i]); j++) {
            if (arr[i] % j == 0) {
                if (arr[i] / j == j) {
                    divisors++;
                }
                else {
                    divisors += 2;
                }
            }
        }
        if (divisors % 2 != 0) {
            count++;
        }
    }
    return count;
}
 
// Driver Code
int main()
{
    int N = 5;
    int Q = 3;
 
    // Given array arr[]
    int arr[] = { 2, 4, 5, 6, 9 };
 
    // Given Query
    vector<pair<int, int> > Query
        = { { 0, 2 }, { 1, 3 }, { 1, 4 } };
 
    // Iterating on queries
    for (int i = 0; i < Q; i++) {
        int L = Query[i].first;
        int R = Query[i].second;
        cout << OddDivisorsCount(arr, N, L, R) << endl;
    }
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class Pair<A, B> {
    A first;
    B second;
 
    public Pair(A first, B second) {
        this.first = first;
        this.second = second;
    }
 
    public A getFirst() {
        return first;
    }
 
    public B getSecond() {
        return second;
    }
}
 
public class Main {
    // Function to count the number of elements
    // in the array having an odd number of
    // divisors from index L to R
    static int oddDivisorsCount(int[] arr, int N, int L, int R) {
        int count = 0;
        for (int i = L; i <= R; i++) {
            int divisors = 0;
            for (int j = 1; j <= Math.sqrt(arr[i]); j++) {
                if (arr[i] % j == 0) {
                    if (arr[i] / j == j) {
                        divisors++;
                    } else {
                        divisors += 2;
                    }
                }
            }
            if (divisors % 2 != 0) {
                count++;
            }
        }
        return count;
    }
 
    // Driver Code
    public static void main(String[] args) {
        int N = 5;
        int Q = 3;
 
        // Given array arr[]
        int[] arr = { 2, 4, 5, 6, 9 };
 
        // Given Query
        List<Pair<Integer, Integer>> Query = new ArrayList<>();
        Query.add(new Pair<>(0, 2));
        Query.add(new Pair<>(1, 3));
        Query.add(new Pair<>(1, 4));
 
        // Iterating on queries
        for (int i = 0; i < Q; i++) {
            int L = Query.get(i).getFirst();
            int R = Query.get(i).getSecond();
            System.out.println(oddDivisorsCount(arr, N, L, R));
        }
    }
}

Python3

# Python implementation of the approach
import math
 
# Function to count the number of elements
# in the array having an odd number of
# divisors from index L to R
def OddDivisorsCount(arr, N, L, R):
    count = 0
    for i in range(L, R + 1):
        divisors = 0
        for j in range(1, int(math.sqrt(arr[i])) + 1):
            if arr[i] % j == 0:
                if arr[i] // j == j:
                    divisors += 1
                else:
                    divisors += 2
        if divisors % 2 != 0:
            count += 1
    return count
 
# Driver Code
if __name__ == "__main__":
    N = 5
    Q = 3
 
    # Given array arr[]
    arr = [2, 4, 5, 6, 9]
 
    # Given Query
    Query = [(0, 2), (1, 3), (1, 4)]
 
    # Iterating on queries
    for i in range(Q):
        L = Query[i][0]
        R = Query[i][1]
        print(OddDivisorsCount(arr, N, L, R))

C#

using System;
using System.Collections.Generic;
 
class Program
{
    // Function to count the number of elements
    // in the array having an odd number of divisors from index L to R
    static int OddDivisorsCount(int[] arr, int N, int L, int R)
    {
        int count = 0;
        for (int i = L; i <= R; i++)
        {
            int divisors = 0;
            for (int j = 1; j * j <= arr[i]; j++)
            {
                if (arr[i] % j == 0)
                {
                    if (arr[i] / j == j)
                    {
                        divisors++;
                    }
                    else
                    {
                        divisors += 2;
                    }
                }
            }
            if (divisors % 2 != 0)
            {
                count++;
            }
        }
        return count;
    }
 
    static void Main()
    {
        int N = 5;
        int Q = 3;
 
        // Given array arr[]
        int[] arr = { 2, 4, 5, 6, 9 };
 
        // Given Query
        List<Tuple<int, int>> Query = new List<Tuple<int, int>>
        {
            new Tuple<int, int>(0, 2),
            new Tuple<int, int>(1, 3),
            new Tuple<int, int>(1, 4)
        };
 
        // Iterating on queries
        for (int i = 0; i < Q; i++)
        {
            int L = Query[i].Item1;
            int R = Query[i].Item2;
            Console.WriteLine(OddDivisorsCount(arr, N, L, R));
        }
    }
}

Javascript

// Function to count the number of elements
// in the array having an odd number of
// divisors from index L to R
function OddDivisorsCount(arr, L, R) {
    let count = 0;
    for (let i = L; i <= R; i++) {
        let divisors = 0;
        for (let j = 1; j <= Math.sqrt(arr[i]); j++) {
            if (arr[i] % j === 0) {
                if (arr[i] / j === j) {
                    divisors++;
                } else {
                    divisors += 2;
                }
            }
        }
        if (divisors % 2 !== 0) {
            count++;
        }
    }
    return count;
}
 
// Driver Code
const N = 5;
const Q = 3;
 
// Given array arr[]
const arr = [2, 4, 5, 6, 9];
 
// Given Query
const Query = [
    [0, 2],
    [1, 3],
    [1, 4]
];
 
// Iterating on queries
for (let i = 0; i < Q; i++) {
    const L = Query[i][0];
    const R = Query[i][1];
    console.log(OddDivisorsCount(arr, L, R));
}

Output:

1
1
2

Time Complexity: O(Q * N * sqrt(N))
Auxiliary Space: O(1)

Efficient Approach: We can observe that the number of divisors is odd only in case of perfect squares. Hence the best solution is to check if the given number is a perfect square or not in the range [L, R]. Below are the steps:

Initialize the array dp[] of size N with value 0.
Traverse the given array arr[] and if any element in the it is a perfect square the update the value at that index in dp[] as 1.
To calculate the answer for each query efficiently we will precompute the answer.
We will do the prefix sum of the array dp[] and for each query in the range [L, R] the answer will be given by:

OddDivisorCount(L, R) = DP[R] - DP[L-1]

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function count the number of elements
// having odd number of divisors
void OddDivisorsCount(
    int n, int q, int a[],
    vector<pair<int, int> > Query)
{
    // Initialise dp[] array
    int DP[n] = { 0 };
 
    // Precomputation
    for (int i = 0; i < n; i++) {
        int x = sqrt(a[i]);
 
        if (x * x == a[i])
            DP[i] = 1;
    }
 
    // Find the Prefix Sum
    for (int i = 1; i < n; i++) {
        DP[i] = DP[i - 1] + DP[i];
    }
 
    int l, r;
 
    // Iterate for each query
    for (int i = 0; i < q; i++) {
        l = Query[i].first;
        r = Query[i].second;
 
        // Find the answer for each query
        if (l == 0) {
            cout << DP[r] << endl;
        }
        else {
            cout << DP[r] - DP[l - 1]
                 << endl;
        }
    }
}
 
// Driver Code
int main()
{
    int N = 5;
    int Q = 3;
 
    // Given array arr[]
    int arr[] = { 2, 4, 5, 6, 9 };
 
    // Given Query
    vector<pair<int, int> > Query
        = { { 0, 2 }, { 1, 3 }, { 1, 4 } };
 
    // Function Call
    OddDivisorsCount(N, Q, arr, Query);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static class pair
{ 
    int first, second; 
    public pair(int first, int second) 
    { 
        this.first = first; 
        this.second = second; 
    } 
} 
 
// Function count the number of elements
// having odd number of divisors
static void OddDivisorsCount(int n, int q,
                             int a[], 
                             pair []Query)
{
     
    // Initialise dp[] array
    int DP[] = new int[n];
 
    // Precomputation
    for(int i = 0; i < n; i++)
    {
       int x = (int)Math.sqrt(a[i]);
        
       if (x * x == a[i])
           DP[i] = 1;
    }
     
    // Find the Prefix Sum
    for(int i = 1; i < n; i++)
    {
       DP[i] = DP[i - 1] + DP[i];
    }
     
    int l, r;
 
    // Iterate for each query
    for(int i = 0; i < q; i++)
    {
       l = Query[i].first;
       r = Query[i].second;
        
       // Find the answer for each query
       if (l == 0)
       {
           System.out.print(DP[r] + "\n");
       }
       else
       {
           System.out.print(DP[r] - 
                            DP[l - 1] + "\n");
       }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5;
    int Q = 3;
 
    // Given array arr[]
    int arr[] = { 2, 4, 5, 6, 9 };
 
    // Given Query
    pair []Query = { new pair(0, 2),
                     new pair(1, 3), 
                     new pair(1, 4) };
 
    // Function Call
    OddDivisorsCount(N, Q, arr, Query);
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 program for the above approach
import math
 
# Function count the number of elements
# having odd number of divisors
def OddDivisorsCount(n, q, a, Query):
     
    # Initialise dp[] array
    DP = [0 for i in range(n)]
  
    # Precomputation
    for i in range(n):
        x = int(math.sqrt(a[i]));
  
        if (x * x == a[i]):
            DP[i] = 1;
  
    # Find the Prefix Sum
    for i in range(1, n):
        DP[i] = DP[i - 1] + DP[i];
  
    l = 0
    r = 0
  
    # Iterate for each query
    for i in range(q):
        l = Query[i][0];
        r = Query[i][1];
  
        # Find the answer for each query
        if (l == 0):
            print(DP[r])
        else:
            print(DP[r] - DP[l - 1])
 
# Driver code 
if __name__=="__main__":
     
    N = 5;
    Q = 3;
  
    # Given array arr[]
    arr = [ 2, 4, 5, 6, 9 ]
  
    # Given Query
    Query = [ [ 0, 2 ], 
              [ 1, 3 ],
              [ 1, 4 ] ]
  
    # Function call
    OddDivisorsCount(N, Q, arr, Query);
 
# This code is contributed by rutvik_56

C#

// C# program for the above approach
using System;
 
class GFG{
class pair
{ 
    public int first, second; 
    public pair(int first, int second) 
    { 
        this.first = first; 
        this.second = second; 
    } 
} 
 
// Function count the number of elements
// having odd number of divisors
static void OddDivisorsCount(int n, int q,
                             int []a, 
                             pair []Query)
{
     
    // Initialise []dp array
    int []DP = new int[n];
 
    // Precomputation
    for(int i = 0; i < n; i++)
    {
       int x = (int)Math.Sqrt(a[i]);
       if (x * x == a[i])
           DP[i] = 1;
    }
     
    // Find the Prefix Sum
    for(int i = 1; i < n; i++)
    {
       DP[i] = DP[i - 1] + DP[i];
    }
     
    int l, r;
 
    // Iterate for each query
    for(int i = 0; i < q; i++)
    {
       l = Query[i].first;
       r = Query[i].second;
        
       // Find the answer for each query
       if (l == 0)
       {
           Console.Write(DP[r] + "\n");
       }
       else
       {
           Console.Write(DP[r] - 
                         DP[l - 1] + "\n");
       }
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 5;
    int Q = 3;
 
    // Given array []arr
    int []arr = { 2, 4, 5, 6, 9 };
 
    // Given Query
    pair []Query = { new pair(0, 2),
                     new pair(1, 3), 
                     new pair(1, 4) };
 
    // Function Call
    OddDivisorsCount(N, Q, arr, Query);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript program for the above approach
 
// Function count the number of elements
// having odd number of divisors
function OddDivisorsCount(
    n, q, a,Query)
{
 
    // Initialise dp[] array
    var DP = new Array(n).fill(0);
 
    // Precomputation
    for (var i = 0; i < n; i++) {
        var x = Math.sqrt(a[i]);
 
        if (x * x == a[i])
            DP[i] = 1;
    }
 
    // Find the Prefix Sum
    for (var i = 1; i < n; i++) {
        DP[i] = DP[i - 1] + DP[i];
    }
 
    var l, r;
 
    // Iterate for each query
    for (var i = 0; i < q; i++) {
        l = Query[i][0];
        r = Query[i][1];
 
        // Find the answer for each query
        if (l == 0) {
            document.write( DP[r] + "<br>");
        }
        else {
            document.write( DP[r] - DP[l - 1]+ "<br>");
        }
    }
}
 
// Driver Code
var N = 5;
var Q = 3;
 
// Given array arr[]
var arr = [2, 4, 5, 6, 9];
 
// Given Query
var Query
    = [[0, 2 ], [1, 3 ], [1, 4 ]];
     
// Function Call
OddDivisorsCount(N, Q, arr, Query);
 
// This code is contributed by noob2000.
</script>

Output

1
1
2

Time complexity:

Precomputation: O(N)
For each query: O(1)

Auxiliary Space: O(n)

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 zambiatek!