# PROBLEM LINK:

Practice

Contest: Division 3

Contest: Division 2

Contest: Division 1

**Author:** Soumyadeep Pal

**Tester:** Manan Grover

**Editorialist:** Vichitr Gandas

# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

Binary Search, Digit DP

# PROBLEM:

Find the minimum integer K such that sum of bits present on odd positions in binary representation of all integers from 1 to K is greater than or equal to N.

# QUICK EXPLANATION

Use digit DP to find sum of bits present on odd positions in binary presentation of all integer from 1 to K for a particular K. As the sum would only increase with increasing K hence we can binary search on K.

# EXPLANATION

Lets define a function F(K) as sum of bits present on odd positions in binary representation of all integers between 1 to K. As sum would increase if we increase K hence

F(K+1) \ge F(K)

As F is a non-decreasing function, this gives an ideal condition to binary search on K such that F(K) \ge N.

Now the task is reduced to find F(K) for a given K. This can be easily found with digit dp.

Let B be the binary representation of K and its length be len. Consider 1-based indexing in rest of the editorial.

Let dp1[pos][tight] represent the count of numbers which are \le B[pos: len].

Here B[pos: len] represents the substring of B starting from index pos upto end.

Here tight is a boolean which represents if previous bits ie from index 1 to pos-1 are chosen exactly same as they are in B.

Now first letâ€™s calculate dp1.

**Case 1: tight = 1**

This means all previous bits have been chosen as it is, hence current bit can be selected <= B[pos]. Otherwise current number would be greater than K. Hence,

- If B[pos] = 0, we can select current bit as only 0 so dp transition would be as following:

dp1[pos][tight] = dp1[pos+1][tight]. - If B[pos] = 1, we have two choices for current bit as either 0 or 1. If we choose 0, tight would become 0 as the number would no more remain same as B upto current index. And if we choose current digit as 1, tight would remain 1 only so dp transition would be as following:

dp1[pos][tight] = dp1[pos+1][0] + dp1[pos+1][1].

**Case 2: tight = 0**

If tight = 0, then we can use either 0 or 1 for current bit as the number would always be <K hence dp transition would be:

dp1[pos][tight] = dp1[pos+1][tight] + dp1[pos+1][tight].

**Calculating F(K) with DP**

Now we will use this dp to calculate F. Let dp2[pos][tight][parity] represent the sum of odd bits of numbers which started from an index with odd-even parity as parity and are \le B[pos: len].

Here B[pos: len] represents the substring of B starting from index pos upto end.

Here tight is a boolean which represents if previous bits ie from index 1 to pos-1 are chosen exactly same as they are in B.

Here if start index was odd then parity=1, if start index was even then parity=0. Initially we will say parity=2 if start index is not known.

Now lets calculate dp2. Two cases here as well:

**Case 1: tight = 1**

Here if B[pos] = 0, current bit wonâ€™t contribute anything to the sum as its 0. Sum value would be equal to the sum we get from next index. Hence dp transition can be written as following:

- dp2[pos][tight][parity] = dp2[pos+1][tight][parity]

If B[pos] = 1

- We can either select 0 for current bit
- In that case, tight would become 0 and sum would be equal to the sum we get from next index ie dp2[pos+1][0][parity].

- Or we can also choose 1 for current bit
- If parity = 2 then it would become parity = pos \% 2 as pos would be start position because of picking current bit as 1.
- Current bit would contribute only if the current pos is at odd position from start ie (pos-parity) \% 2 = 0.
- Also the contribution from current bit would be dp1[pos+1][tight]. Because the count of numbers which can be formed <=K after fixing current bit as 1 is dp1[pos+1][tight].
- Contribution from next index ie dp2[pos+1][tight][pos \% 2] would also be added as we are finding sum.

- To find the sum, we add the values we get from both choices.

Hence the dp transition can be written as following:

dp2[pos][tight][parity] = dp2[pos+1][0][parity] + dp2[pos+1][tight][pos \% 2] + ((pos-parity) \% 2 == 0) ? dp1[pos+1][tight] : 0.

**Case 2: tight = 0**

In this case, we always have 2 choices for current bit.

- If we select current bit as 0, the sum would be equal to dp2[pos+1][tight][parity].
- If we select current bit as 1
- If parity = 2 then it would become parity = pos \% 2 as pos would be start position because of picking current bit as 1.
- Current bit would contribute only if the current pos is at odd position from start ie (pos-parity) \% 2 = 0.
- Also the contribution from current bit would be dp1[pos+1][tight]. Because the count of numbers which can be formed <=K after fixing current bit as 1 is dp1[pos+1][tight].
- Contribution from next index ie dp2[pos+1][tight][pos \% 2] would also be added as we are finding sum.

- To find the sum, we add the values we get from both choices.

Hence the dp transition can be written as following:

dp2[pos][tight][parity] = dp2[pos+1][tight][parity] + dp2[pos+1][tight][pos \% 2] +((pos-parity) \% 2 == 0) ? dp1[pos+1][tight] : 0.

# TIME COMPLEXITY:

