In this HackerEarth Very Cool Numbers problem solution For a number X, let its "Coolness" be defined as the number of "101"s occurring in its binary representation. For example, the number 21 has Coolness 2, since its binary representation is 101012, and the string "101" occurs twice in this representation.

A number is defined as Very Cool if its Coolness is greater than or equal to K. Please, output the number of Very Cool integers between 1 and R.


HackerEarth Very Cool Numbers problem solution


HackerEarth Very Cool Numbers problem solution.

#include <bits/stdc++.h>
using namespace std;
int counter[100005]; 
int main()
{
  for (int g=1; g<=100000; g++)
  {
    for (int y=0; y<20; y++)
    {
      if (((1<<y)&g) && (!((1<<(y+1))&g)) && ((1<<(y+2))&g))counter[g]++; 
    }
  }
  int T; scanf("%d", &T); 
  for (int g=0; g<T; g++)
  {
    int R,K;scanf("%d %d", &R, &K); 
    int ans=0; 
    for (int y=1; y<=R; y++)
    {
      ans+=(counter[y]>=K);
    }
    printf("%d\n", ans); 
  }
  return 0; 
}


Second solution

#include <cstdio>
#include <iostream>
#include <cassert>

using namespace std;

#define MAXN 100000

int ar[MAXN+1];

int val(int i){
  int state=0;
  int ans=0;
  while(i){
    if(i&1){
      if(state==1)
        state = 1;
      else if(state==2)
        state = 3;
      else if(state==0)
        state = 1;
    }else{
      if(state==1)
        state = 2;
      else
        state = 0;
    }
    if(state==3){
      ans++;
      state=1;
    }
    i = i/2;
  }
  return ans;
}

void init(){
  for(int  i=1;i<=MAXN;i++){
    ar[i] = val(i);
  }
}

int main(){
  int T, R, K;
  init();
  cin >> T;
  assert(T>0 and T<=100);
  while(T--){
    cin >> R >> K;
    assert(R>0 and R<=100000);
    assert(K>0 and K<=100);
    int ans = 0;
    for(int i=1;i<=R;i++)
      if (ar[i]>=K)
        ans++;
    cout << ans << endl;
  }
}