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

×

SHKNUM - Editorial

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.

asked 13 Aug '18, 15:00

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 13 Aug '18, 22:53

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 14 Aug '18, 05:38

david_s's gravatar image

4★david_s
1111
accept rate: 10%

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

link

answered 13 Aug '18, 15:22

code_report's gravatar image

3★code_report
3405
accept rate: 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.$

link

answered 14 Aug '18, 06:28

joffan's gravatar image

5★joffan
9488
accept rate: 13%

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

link

answered 14 Aug '18, 08:58

ayush4's gravatar image

3★ayush4
163
accept rate: 10%

edited 14 Aug '18, 09:04

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

link

answered 14 Aug '18, 09:02

pawan_94's gravatar image

2★pawan_94
1
accept rate: 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.

link

answered 14 Aug '18, 11:18

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

link

answered 14 Aug '18, 14:14

gryphon's gravatar image

3★gryphon
112
accept rate: 0%

My solution is not working for the last test case, kindly check it at https://www.codechef.com/viewsolution/19552013

link

answered 14 Aug '18, 15:44

ishan99's gravatar image

2★ishan99
11
accept rate: 0%

edited 14 Aug '18, 15:45

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.

link

answered 14 Aug '18, 18:05

atiaditya369's gravatar image

3★atiaditya369
1
accept rate: 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

hyperion101010's gravatar image

2★hyperion101010
1
accept rate: 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

hyperion101010's gravatar image

2★hyperion101010
1
accept rate: 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

hyperion101010's gravatar image

2★hyperion101010
1
accept rate: 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

hyperion101010's gravatar image

2★hyperion101010
1
accept rate: 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

hyperion101010's gravatar image

2★hyperion101010
1
accept rate: 0%

include <iostream>

include <math.h>

include <vector>

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

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?

link
This answer is marked "community wiki".

answered 18 Aug '18, 09:00

gagan_1197's gravatar image

2★gagan_1197
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";

}

}

link

answered 18 Aug '18, 13:11

kakashileaf's gravatar image

1★kakashileaf
1
accept rate: 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

answered 17 Oct '18, 16:31

guptasaanika's gravatar image

3★guptasaanika
1
accept rate: 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

guptasaanika's gravatar image

3★guptasaanika
1
accept rate: 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

guptasaanika's gravatar image

3★guptasaanika
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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