package LeetCode_1711

/**
 * 1711. Count Good Meals
 * https://leetcode.com/problems/count-good-meals/
 * A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.
You can pick any two different foods to make a good meal.
Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i​​​​​​th​​​​​​​​ item of food,
return the number of different good meals you can make from this list modulo 10^9 + 7.
Note that items with different indices are considered different even if they have the same deliciousness value.

Example 1:
Input: deliciousness = [1,3,5,7,9]
Output: 4
Explanation: The good meals are (1,3), (1,7), (3,5) and, (7,9).
Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.

Example 2:
Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15
Explanation: The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.

Constraints:
1. 1 <= deliciousness.length <= 10^5
2. 0 <= deliciousness[i] <= 2^20
 * */
class Solution {
    /*
    * solution 1: bruce force, Time:O(n^2), TLE;
    * solution 2: HashMap, TwoSum solution, Time:O(n), Space:O(n);
    * */
    fun countPairs(deliciousness: IntArray): Int {
        var result = 0
        
        //solution 1:
        /*for (i in deliciousness.indices) {
            for (j in i until deliciousness.size) {
                if (i != j) {
                    if (isPowOfTwo(deliciousness[i] + deliciousness[j])) {
                        result++
                    }
                }
            }
        }*/
        
        //solution 2:
        val mod = 1000000007
        //key:num, value:the number of times (target-num) occurrence
        val map = HashMap<Int, Int>()
        for (num in deliciousness) {
            var power = 1
            //handle int32, because 0 <= deliciousness[i] <= 2^20
            for (i in 0..31) {
                //power just like a target, because (1+3=4) or (1+7=8), they are sum are powers of 2, so have to find (power-num)
                val needToFind = power - num
                if (map.containsKey(needToFind)) {
                    result += map.get(needToFind)!!
                    result %= mod
                }
                power *= 2
            }
            map.put(num, map.getOrDefault(num, 0) + 1)
        }
        return result
    }

    private fun isPowOfTwo(n_: Int): Boolean {
        var n = n_
        if (n == 0) {
            return false
        }
        while (n != 1) {
            if (n % 2 != 0) {
                return false
            }
            n /= 2
        }
        return true
    }
}