O(10 \cdot log^2n) per test case

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
#define int long long
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cerr << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sz, n;
int cache[32][2][3], ways[32][2];
int dp1(string &s, int idx = 0, int tight = 1) {
if (idx == sz) {
return ways[idx][tight] = 1;
}
int &ans = ways[idx][tight];
if (ans != -1) return ans;
ans = 0;
int last = 1;
if (tight) last = s[idx] - '0';
for (int i = 0; i <= last; ++i) {
ans += dp1(s, idx + 1, tight && (i == last));
}
// cout << idx << " " << tight << " " << ans << endl;
return ans;
}
int dp2(string &s, int idx = 0, int tight = 1, int start_bit = 2) {
if (idx == sz) {
return 0;
}
int &ans = cache[idx][tight][start_bit];
if (ans != -1) return ans;
ans = 0;
int last = 1;
if (tight) last = s[idx] - '0';
for (int i = 0; i <= last; ++i) {
if (start_bit == 2 and i == 1) start_bit = idx % 2;
int cur = 0;
if (i == 1) {
int idx_from_left = (idx - start_bit);
cur = (idx_from_left & 1 ? 0 : 1);
}
int tight1 = tight && (i == last);
ans += (cur * ways[idx + 1][tight1]) + dp2(s, idx + 1, tight1, start_bit);
}
return ans;
}
int check(int x) {
string s;
while (x > 0) {
s.push_back((char)(x % 2 + '0'));
x /= 2;
}
reverse(s.begin(), s.end());
sz = (int)(s.size());
memset(cache, -1, sizeof(cache));
memset(ways, -1, sizeof(ways));
dp1(s);
int y = dp2(s);
// cout << s << " " << y << endl;
return y;
}
int32_t main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = readIntLn(1, 1000);
while (t--) {
int n = readIntLn(1, 1000000000);
int st = 1, end = n, ans = 1e10;
while (st <= end) {
int mid = (st + end) / 2;
if (check(mid) >= n) {
ans = mid;
end = mid - 1;
} else {
st = mid + 1;
}
}
cout << ans << '\n';
}
assert(getchar()==-1);
return 0;
}
```

## Tester's Solution

```
#include <bits/stdc++.h>
using namespace std;
int n;
bool check(int x){
long long ans = 0;
int temp = 1;
int cnt = -1;
while(true){
temp *= 2;
cnt++;
int len = min(temp, x + 1) - temp / 2;
ans += len;
if(temp <= x + 1){
ans += (len / 2) * (cnt / 2);
}else{
if(cnt % 2){
temp = 4;
}else{
temp = 2;
}
cnt /= 2;
for(int i = 0; i < cnt; i++){
int y = len % temp;
ans += (len - y) / 2;
ans += max(0, y - temp / 2);
temp *= 4;
}
break;
}
}
return n <= ans;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
cin>>n;
int ans;
int l = 1, r = n;
while(l <= r){
int mid = (r + l) / 2;
if(check(mid)){
ans = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
cout<<ans<<"\n";
}
return 0;
}
```

## Editorialist's Solution

```
/*
* @author: vichitr
* @date: 25th July 2021
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);
int n, dp1[33][2], dp2[33][2][3];
string B;
int sol1(int pos, int tight) {
if (pos == B.size())
return 1;
int &ans = dp1[pos][tight];
if (ans != -1)
return ans;
ans = 0;
if (tight == 1) {
if (B[pos] == '0')
ans = sol1(pos + 1, tight);
else {
ans = sol1(pos + 1, 0) + sol1(pos + 1, 1);
}
}
else {
ans = sol1(pos + 1, tight) * 2;
}
return ans;
}
int sol2(int pos, int tight, int parity) {
if (pos == B.size())
return 0;
int &ans = dp2[pos][tight][parity];
if (ans != -1)
return ans;
ans = 0;
if (tight) {
if (B[pos] == '0')
ans = sol2(pos + 1, tight, parity);
else {
// current bit as 0
ans += sol2(pos + 1, 0, parity);
// current bit as 1
// if parity is still 2 then update it with current pos
if (parity == 2) parity = pos % 2;
// ans from next index for choice 1 for current bit
ans += sol2(pos + 1, 1, parity);
// if cur pos is odd position from start then add
// contribution of current bit
if ((pos - parity) % 2 == 0)
ans += sol1(pos + 1, tight);
}
}
else {
// current bit as 0
ans += sol2(pos + 1, tight, parity);
// current bit as 1
// if parity is still 2 then update it with current pos
if (parity == 2) parity = pos % 2;
// ans from next index for choice 1 for current bit
ans += sol2(pos + 1, tight, parity);
// if cur pos is odd position from start then add
// contribution of current bit
if ((pos - parity) % 2 == 0)
ans += sol1(pos + 1, tight);
}
return ans;
}
bool check(int x) {
memset(dp1, -1, sizeof dp1);
memset(dp2, -1, sizeof dp2);
B.clear();
while (x) {
B += (char)(x % 2 + '0');
x /= 2;
}
B += '0';
reverse(B.begin(), B.end());
return sol2(1, 1, 2) >= n;
}
void solve() {
cin >> n;
int ans = 0, s = 0, e = n;
while (s <= e) {
int m = (s + e) / 2;
if (check(m)) {
ans = m;
e = m - 1;
}
else
s = m + 1;
}
cout << ans << '\n';
}
signed main() {
fast;
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
cin >> t;
for (int tt = 1; tt <= t; tt++) {
// cout << "Case #" << tt << ": ";
solve();
}
return 0;
}
```

# VIDEO EDITORIAL:

If you have other approaches or solutions, letâ€™s discuss in comments.If you have other approaches or solutions, letâ€™s discuss in comments.