LeetCode //C - 970. Powerful Integers

970. Powerful Integers

Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal to bound.

An integer is powerful if it can be represented as x i + y j x^i + y^j xi+yjfor some integers i >= 0 and j >= 0.

You may return the answer in any order. In your answer, each value should occur at most once.
 

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 2 0 + 3 0 2 = 2^0 + 3^0 2=20+30
3 = 2 1 + 3 0 3 = 2^1 + 3^0 3=21+30
4 = 2 0 + 3 1 4 = 2^0 + 3^1 4=20+31
5 = 2 1 + 3 1 5 = 2^1 + 3^1 5=21+31
7 = 2 2 + 3 1 7 = 2^2 + 3^1 7=22+31
9 = 2 3 + 3 0 9 = 2^3 + 3^0 9=23+30
10 = 2 0 + 3 2 10 = 2^0 + 3^2 10=20+32

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

Constraints:

• 1 <= x, y <= 100
• 0 < = b o u n d < = 10 6 0 <= bound <= 10^6 0<=bound<=106

From: LeetCode
Link: 970. Powerful Integers

Solution:

Ideas:

• A powerful integer is any number that can be written as x^i + y^j where i, j ≥ 0.
• Precompute all powers of x and y that do not exceed bound.
• Special case: if x == 1 or y == 1, only one power (1) exists for that base.
• Combine every x^i with every y^j and compute the sum.
• Use a seen array (or hash set) to avoid duplicates.
• Only keep sums ≤ bound.
• Collect all marked sums and return them as the final list.

Code:

/** * Note: The returned array must be malloced, assume caller calls free(). */int*powerfulIntegers(int x,int y,int bound,int* returnSize){if(bound <2){// smallest possible sum is 1^0 + 1^0 = 2*returnSize =0;returnNULL;}// Precompute powers of x and y up to `bound`int xp[32], yp[32];int xn =0, yn =0;int val =1;while(val <= bound){ xp[xn++]= val;if(x ==1)break;// further powers would be the sameif(val > bound / x)break; val *= x;} val =1;while(val <= bound){ yp[yn++]= val;if(y ==1)break;if(val > bound / y)break; val *= y;}// Use a boolean array to mark which sums have appeared (to avoid duplicates)char*seen =(char*)calloc(bound +1,sizeof(char));if(!seen){*returnSize =0;returnNULL;// allocation failure (unlikely on LeetCode)}int count =0;for(int i =0; i < xn;++i){for(int j =0; j < yn;++j){int sum = xp[i]+ yp[j];if(sum > bound)continue;if(!seen[sum]){ seen[sum]=1; count++;}}}int*res =(int*)malloc(sizeof(int)* count);if(!res){free(seen);*returnSize =0;returnNULL;}// Collect sums in any order; here we choose increasing orderint idx =0;for(int s =2; s <= bound;++s){if(seen[s]){ res[idx++]= s;}}free(seen);*returnSize = count;return res;}