Sum of all the Composite Numbers from Odd indices of the given array
Given an array arr[] of size N which contains at least one composite number. The task is to find out the sum of all the composite numbers in the array which are at odd indices (where indexing is 1 based).
Examples:
Input: arr = [13, 5, 8, 16, 25]
Output: 33
Explanation:
The number in the odd indices are 13, 8, 25 since we follow 1 based indexing.
Out of all these 3 numbers, the composite numbers are 8 and 25, which sums to 33.Input: arr = [9, 7, 14, 10, 34]
Output: 57
Explanation:
The number in the odd indices are 9, 14, 34 since we follow 1 based indexing.
All three numbers are composite numbers, which sums to 57.
Approach:
To solve the problem mentioned above the main idea is to check for the composite numbers that is, if an integer has more than 2 factors then it’s a composite number otherwise it is not. Then we will iterate and check for the composite numbers in odd indices of the array. If it is a composite number then we will add it to the sum variable otherwise skip it until the end of the array reaches.
Below is the implementation of the above approach:
C++
// C++ implementation to find the sum of all the // composite numbers from odd indices of the given array #include<bits/stdc++.h> using namespace std; // Function to check for composite numbers int composite( int n){ int flag = 0; int c = 0; // Check if the factors are greater than 2 for ( int j = 1; j <= n; j++){ if (n % j == 0){ c += 1; } } // Check if the number is composite or not if (c >= 3) flag = 1; return flag; } // Function to print the sum of all // composite numbers in the array void odd_indices( int arr[], int n){ int sum = 0; // Iterate for odd indices in the array for ( int k = 0; k < n; k += 2){ int check = composite(arr[k]); // Check if the number is composite // then add it to sum if (check == 1) sum += arr[k]; } // return the sum cout << sum << endl; } // Driver code int main(){ int arr[] = {13, 5, 8, 16, 25}; int n = sizeof (arr)/ sizeof (arr[0]); odd_indices(arr,n); } // This code is contributed by Surendra_Gangwar |
Java
// Java implementation to find the sum of all the // composite numbers from odd indices of the given array class GFG{ // Function to check for composite numbers static int composite( int n){ int flag = 0 ; int c = 0 ; // Check if the factors are greater than 2 for ( int j = 1 ; j <= n; j++){ if (n % j == 0 ){ c += 1 ; } } // Check if the number is composite or not if (c >= 3 ) flag = 1 ; return flag; } // Function to print the sum of all // composite numbers in the array static void odd_indices( int arr[], int n){ int sum = 0 ; // Iterate for odd indices in the array for ( int k = 0 ; k < n; k += 2 ){ int check = composite(arr[k]); // Check if the number is composite // then add it to sum if (check == 1 ) sum += arr[k]; } // return the sum System.out.print(sum + "\n" ); } // Driver code public static void main(String[] args){ int arr[] = { 13 , 5 , 8 , 16 , 25 }; int n = arr.length; odd_indices(arr,n); } } // This code contributed by sapnasingh4991 |
Python3
# Python3 implementation to find the sum of all the # composite numbers from odd indices of the given array # Function to print the sum of all # composite numbers in the array def odd_indices(arr): sum = 0 # Iterate for odd indices in the array for k in range ( 0 , len (arr), 2 ): check = composite (arr[k]) # Check if the number is composite # then add it to sum sum + = arr[k] if check = = 1 else 0 # return the sum print ( sum ) # Function to check for composite numbers def composite(n): flag = 0 c = 0 # Check if the factors are greater than 2 for j in range ( 1 , n + 1 ): if (n % j = = 0 ): c + = 1 # Check if the number is composite or not if (c > = 3 ): flag = 1 return flag # Driver code if __name__ = = "__main__" : arr = [ 13 , 5 , 8 , 16 , 25 ] odd_indices(arr) |
C#
// C# implementation to find the sum // of all the composite numbers from // odd indices of the given array using System; class GFG{ // Function to check for composite numbers static int composite( int n) { int flag = 0; int c = 0; // Check if the factors are greater than 2 for ( int j = 1; j <= n; j++) { if (n % j == 0) { c += 1; } } // Check if the number is composite or not if (c >= 3) flag = 1; return flag; } // Function to print the sum of all // composite numbers in the array static void odd_indices( int []arr, int n) { int sum = 0; // Iterate for odd indices in the array for ( int k = 0; k < n; k += 2) { int check = composite(arr[k]); // Check if the number is composite // then add it to sum if (check == 1) sum += arr[k]; } // return the sum Console.Write(sum + "\n" ); } // Driver code public static void Main(String[] args) { int []arr = { 13, 5, 8, 16, 25 }; int n = arr.Length; odd_indices(arr, n); } } // This code is contributed by Rohit_ranjan |
Javascript
<script> // Javascript implementation to find the sum of all the // composite numbers from odd indices of the given array // Function to check for composite numbers function composite(n){ let flag = 0; let c = 0; // Check if the factors are greater than 2 for (let j = 1; j <= n; j++){ if (n % j == 0){ c += 1; } } // Check if the number is composite or not if (c >= 3) flag = 1; return flag; } // Function to print the sum of all // composite numbers in the array function odd_indices(arr, n){ let sum = 0; // Iterate for odd indices in the array for (let k = 0; k < n; k += 2){ let check = composite(arr[k]); // Check if the number is composite // then add it to sum if (check == 1) sum += arr[k]; } // return the sum document.write(sum + "<br>" ); } // Driver code let arr = [13, 5, 8, 16, 25]; let n = arr.length odd_indices(arr,n); // This code is contributed by gfgking </script> |
33
Time Complexity: O(n * m), where n is the length of the given array and m is the maximum element in the array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Contact Us