Given an array arr[] consisting of N integers, the task is to find the sum of array elements that are equidistant from the two consecutive powers of 2.
Examples:
Input: arr[] = {10, 24, 17, 3, 8}
Output: 27
Explanation:
Following array elements are equidistant from two consecutive powers of 2:
- arr[1] (= 24) is equally separated from 24 and 25.
- arr[3] (= 3) is equally separated from 21 and 22.
Therefore, the sum of 24 and 3 is 27.
Input: arr[] = {17, 5, 6, 35}
Output: 6
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say res, that stores the sum of array elements.
- Traverse the given array arr[] and perform the following steps:
- Find the value of log2(arr[i]) and store it in a variable, say power.
- Find the value of 2(power) and 2(power + 1) and store them in variables, say LesserValue and LargerValue, respectively.
- If the value of (arr[i] – LesserValue) equal to (LargerValue – arr[i]), then increment the value of res by arr[i].
- After completing the above steps, print the value of res as the resultant sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the sum of array// elements that are equidistant from// two consecutive powers of 2int FindSum(int arr[], int N){ // Stores the resultant sum of the // array elements int res = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Stores the power of 2 of the // number arr[i] int power = log2(arr[i]); // Stores the number which is // power of 2 and lesser than // or equal to arr[i] int LesserValue = pow(2, power); // Stores the number which is // power of 2 and greater than // or equal to arr[i] int LargerValue = pow(2, power + 1); // If arr[i] - LesserValue is the // same as LargerValue-arr[i] if ((arr[i] - LesserValue) == (LargerValue - arr[i])) { // Increment res by arr[i] res += arr[i]; } } // Return the resultant sum res return res;}// Driver Codeint main(){ int arr[] = { 10, 24, 17, 3, 8 }; int N = sizeof(arr) / sizeof(arr[0]); cout << FindSum(arr, N); return 0;} |
Java
// Java program for the above approachclass GFG { // Function to print the sum of array // elements that are equidistant from // two consecutive powers of 2 static int FindSum(int[] arr, int N) { // Stores the resultant sum of the // array elements int res = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Stores the power of 2 of the // number arr[i] int power = (int)(Math.log(arr[i]) / Math.log(2)); // Stores the number which is // power of 2 and lesser than // or equal to arr[i] int LesserValue = (int)Math.pow(2, power); // Stores the number which is // power of 2 and greater than // or equal to arr[i] int LargerValue = (int)Math.pow(2, power + 1); // If arr[i] - LesserValue is the // same as LargerValue-arr[i] if ((arr[i] - LesserValue) == (LargerValue - arr[i])) { // Increment res by arr[i] res += arr[i]; } } // Return the resultant sum res return res; } // Driver Code public static void main(String[] args) { int[] arr = { 10, 24, 17, 3, 8 }; int N = arr.length; System.out.println(FindSum(arr, N)); }}// This code is contributed by ukasp. |
Python3
# Python3 program for the above approachfrom math import log2# Function to print sum of array# elements that are equidistant from# two consecutive powers of 2def FindSum(arr, N): # Stores the resultant sum of the # array elements res = 0 # Traverse the array arr[] for i in range(N): # Stores the power of 2 of the # number arr[i] power = int(log2(arr[i])) # Stores the number which is # power of 2 and lesser than # or equal to arr[i] LesserValue = pow(2, power) # Stores the number which is # power of 2 and greater than # or equal to arr[i] LargerValue = pow(2, power + 1) # If arr[i] - LesserValue is the # same as LargerValue-arr[i] if ((arr[i] - LesserValue) == (LargerValue - arr[i])): # Increment res by arr[i] res += arr[i] # Return the resultant sum res return res# Driver Codeif __name__ == '__main__': arr = [ 10, 24, 17, 3, 8 ] N = len(arr) print (FindSum(arr, N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System; class GFG{ // Function to print the sum of array// elements that are equidistant from// two consecutive powers of 2static int FindSum(int[] arr, int N){ // Stores the resultant sum of the // array elements int res = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Stores the power of 2 of the // number arr[i] int power = (int)(Math.Log(arr[i]) / Math.Log(2)); // Stores the number which is // power of 2 and lesser than // or equal to arr[i] int LesserValue = (int)Math.Pow(2, power); // Stores the number which is // power of 2 and greater than // or equal to arr[i] int LargerValue = (int)Math.Pow(2, power + 1); // If arr[i] - LesserValue is the // same as LargerValue-arr[i] if ((arr[i] - LesserValue) == (LargerValue - arr[i])) { // Increment res by arr[i] res += arr[i]; } } // Return the resultant sum res return res;} // Driver Codepublic static void Main(){ int[] arr= { 10, 24, 17, 3, 8 }; int N = arr.Length; Console.WriteLine(FindSum(arr, N));}}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript program for the above approach// Function to print the sum of array// elements that are equidistant from// two consecutive powers of 2function FindSum(arr, N){ // Stores the resultant sum of // the array elements let res = 0; // Traverse the array arr[] for(let i = 0; i < N; i++) { // Stores the power of 2 of the // number arr[i] let power = Math.floor( Math.log2(arr[i])); // Stores the number which is // power of 2 and lesser than // or equal to arr[i] let LesserValue = Math.pow(2, power); // Stores the number which is // power of 2 and greater than // or equal to arr[i] let LargerValue = Math.pow(2, power + 1); // If arr[i] - LesserValue is the // same as LargerValue-arr[i] if ((arr[i] - LesserValue) == (LargerValue - arr[i])) { // Increment res by arr[i] res += arr[i]; } } // Return the resultant sum res return res;}// Driver Codelet arr = [ 10, 24, 17, 3, 8 ];let N = arr.length;document.write(FindSum(arr, N));// This code is contributed by sanjoy_62</script> |
Output:
27
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
