algorithm - Mathematical and Coding logic to be used for reaching a target number from 0 -


so here's stuck with:

problem: find minimum number of steps required reach target number x 0 (zero), using 2 operations: +1 (add 1 number) or *2 (multiply 2 number).

here's thought/found out:

method 1: suppose number 29, start adding 1 0 (current_ans: 1), keep multiplying 2 current_ans till reach closest value 29, in case becomes 16 (operations: +1 *2 *2 *2 *2). keep adding 1 required number (operations: +1 *2 *2 *2 *2 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1). but, method not give efficient solution total number of steps 18, whereas can done in 8 steps using 2nd method (mentioned below).

here's code snippet same:

int count = 0, current_ans = 0, old_value, x = 29; //x number reach while(current_ans != x) {     old_value = current_ans;     if(current_ans == 0)     {         current_ans++;         count++;     }     if(current_ans < x)     {         current_ans *= 2;         count++;         continue;     }     if(current_ans > x)     {         current_ans = old_value;         count += x - current_ans;         current_ans = x;     } }

method 2: let take same number 29 , convert binary, 11101. starting 0, take first step +1 (current_ans: 1). next, multiply 2 , convert binary (current_ans: 10). similarly, other operations include +1 (current_ans: 1) *2 (current_ans: 10) +1 (current_ans: 11) *2 (current_ans: 110) +1 (current_ans: 111) *2 (current_ans: 1110) *2 (current_ans: 11100) +1 (current_ans: 11101) , required answer in 8 steps, right answer.

here's code snippet same:

int count = 0, current_ans = 0, old_value, x = 29; //x number reach while(current_ans != x) {     old_value = current_ans;     if(current_ans == 0)     {         current_ans++;         count++;     }     if(current_ans < x) //i not sure of condition     {         current_ans = current_ans << 1;         count++;         continue;     } }

so, don't know how convert logic working code in c/c++/java/python. if has better solution or code snippet towards solving same helpful. checked out other related questions too, didn't me query. method 2, know can use left shift operation, how use if there's no other better solution?

thanks in advance :)

edit: added code snippets :)

the best way work backwards. start number need:

  1. subtract 1 if number odd.

  2. divide 2 if number if even.

  3. stop when zero.

for example, 29, 28, 14, 7, 6, 3, 2, 1, 0.

c code, intentionally undocumented:

int main() {     int steps = 0;     int x = 29;     (; x; x = x % 2 ? x - 1 : x / 2, ++steps);     return steps; }

Comments

Post a Comment

Popular posts from this blog

Sort a complex associative array in PHP -

this question has answer here: php sort array subarray value 5 answers i have associative array in php like: $newarray1 = array ( [producta] => array ( [link] => http://sanjosespartan.com/blog/products/agile-java-development/ [visitcount] => 4 ) [productd] => array ( [link] => http://sanjosespartan.com/blog/products/intro-to-go/ [visitcount] => 1 ) [productg] => array ( [link] => http://sanjosespartan.com/blog/products/node-js-for-developers/ [visitcount] => 1 ) [productb] => array ( [link] => http://sanjosespartan.com/blog/products/beginning-mysql/ [visitcount] => 1 ) [productc] => array ( [link] => http://sanjosespartan.com/blog/products/computer-networks/ [visitcount] => 1 ) ...
Read more

vb.net - How to ignore if a cell is empty nothing -

how use roscolor() ignore value (like empty cell) ? color row if value upper 5 when there nothing in cell, want ignore roscolor() apply, how? public sub roscolor() integer = 0 quotedatagridview1.rows.count() - 1 step +1 dim val integer val = quotedatagridview1.rows(i).cells(3).value if val = vbempty quotedatagridview1.rows(i).defaultcellstyle.backcolor = color.white elseif val < 5 quotedatagridview1.rows(i).defaultcellstyle.backcolor = color.red elseif val > 5 , val < 10 quotedatagridview1.rows(i).defaultcellstyle.backcolor = color.lightyellow end if next end sub you can check empty value following public sub roscolor() integer = 0 quotedatagridview1.rows.count() - 1 step +1 dim val = quotedatagridview1.rows(i).cells(3).value if isdbnull(val) or val nothing quotedatagridview1.rows(i).defaultcellstyle.backcolor = color.white ...
Read more

recursion - Can every recursive algorithm be improved with dynamic programming? -

i first year undergraduate csc student looking competitive programming. recursion involves defining , solving sub problems. understand, top down dynamic programming (dp) involves memoizing solutions sub problems reduce time complexity of algorithm. can top down dp used improve efficiency of every recursive algorithm overlapping sub problems? dp fail work , how can identify this? the short answer is: yes. however, there constraints. obvious 1 recursive calls must overlap. i.e. during execution of algorithm, recursive function must called multiple times same parameters. lets truncate recursion tree memoization. can use memoization reduce number of calls. however, reduction of calls comes price. need store results somewhere. next obvious constraint need have enough memory. comes not-so obvious constraint. memory access requires time. first need find result stored , maybe copy location. in cases, might faster let recursion calculate result instead of loading somewher...
Read more