SHKNUM - Editorial

editorial
, , , , , ,
1

Problem Link

Practice

Contest

Author: Jitender Sheora

Tester: Mark Mikhno

Editorialist: Bhuvnesh Jain

Difficulty

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.

2

Video solution with explanation (C++, Java, Python): https://youtu.be/yMxoRT381yQ

1 Like
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

4 Likes
4

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.

5

whats wrong with my code CodeChef: Practical coding for everyone
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

6

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<Long> 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<Long> findSetof2SetBits() {
    long num = 0;
    TreeSet<Long> setOf2SetBits = new TreeSet<Long>();
    

    // 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??

7

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.

8

https://www.codechef.com/viewsolution/19638812

Different approach…

9

My solution is not working for the last test case, kindly check it at CodeChef: Practical coding for everyone

10

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.

11

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 :slight_smile:
check it out :
https://www.codechef.com/viewsolution/19619650

12

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 :slight_smile:
check it out :
https://www.codechef.com/viewsolution/19619650

13

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 :slight_smile:
check it out :
https://www.codechef.com/viewsolution/19619650

14

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 :slight_smile:
check it out :
https://www.codechef.com/viewsolution/19619650

15

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 :slight_smile:
check it out :
https://www.codechef.com/viewsolution/19619650

16

#include
#include <math.h>
#include
#include <bits/stdc++.h>
#include
using namespace std;

int main()
{
vector 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 ::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?

17

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"; 
    
}

}

18

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.

19

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.

20

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.