You are not logged in. Please login at www.codechef.com to post your questions!

×

# SHKNUM - Editorial

Practice

Contest

Author: Jitender Sheora

Tester: Mark Mikhno

Editorialist: Bhuvnesh Jain

SIMPLE

# Prerequisites

Pre-computation, Binary-search

# Problem

You are given a number $N$ and you can apply 2 type of operations:

1. Add 1 to the number.
2. Subtract 1 from the number.

Find the minimum number of operations to be carried such that the resulting number can be represented as $2^x + 2^y$, where $x$ and $y$ are non-negative and $x != y$.

# Explanation

The first thing to note is the optimal answer requires us to apply the only operation of either type. Since the operations negate the effect of each other, we should either only add or subtract from our initial number $N$.

Suppose, if we have a sorted list of all possible final numbers which can be represented in the form, $2^x + 2^y$, then we can simply find the number nearest to $N$. For the smaller number, we can simply apply subtraction operation and for the greater number, we can simply apply the addition operation.

For finding the nearest number greater than or smaller than a given number, we can simply binary search. If you are not familiar with this, you can read topcoder tutorial. There are also inbuilt-functions like "lower_bound" and "upper_bound" in C++ which do your job. (But remember your list should be sorted.)

We can now pre-computate all possible numbers which can be represented in the form $2^x + 2^y$. Below is a pseudo-code for it:


vals = []
for i in [0, 30]:
for j in [i+1, 30]:
x = (1 << i) + (1 << j)
vals.append(x)



Note that the maximum possible exponent of $2$ in answer can be $ceil(\log{{10}^9}) = 30$. This is because, for the minimum operation, we need to find the nearest possible number closest to $N$.

The size of $vals$ will be $(31 * 30) / 2) = 465$. Since the size is not large, even iterating through all numbers, instead of applying binary search will pass for the full solution.

Once, you are clear with the above idea, you can see the author or editorialist implementation below for help.

Feel free to share your approach, if it was somewhat different.

# Time Complexity

$O({\log}^2{N})$ for pre-computation.

$O({\log{|vals|}})$ per test case.

# Space Complexity

$O({\log}^2{N})$

# SOLUTIONS:

Author's solution can be found here.

Tester's solution can be found here.

Editorialist's solution can be found here.

asked 13 Aug '18, 15:00 6★likecs
3.7k2481
accept rate: 9% 19.8k350498541

 3 My approach was to search directly. First 'decode' the number, counting the number of binary ones, and finding the zero-based position of the first and second binary digits. For a number with more than 2 binary digits, there are two possibilities. For a number 'n' (a) Subtract to remove digits less significant than the first two  int mask = (1 << index_second) - 1; output = n & mask;  (b) Add to leave only 2 binary digits  int shift = 1 << (index_second + 1); int mask = shift - 1; output = shift - ( n & mask_b ); if (index_first == index_second + 1) ++output;  Choose whichever is the less. You can see the solution at https://www.codechef.com/viewsolution/19485795 answered 14 Aug '18, 05:38 4★david_s 111●1 accept rate: 10%
 0 Video solution with explanation (C++, Java, Python): https://youtu.be/yMxoRT381yQ answered 13 Aug '18, 15:22 340●5 accept rate: 0%
 0 First, for numbers $4$ or less, find the difference to $3$, the smallest qualifying value. Then starting with $8$, I doubled up to find the smallest power of $2$ not less than $n$, then stepped back down by smaller powers of $2$ until I had $n$ bracketed. so for example for $n=39$ the trail would go $8\to 16\to 32\to 64\to 48\to 40\to 36,$ with the result following from $\min(40-39, 39-36) =1.$ At the turn point the top of the bracket is held (if needed) as $65=64+1.$ answered 14 Aug '18, 06:28 5★joffan 948●8 accept rate: 13%
 0 whats wrong with my code https://www.codechef.com/viewsolution/19615761 My approach was close to the one explained above. Fist I checked if the number is 1 or equal to square's then we can get the number of steps directly. if don't then I subtract the given number with square number in list bigger than it, keep the difference in d. then checking the closet square to d is the number of steps required If u can please run it and find any test case that it fails, plz comment it answered 14 Aug '18, 08:58 3★ayush4 16●3 accept rate: 10%
 0 public static void main(String args[]) throws Exception { in = new InputReader(System.in); out = new PrintWriter(System.out); int testCases = in.nextInt(); long number, ceiling = 0, floor = 0; TreeSet setOf2SetBits = findSetof2SetBits(); while(testCases-- > 0) { ceiling = 0; floor = 0; number = in.nextLong(); try { ceiling = setOf2SetBits.ceiling(number); } catch(NullPointerException n) { ceiling = -1; } try { floor = setOf2SetBits.floor(number); }catch(NullPointerException n) { floor = -1; } if(ceiling==-1 || floor==-1) { out.println(Math.abs(number-Math.abs(Math.max(ceiling, floor)))); } else { out.println(Math.min(ceiling-number, number-floor)); } } out.close(); } static TreeSet findSetof2SetBits() { long num = 0; TreeSet setOf2SetBits = new TreeSet(); // Find numbers whose 2 bits are set for (int i = 0; i<=30 ; i++) { for (int j = i+1; j <= 30; j++) { num = (1 << i) + (1 << j); setOf2SetBits.add(num); } } return setOf2SetBits; }  the above solution is failing in last test case.Can anyone suggest where I am doing wrong?? answered 14 Aug '18, 09:02 2★pawan_94 1 accept rate: 0%
 0 If the binary representation of $N$ has only one set bit then the answer is $1$, unless $N = 1$, in which case the answer is $2$. Let 2 or more bits are set in the binary representation of $N$. Find the two numbers $l$ and $h$ such that $l$ is the largest number represented as $2^x+2^y$ that is not greater than $N$, and $h$ is the smallest number represented as $2^x+2^y$ that is greater than $N$. Let $b_1$ be the number corresponding to the highest set bit in the binary representation of $N$, and $b_2$ - to the second highest. Then $l=b_1 + b_2$ and $h=b_1+2b_2$ if $b_1>2b_2$, otherwise $h=b_1+2b_2+1$. The answer is the smallest of the distances from $N$ to $l$ and $h$. Solution in Python. answered 14 Aug '18, 11:18 3★eugalt 282●7 accept rate: 4%
 0 https://www.codechef.com/viewsolution/19638812 Different approach... answered 14 Aug '18, 14:14 3★gryphon 11●2 accept rate: 0%
 0 My solution is not working for the last test case, kindly check it at https://www.codechef.com/viewsolution/19552013 answered 14 Aug '18, 15:44 2★ishan99 1●1 accept rate: 0%
 0 I found out the highest value of 2^x which is less than or equal to the given number and iterated y from 0 to x-1 adding both the values of 2^x and 2^y.If the sum is less than or equal to the given number I am updating the value of temp and if the sum is greater than or equals to the given number I am assigning the value to temp1 and breaking the loop.If sum never equals or exceeds the number temp1 is assigned with (2^(x+1))+1 which has 2 set bits(in the form of (2^x+2^y)). The minimum of the absolute difference between temp and temp1 is the answer.I can't figure out what could probably go wrong in this.So if you could please test it and correct my code I would be thankful.This is the link to my solution link text. Kindly check it. answered 14 Aug '18, 18:05 1 accept rate: 0%
 0 My approach was using log function , then by approximating the nearest value of the given number by taking log and then applying ceil and floor of the given value there must be either one power of 2 solving the given problem , thus by clever approximations to power of 2 i got AC :) check it out : https://www.codechef.com/viewsolution/19619650 link This answer is marked "community wiki". answered 14 Aug '18, 22:25 1 accept rate: 0%
 0 My approach was using log function , then by approximating the nearest value of the given number by taking log and then applying ciel and floor of the given value there must be either one power of 2 solving the given problem , thus by clever approximations to power of 2 i got AC :) check it out : https://www.codechef.com/viewsolution/19619650 link This answer is marked "community wiki". answered 14 Aug '18, 22:25 1 accept rate: 0%
 0 My approach was using log function , then by approximating the nearest value of the given number by taking log and then applying ceil and floor of the given value there must be either one power of 2 solving the given problem , thus by clever approximations to power of 2 i got AC :) check it out : https://www.codechef.com/viewsolution/19619650 link This answer is marked "community wiki". answered 14 Aug '18, 22:25 1 accept rate: 0%
 0 My approach was using log function , then by approximating the nearest value of the given number by taking log and then applying ceil and floor of the given value there must be either one power of 2 solving the given problem , thus by clever approximations to power of 2 i got AC :) check it out : https://www.codechef.com/viewsolution/19619650 link This answer is marked "community wiki". answered 14 Aug '18, 22:25 1 accept rate: 0%
 0 My approach was using log function , then by approximating the nearest value of the given number by taking log and then applying ceil and floor of the given value there must be either one power of 2 solving the given problem , thus by clever approximations to power of 2 i got AC :) check it out : https://www.codechef.com/viewsolution/19619650 link This answer is marked "community wiki". answered 14 Aug '18, 22:25 1 accept rate: 0%

# include <algorithm>

using namespace std;

int main() { vector <long long="" int=""> v1; int i,j,n1,t,flag=0; long long int n; for(i=0;i<=30;i++) { for(j=i+1;j<=30;j++) { n1=pow(2,i)+pow(2,j); v1.push_back(n1); } } sort(v1.begin(),v1.end()); vector <long long="" int=""> ::iterator lower,upper; cin>>t; while(t--) { cin>>n; for(auto itr=v1.begin();itr!=v1.end();itr++) { if(itr==n) { cout<<'0'<<endl; flag=1; break; } else if(n==1) { cout<<'2'<<endl; flag=1; break; } else if(n==2) { cout<<'1'<<endl; flag=1; break; } } if(flag==0) { for(auto itr=v1.begin();itr!=v1.end();itr++) { lower=lower_bound(v1.begin(),v1.end(),n)-1; upper=upper_bound(v1.begin(),v1.end(),n); if(n-lower<=upper-n) { cout<<n-lower<<endl; break; } else { cout<<*upper-n<<endl; break; } } } } return 0; }

plz tell me what is wrong with my code?

This answer is marked "community wiki".

answered 18 Aug '18, 09:00 32
accept rate: 0%

Please tell why my solution isn't working for all the inputs.....

# include<bits stdc++.h="">

using namespace std;

int main() { int t; cin>>t; while(t--) { long int n; cin>>n;

   long int shrt=0;
long int grtr=0;
int flag=0;

for(int i=1;;i++)
{
if(flag==1) break;
long int gr=pow(2,i);
for(int j=0;j<i;j++)
{
long int ls=pow(2,j);
if(gr+ls>n)
{
grtr=gr+ls;

if(j-1>=0)
shrt=gr+pow(2,j-1);
else shrt=grtr;

flag=1;
break;

}
else continue;
}
}
if(grtr==shrt) cout<<(grtr-n)<<"\n";
else if((grtr-n)<(n-shrt)) cout<<(grtr-n)<<"\n";
else cout<<(n-shrt)<<"\n";

}


}

answered 18 Aug '18, 13:11 1
accept rate: 0%

 0 Please check my solution. I'm getting TLE and WA. Please tell me some of the edge cases where I might get a wrong output and also how can I optimize it more. Thank you. answered 17 Oct '18, 16:31 1 accept rate: 0%
 0 Please check my solution. I'm getting TLE and WA. Please tell me some of the edge cases where I might get a wrong output and also how can I optimize it more. Thank you. link This answer is marked "community wiki". answered 17 Oct '18, 16:31 1 accept rate: 0%
 0 Please check my solution. I'm getting TLE and WA. Please tell me some of the edge cases where I might get a wrong output and also how can I optimize it more. Thank you. link This answer is marked "community wiki". answered 17 Oct '18, 16:31 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,191
×1,056
×593
×196
×145
×26

question asked: 13 Aug '18, 15:00

question was seen: 2,029 times

last updated: 17 Oct '18, 16:31