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 Rint 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 Codeint 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 approachimport 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 approachimport math# Function to count the number of elements# in the array having an odd number of# divisors from index L to Rdef 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 Codeif __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 Rfunction 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 Codeconst N = 5;const Q = 3;// Given array arr[]const arr = [2, 4, 5, 6, 9];// Given Queryconst Query = [ [0, 2], [1, 3], [1, 4]];// Iterating on queriesfor (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 divisorsvoid 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 Codeint 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 approachimport 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 divisorsstatic 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 Codepublic 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 approachimport math# Function count the number of elements# having odd number of divisorsdef 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 approachusing 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 divisorsstatic 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 Codepublic 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 divisorsfunction 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 Codevar N = 5;var Q = 3;// Given array arr[]var arr = [2, 4, 5, 6, 9];// Given Queryvar Query = [[0, 2 ], [1, 3 ], [1, 4 ]]; // Function CallOddDivisorsCount(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
