Print all array elements that are equidistant from two consecutive powers of 2

Print all array elements that are equidistant from two consecutive powers of 2

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:

1. arr[1] (= 24) is equally separated from 2⁴ and 2⁵.
2. arr[3] (= 3) is equally separated from 2¹ and 2².

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 log₂(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++

#include <bits/stdc++.h> using namespace std;    int FindSum(int arr[], int N) {               int res = 0;             for (int i = 0; i < N; i++) {                              int power = log2(arr[i]);                                       int LesserValue = pow(2, power);                                       int LargerValue = pow(2, power + 1);                              if ((arr[i] - LesserValue)             == (LargerValue - arr[i])) {                             res += arr[i];         }     }             return res; }    int main() {     int arr[] = { 10, 24, 17, 3, 8 };     int N = sizeof(arr) / sizeof(arr[0]);     cout << FindSum(arr, N);        return 0; }

Output:

27

Time Complexity: O(N)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets