Algorithm
Problem link- https://www.spoj.com/problems/NOVICE63/
NOVICE63 - Special Numbers
Ted thinks that integers having equal number of 1's and 0's in their binary representation are special. Therefore, he wants to know how many such integers are present.
Note: For this problem, the binary representation of an integer(>0) is considered from the least significant bit to the last set bit. Which means, 5 has a binary representation of 101, 3 has a binary representation of 11 etc. As such, one example of a special number is 9 which has a binary representation, 1001.
Input
First line contains an integer T (at most 100) denoting the total number of test cases. Each test case contains a single integer N (2 <= N <= 2^60). N is always a power of 2.
Output
A single integer denoting the total number of such special numbers in the range 1 to N (inclusive).
Example
Input: 3 8 16 32 Output: 1 4 4
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
def f(n, k):
return fac[n] // fac[k] // fac[n - k]
fac = [1] * 123
for i in range(1, 123):
fac[i] = fac[i - 1] * i
T = int(input())
for _ in range(T):
N = int(input())
if N == 2:
print(1)
continue
for i in range(65):
if N & (1 << i):
N = i
break
result = 0
for j in range(1, N // 2 + 1):
result += f(j + j - 1, j)
print(result)Input
8
16
32
Output
4
4
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cassert>
#include <iostream>
using namespace std;
const int MAX = 1000005;
int phi[MAX];
int main()
{
for(int i=1; i<=MAX; i++)
phi[i]=i;
for(int i=2; i<=MAX; i++)
{ if(phi[i]==i)
{ // This condition guarantees that i is prime since it was not modified by any number <i.
for(int j=i; j<=MAX; j+=i)
phi[j]-=(phi[j]/i); // In this step we multiply (1-1/i) to each multiple of i, since it would be a prime factor in factorisation of all its multiples.
}
}
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{ int p;
cin >> p;
assert(1<=p && p<=1000000);
cout << phi[phi[p]]<<'\n';
}
}Input
8
16
32
Output
4
4
Demonstration
SPOJ Solution-Special Numbers-Solution in C, C++, Java, Python