# Pair Sums to Power of Two - Google Top Interview Questions

### Problem Statement :

```You are given a list of integers nums. Return the number of pairs i < j such that nums[i] + nums[j] is equal to 2 ** k for some 0 ≤ k.

Constraints

0 ≤ n ≤ 100,000 where n is the length of nums

Example 1

Input

nums = [1, 1, 3, 5]

Output

4

Explanation

We can have the following pairs that sums to power of 2

(1, 1)

(1, 3)

(1, 3)

(3, 5)```

### Solution :

```                        ```Solution in C++ :

int solve(vector<int>& arr) {
unordered_map<int, int> mp;
for (int i : arr) mp[i]++;
int n = arr.size();
int ans = 0;
for (int i = 0; i < 32; i++) {
int sum = 1 << i;
for (int i = 0; i < n; i++) {
ans += mp[sum - arr[i]];
if (sum - arr[i] == arr[i]) ans--;
}
}
return ans / 2;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(int[] nums) {
ArrayList<Integer> powers = new ArrayList();
long two = 1;
while (two < Integer.MAX_VALUE) {
two *= 2;
}

HashMap<Integer, Integer> hm = new HashMap();
int n = nums.length;
int res = 0;
for (int i = 0; i < n; i++) {
int cur = nums[i];
for (int twos : powers) {
res += hm.getOrDefault(twos - cur, 0);
}
hm.put(cur, hm.getOrDefault(cur, 0) + 1);
}
return res;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, nums):
found = {}
ans = 0

powers = list(map(lambda x: 2 ** x, range(32)))

for num in nums:
for p in powers:
target = p - num

ans += found.get(target, 0)

found[num] = found.get(num, 0) + 1

return ans```
```

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element