GREEDY MOVES DAY 02 – Q5

C. Adding Powers

Problem Statement – https://codeforces.com/problemset/problem/1312/C

We will use bitmasking to solve this question. Let’s convert this number in k-system. Clearly, every element of a needs to be summation of some powers of k. Else you can just return 0.

Let us say that x is the element and powers of k are a,b,c.

remove the least of them (suppose a) and it becomes :

x = k^a(1 + k^(b-a) + k^(c-a)).

We can count this by recursively dividing x with k.

The neat code is here

bool visited[55];
ll n,k;
bool mark_it(ll num, ll index){
    if (num == 0) return 1; 
    if (num % k == 0){
        return mark_it(num/k,index+1);
    }
    else if (num % k == 1){
        if (visited[index]) return 0;
        visited[index] = 1;
        return mark_it(num-1,index);
    }
    else return 0;
}

void solve()
{
	
	cin >> n >> k;
	ll a[n];
	rep(i,0,n) cin >> a[i];  
    clr(visited,0);
    rep(i,0,n){
        if(!mark_it(a[i],0)){
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
    return;
    
}

Leave a Reply