medium
0 views

Count of Power of X

Count the number of integers in a list that are exact powers of a given base number X

Understand the Problem

Problem Statement

Given N positive integers vi where i = 1 to N, count the number C of values that are exact powers of X.

A number v is considered a power of X if there exists a non-negative integer k such that v = Xk.

Constraints

  • 1 ≤ N ≤ 106
  • 1 ≤ vi ≤ 1018
  • 1 ≤ X ≤ 106
  • All input values are positive integers
  • For X = 1, only the value 1 should be counted as a valid power

Examples

Example 1
Input
9 5
25 15 125 35 625 380625 152587890625 10 90
Output
4
Explanation

The powers of 5 in the list are: 25 (5²), 125 (5³), 625 (5⁴), and 152587890625 (5¹⁶). The other values (15, 35, 380625, 10, 90) are not powers of 5.

Example 2
Input
7 2
1 2 4 8 16 20 32
Output
6
Explanation

All values except 20 are powers of 2: 1 (2⁰), 2 (2¹), 4 (2²), 8 (2³), 16 (2⁴), and 32 (2⁵).

Solution

#include <stdio.h>
#include <stdbool.h>

bool isPowerOfX(long long value, int X) {
    if (X == 1) {
        return value == 1;
    }
    
    long long power = 1;
    while (power < value) {
        power *= X;
    }
    
    return power == value;
}

int main() {
    int N, X;
    scanf("%d %d", &N, &X);
    
    long long values[1000000];
    for (int i = 0; i < N; i++) {
        scanf("%lld", &values[i]);
    }
    
    int count = 0;
    for (int i = 0; i < N; i++) {
        if (isPowerOfX(values[i], X)) {
            count++;
        }
    }
    
    printf("%d\n", count);
    return 0;
}
Time:O(N × logₐ(max_value)) where a is the base X. In worst case, for each of N values we may need logₐ(v) multiplications.
Space:O(N) for storing the input array
Approach:

C Implementation:

1. isPowerOfX() function checks if a value is a power of X 2. Special case for X = 1: only returns true for value = 1 3. For other cases, iteratively multiplies by X until reaching or exceeding the target 4. Main function reads input, processes all values, and counts matches 5. Uses long long to handle values up to 10¹⁸

Visual Explanation

Loading diagram...
All Problems
Count of Power of X | Letuscrack