Given an array arr[], the task is to count the number of elements from the array which divide the sum of all other elements.
Examples:
Input: arr[] = {3, 10, 4, 6, 7}
Output: 3
3 divides (10 + 4 + 6 + 7) i.e. 27
10 divides (3 + 4 + 6 + 7) i.e. 20
6 divides (3 + 10 + 4 + 7) i.e. 24Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Output: 2
Naive Approach: Run two-loop from 0 to N, calculate the sum of all elements except the current element and if this element divides that sum, then increment the count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// Function to return the count// of the required numbersint countNum(int N, int arr[]){ // To store the count of required numbers int count = 0; for (int i = 0; i < N; i++) { // Initialize sum to 0 int sum = 0; for (int j = 0; j < N; j++) { // If current element and the // chosen element are same if (i == j) continue; // Add all other numbers of array else sum += arr[j]; } // If sum is divisible by the chosen element if (sum % arr[i] == 0) count++; } // Return the count return count;}// Driver codeint main(){ int arr[] = { 3, 10, 4, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countNum(n, arr); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to return the count// of the required numbersstatic int countNum(int N, int arr[]){ // To store the count of required numbers int count = 0; for (int i = 0; i < N; i++) { // Initialize sum to 0 int sum = 0; for (int j = 0; j < N; j++) { // If current element and the // chosen element are same if (i == j) continue; // Add all other numbers of array else sum += arr[j]; } // If sum is divisible by the chosen element if (sum % arr[i] == 0) count++; } // Return the count return count;}// Driver codepublic static void main(String[] args){ int arr[] = { 3, 10, 4, 6, 7 }; int n = arr.length; System.out.println(countNum(n, arr));}}// This code is contributed by Code_Mech |
Python3
# Python3 implementation of the approach# Function to return the count# of the required numbersdef countNum(N, arr): # To store the count of # required numbers count = 0 for i in range(N): # Initialize sum to 0 Sum = 0 for j in range(N): # If current element and the # chosen element are same if (i == j): continue # Add all other numbers of array else: Sum += arr[j] # If Sum is divisible by the # chosen element if (Sum % arr[i] == 0): count += 1 # Return the count return count# Driver codearr = [3, 10, 4, 6, 7]n = len(arr)print(countNum(n, arr))# This code is contributed# by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG{ // Function to return the count// of the required numbersstatic int countNum(int N, int []arr){ // To store the count of required numbers int count = 0; for (int i = 0; i < N; i++) { // Initialize sum to 0 int sum = 0; for (int j = 0; j < N; j++) { // If current element and the // chosen element are same if (i == j) continue; // Add all other numbers of array else sum += arr[j]; } // If sum is divisible by the chosen element if (sum % arr[i] == 0) count++; } // Return the count return count;}// Driver codepublic static void Main(){ int []arr = { 3, 10, 4, 6, 7 }; int n = arr.Length; Console.WriteLine(countNum(n, arr));}}// This code is contributed by inder_verma.. |
PHP
<?php// Php implementation of the approach// Function to return the count// of the required numbersfunction countNum($N, $arr){// To store the count of// required numbers$count = 0;for ($i=0;$i<$N;$i++) {// Initialize sum to 0 $Sum = 0; for ($j = 0; $j < $N; $j++) { // If current element and the // chosen element are same if ($i == $j) continue; // Add all other numbers of array else $Sum += $arr[$j]; } // If Sum is divisible by the // chosen element if ($Sum % $arr[$i] == 0) $count += 1;}// Return the count return $count;}// Driver code$arr = array(3, 10, 4, 6, 7);$n = count($arr);echo countNum($n, $arr);// This code is contributed// by Srathore?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the count // of the required numbers function countNum(N, arr) { // To store the count of required numbers let count = 0; for (let i = 0; i < N; i++) { // Initialize sum to 0 let sum = 0; for (let j = 0; j < N; j++) { // If current element and the // chosen element are same if (i == j) continue; // Add all other numbers of array else sum += arr[j]; } // If sum is divisible by the chosen element if (sum % arr[i] == 0) count++; } // Return the count return count; } let arr = [ 3, 10, 4, 6, 7 ]; let n = arr.length; document.write(countNum(n, arr)); // This code is contributed by vaibhavrabadiya117</script> |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Efficient Approach: Run a single loop from 0 to N, calculate the sum of all the elements. Now run another loop from 0 to N and if (sum – arr[i]) % arr[i] = 0 then increment the count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// Function to return the count// of the required numbersint countNum(int N, int arr[]){ // Initialize sum and count to 0 int sum = 0, count = 0; // Calculate sum of all // the array elements for (int i = 0; i < N; i++) sum += arr[i]; for (int i = 0; i < N; i++) // If current element satisfies the condition if ((sum - arr[i]) % arr[i] == 0) count++; // Return the count of required elements return count;}// Driver codeint main(){ int arr[] = { 3, 10, 4, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countNum(n, arr); return 0;} |
Java
// Java implementation of the approachclass GFG { // Function to return the count // of the required numbers static int countNum(int N, int arr[]) { // Initialize sum and count to 0 int sum = 0, count = 0; // Calculate sum of all // the array elements for (int i = 0; i < N; i++) { sum += arr[i]; } // If current element satisfies the condition for (int i = 0; i < N; i++) { if ((sum - arr[i]) % arr[i] == 0) { count++; } } // Return the count of required elements return count; } // Driver code public static void main(String[] args) { int arr[] = {3, 10, 4, 6, 7}; int n = arr.length; System.out.println(countNum(n, arr)); }}// This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach# Function to return the count# of the required numbersdef countNum(N, arr): # Initialize Sum and count to 0 Sum, count = 0, 0 # Calculate Sum of all the # array elements for i in range(N): Sum += arr[i] for i in range(N): # If current element satisfies # the condition if ((Sum - arr[i]) % arr[i] == 0): count += 1 # Return the count of required # elements return count# Driver codearr = [ 3, 10, 4, 6, 7 ]n = len(arr)print(countNum(n, arr))# This code is contributed # by Mohit Kumar |
C#
// C# implementation of the approach using System;class GFG { // Function to return the count // of the required numbers static int countNum(int N, int []arr) { // Initialize sum and count to 0 int sum = 0, count = 0; // Calculate sum of all // the array elements for (int i = 0; i < N; i++) { sum += arr[i]; } // If current element satisfies the condition for (int i = 0; i < N; i++) { if ((sum - arr[i]) % arr[i] == 0) { count++; } } // Return the count of required elements return count; } // Driver code public static void Main() { int []arr = {3, 10, 4, 6, 7}; int n = arr.Length; Console.WriteLine(countNum(n, arr)); }}/* This code contributed by PrinciRaj1992 */ |
PHP
<?php// PHP implementation of the approach// Function to return the count// of the required numbersfunction countNum($N, $arr){ // Initialize sum and count to 0 $sum = 0; $count = 0; // Calculate sum of all // the array elements for ($i = 0; $i < $N; $i++) $sum += $arr[$i]; for ($i = 0; $i < $N; $i++) // If current element satisfies // the condition if (($sum - $arr[$i]) % $arr[$i] == 0) $count++; // Return the count of required elements return $count;}// Driver code$arr = array(3, 10, 4, 6, 7);$n = count($arr);echo countNum($n, $arr);// This code contributed by Rajput-Ji ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the count // of the required numbers function countNum(N, arr) { // Initialize sum and count to 0 let sum = 0, count = 0; // Calculate sum of all // the array elements for (let i = 0; i < N; i++) { sum += arr[i]; } // If current element satisfies the condition for (let i = 0; i < N; i++) { if ((sum - arr[i]) % arr[i] == 0) { count++; } } // Return the count of required elements return count; } let arr = [3, 10, 4, 6, 7]; let n = arr.length; document.write(countNum(n, arr)); </script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1), no extra space is required, so it is a constant.
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!
