Given an array arr[] of N elements. The good value of an element arr[i] is the number of valid indices j<i such that arr[j] is divisible by arr[i].
Example:
Input: arr[] = {9, 6, 2, 3}
Output: 2
9 doesn’t has any element on its left.
6 doesn’t divide any element on its left.
2 divides 6.
3 divides 6 and 9.
Input: arr[] = {8, 1, 28, 4, 2, 6, 7}
Output: 3
Naive approach: For every element, find the count of numbers divisible by it on its left and print the maximum of these values.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum count // of required elements int findMax(int arr[], int n){ int res = 0; int i, j; // For every element in the array starting // from the second element for(i = 0; i < n ; i++) { // Check all the elements on the left // of current element which are divisible // by the current element int count = 0; for(j = 0; j < i; j++) { if (arr[j] % arr[i] == 0) count += 1; } res = max(count, res); } return res;}// Driver codeint main(){ int arr[] = { 8, 1, 28, 4, 2, 6, 7 }; int n = sizeof(arr) / sizeof(int); cout << findMax(arr, n); return 0;}// This code is contributed by Rajput-Ji |
Java
// Java implementation of the approach class GFG {// Function to return the maximum count // of required elements static int findMax(int arr[], int n){ int res = 0; int i, j; // For every element in the array starting // from the second element for(i = 0; i < n ; i++) { // Check all the elements on the left // of current element which are divisible // by the current element int count = 0; for(j = 0; j < i; j++) { if (arr[j] % arr[i] == 0) count += 1; } res = Math.max(count, res); } return res;}// Driver Codepublic static void main (String[] args){ int arr[] = {8, 1, 28, 4, 2, 6, 7}; int n = arr.length; System.out.println(findMax(arr, n));}}// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach# Function to return the maximum count # of required elementsdef findMax(arr, n): res = 0 # For every element in the array starting # from the second element for i in range(1, n): # Check all the elements on the left # of current element which are divisible # by the current element count = 0 for j in range(0, i): if arr[j] % arr[i] == 0: count += 1 res = max(count, res) return res# Driver codearr = [8, 1, 28, 4, 2, 6, 7]n = len(arr)print(findMax(arr, n)) |
C#
// C# implementation of the above approach using System; class GFG {// Function to return the maximum count // of required elements static int findMax(int []arr, int n){ int res = 0; int i, j; // For every element in the array // starting from the second element for(i = 0; i < n ; i++) { // Check all the elements on the left // of current element which are divisible // by the current element int count = 0; for(j = 0; j < i; j++) { if (arr[j] % arr[i] == 0) count += 1; } res = Math.Max(count, res); } return res;}// Driver Codepublic static void Main (String[] args){ int []arr = {8, 1, 28, 4, 2, 6, 7}; int n = arr.Length; Console.WriteLine(findMax(arr, n));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript implementation of the approach// Function to return the maximum count // of required elements function findMax(arr, n){ var res = 0; var i, j; // For every element in the array starting // from the second element for(i = 0; i < n ; i++) { // Check all the elements on the left // of current element which are divisible // by the current element var count = 0; for(j = 0; j < i; j++) { if (arr[j] % arr[i] == 0) count += 1; } res = Math.max(count, res); } return res;}// Driver codevar arr = [8, 1, 28, 4, 2, 6, 7];var n = arr.length;document.write( findMax(arr, n));</script> |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Efficient approach: It can be observed that for any element pair (arr[i], arr[j]) where i < j and (arr[i] % arr[j]) = 0, if the count of elements divisible by arr[i] on its left is X then the count of elements divisible by arr[j] on its left will definitely be greater than X as all the elements which are divisible by arr[i] will also be divisible by arr[j]. So, for every element which is divisible by any other element on its right, the count of elements on its left which are divisible by it doesn’t need to be calculated which will improve the time complexity of the overall program but it should be noted that for the input where no element is divisible by any other element (for example, when all the elements are prime), the worst-case time complexity would still be O(N2).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum count// of required elementsint findMax(int arr[], int n){ // divisible[i] will store true // if arr[i] is divisible by // any element on its right bool divisible[n] = { false }; // To store the maximum required count int res = 0; // For every element of the array for (int i = n - 1; i > 0; i--) { // If the current element is // divisible by any element // on its right if (divisible[i]) continue; // Find the count of element // on the left which are divisible // by the current element int cnt = 0; for (int j = 0; j < i; j++) { // If arr[j] is divisible then // set divisible[j] to true if ((arr[j] % arr[i]) == 0) { divisible[j] = true; cnt++; } } // Update the maximum required count res = max(res, cnt); } return res;}// Driver codeint main(){ int arr[] = { 8, 1, 28, 4, 2, 6, 7 }; int n = sizeof(arr) / sizeof(int); cout << findMax(arr, n); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to return the maximum count// of required elementsstatic int findMax(int arr[], int n){ // divisible[i] will store true // if arr[i] is divisible by // any element on its right boolean []divisible = new boolean[n]; // To store the maximum required count int res = 0; // For every element of the array for (int i = n - 1; i > 0; i--) { // If the current element is // divisible by any element // on its right if (divisible[i]) continue; // Find the count of element // on the left which are divisible // by the current element int cnt = 0; for (int j = 0; j < i; j++) { // If arr[j] is divisible then // set divisible[j] to true if ((arr[j] % arr[i]) == 0) { divisible[j] = true; cnt++; } } // Update the maximum required count res = Math.max(res, cnt); } return res;}// Driver codepublic static void main(String[] args) { int arr[] = { 8, 1, 28, 4, 2, 6, 7 }; int n = arr.length; System.out.println(findMax(arr, n));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function to return the maximum count # of required elements def findMax(arr, n) : # divisible[i] will store true # if arr[i] is divisible by # any element on its right divisible = [ False ] * n; # To store the maximum required count res = 0; # For every element of the array for i in range(n - 1, -1, -1) : # If the current element is # divisible by any element # on its right if (divisible[i]) : continue; # Find the count of element # on the left which are divisible # by the current element cnt = 0; for j in range(i) : # If arr[j] is divisible then # set divisible[j] to true if ((arr[j] % arr[i]) == 0) : divisible[j] = True; cnt += 1; # Update the maximum required count res = max(res, cnt); return res; # Driver code if __name__ == "__main__" : arr = [ 8, 1, 28, 4, 2, 6, 7 ]; n = len(arr); print(findMax(arr, n)); # This code is contributed by kanugargng |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the maximum count// of required elementsstatic int findMax(int []arr, int n){ // divisible[i] will store true // if arr[i] is divisible by // any element on its right bool []divisible = new bool[n]; // To store the maximum required count int res = 0; // For every element of the array for (int i = n - 1; i > 0; i--) { // If the current element is // divisible by any element // on its right if (divisible[i]) continue; // Find the count of element // on the left which are divisible // by the current element int cnt = 0; for (int j = 0; j < i; j++) { // If arr[j] is divisible then // set divisible[j] to true if ((arr[j] % arr[i]) == 0) { divisible[j] = true; cnt++; } } // Update the maximum required count res = Math.Max(res, cnt); } return res;}// Driver codepublic static void Main(String[] args) { int []arr = { 8, 1, 28, 4, 2, 6, 7 }; int n = arr.Length; Console.WriteLine(findMax(arr, n));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation of the approach// Function to return the maximum count// of required elementsfunction findMax(arr, n){ // divisible[i] will store true // if arr[i] is divisible by // any element on its right var divisible = Array(n).fill(false); // To store the maximum required count var res = 0; // For every element of the array for (var i = n - 1; i > 0; i--) { // If the current element is // divisible by any element // on its right if (divisible[i]) continue; // Find the count of element // on the left which are divisible // by the current element var cnt = 0; for (var j = 0; j < i; j++) { // If arr[j] is divisible then // set divisible[j] to true if ((arr[j] % arr[i]) == 0) { divisible[j] = true; cnt++; } } // Update the maximum required count res = Math.max(res, cnt); } return res;}// Driver codevar arr = [8, 1, 28, 4, 2, 6, 7];var n = arr.length;document.write( findMax(arr, n));</script> |
Output:
3
Time Complexity: O(n2)
Auxiliary Space: O(n), where n is the size of the given array.
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!
Share your thoughts in the comments
