Given an array of positive numbers, the task is to find the bitwise AND of the sum of non-prime numbers and the sum of prime numbers. Note that 1 is neither prime nor composite.
Examples:
Input: arr[] = {1, 3, 5, 10, 15, 7}
Output: 9
Sum of non-primes = 10 + 15 = 25
Sum of primes = 3 + 5 + 7 = 15
25 & 15 = 9
Input: arr[] = {3, 4, 6, 7}
Output: 10
Naive approach: A simple solution is to traverse the array and keep checking for every element if it is prime or not. If the number is prime, then add it to S1 which stores the sum of prime numbers from the array else add it to S2 which stores the sum of non-prime numbers. Finally, print S1 & S2.
Time complexity: O(N * sqrt(N))
Efficient approach: Generate all the primes up to the maximum element of the array using the Sieve of Eratosthenes and store them in a hash. Now, traverse the array and check if the number is prime or not. In the end, calculate and print the bitwise AND of the sum of prime numbers and the sum of composite numbers.
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 bitwise AND of the// sum of primes and the sum of non-primesint calculateAND(int arr[], int n){ // Find maximum value in the array int max_val = *max_element(arr, arr + n); // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. vector<bool> prime(max_val + 1, true); // Remaining part of SIEVE prime[0] = false; prime[1] = false; for (int p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= max_val; i += p) prime[i] = false; } } // Store the sum of primes in S1 and // the sum of non-primes in S2 int S1 = 0, S2 = 0; for (int i = 0; i < n; i++) { if (prime[arr[i]]) { // The number is prime S1 += arr[i]; } else if (arr[i] != 1) { // The number is not prime S2 += arr[i]; } } // Return the bitwise AND of the sums return (S1 & S2);}// Driver codeint main(){ int arr[] = { 3, 4, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << calculateAND(arr, n); return 0;} |
Java
// Java implementation of the approach import java.util.Arrays; import java.util.Collections; import java.util.List;class GFG{ static int getMax(int[] A) { int max = Integer.MIN_VALUE; for (int i: A) { max = Math.max(max, i); } return max; } // Function to return the bitwise AND of the // sum of primes and the sum of non-primes static int calculateAND(int arr[], int n) { // using Collections.max() to find // maximum element using only 1 line. // Find maximum value in the array int max_val = getMax(arr); // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. boolean prime[] = new boolean [max_val + 1]; int i; for (i = 0; i < max_val + 1; i++) prime[i] = true; // Remaining part of SIEVE prime[0] = false; prime[1] = false; for (int p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for ( i = p * 2; i <= max_val; i += p) prime[i] = false; } } // Store the sum of primes in S1 and // the sum of non-primes in S2 int S1 = 0, S2 = 0; for (i = 0; i < n; i++) { if (prime[arr[i]]) { // The number is prime S1 += arr[i]; } else if (arr[i] != 1) { // The number is not prime S2 += arr[i]; } } // Return the bitwise AND of the sums return (S1 & S2); } // Driver code public static void main (String[] args) { int arr[] = { 3, 4, 6, 7 }; int n = arr.length; System.out.println(calculateAND(arr, n)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach# Function to return the bitwise AND of the# sum of primes and the sum of non-primesdef calculateAND(arr, n): # Find maximum value in the array max_val = max(arr) # USE SIEVE TO FIND ALL PRIME NUMBERS # LESS THAN OR EQUAL TO max_val # Create a boolean array "prime[0..n]". # A value in prime[i] will finally be false # if i is Not a prime, else true. prime = [True for i in range(max_val + 1)] # Remaining part of SIEVE prime[0] = False prime[1] = False for p in range(2, max_val + 1): if p * p >= max_val: break # If prime[p] is not changed, # then it is a prime if (prime[p]): # Update all multiples of p for i in range(2 * p, max_val + 1, p): prime[i] = False # Store the sum of primes in S1 and # the sum of non-primes in S2 S1 = 0 S2 = 0 for i in range(n): if (prime[arr[i]]): # The number is prime S1 += arr[i] elif (arr[i] != 1): # The number is not prime S2 += arr[i] # Return the bitwise AND of the sums return (S1 & S2)# Driver codearr = [3, 4, 6, 7]n = len(arr)print(calculateAND(arr, n))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG{ static int getMax(int[] A) { int max = int.MinValue; foreach (int i in A) { max = Math.Max(max, i); } return max; } // Function to return the bitwise AND of the // sum of primes and the sum of non-primes static int calculateAND(int []arr, int n) { // using Collections.max() to find // maximum element using only 1 line. // Find maximum value in the array int max_val = getMax(arr); // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. bool []prime = new bool [max_val + 1]; int i; for (i = 0; i < max_val + 1; i++) prime[i] = true; // Remaining part of SIEVE prime[0] = false; prime[1] = false; for (int p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (i = p * 2; i <= max_val; i += p) prime[i] = false; } } // Store the sum of primes in S1 and // the sum of non-primes in S2 int S1 = 0, S2 = 0; for (i = 0; i < n; i++) { if (prime[arr[i]]) { // The number is prime S1 += arr[i]; } else if (arr[i] != 1) { // The number is not prime S2 += arr[i]; } } // Return the bitwise AND of the sums return (S1 & S2); } // Driver code public static void Main (String[] args) { int []arr = { 3, 4, 6, 7 }; int n = arr.Length; Console.WriteLine(calculateAND(arr, n)); } } // This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approach// Function to return the bitwise AND of the// sum of primes and the sum of non-primesfunction calculateAND(arr, n){ // Find maximum value in the array var max_val = arr.reduce((a,b)=>Math.max(a,b)); // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. var prime = Array(max_val + 1).fill(true); // Remaining part of SIEVE prime[0] = false; prime[1] = false; for (var p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (var i = p * 2; i <= max_val; i += p) prime[i] = false; } } // Store the sum of primes in S1 and // the sum of non-primes in S2 var S1 = 0, S2 = 0; for (var i = 0; i < n; i++) { if (prime[arr[i]]) { // The number is prime S1 += arr[i]; } else if (arr[i] != 1) { // The number is not prime S2 += arr[i]; } } // Return the bitwise AND of the sums return (S1 & S2);}// Driver codevar arr = [ 3, 4, 6, 7 ];var n = arr.length;document.write( calculateAND(arr, n));</script> |
Output:
10
Time Complexity: O(N * log(log(N))
Space Complexity: O(max_val) where max_val is the maximum value of an element in 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!
