0
$\begingroup$

I want to know if for any base the most significant digit is 1 or not. Here is the code:

for(int i=3;i<=a;i++)
  {
    int x = i;
    int r = a;
    while(r/x)
    {
      r = r/x;
    }
    int rem = r%x;
    if(r==1)
    {
      count++;
    }
  }

is there any optimal way to replace the while loop nested in the for loop.

$\endgroup$
4
  • $\begingroup$ I want to know if for any base the most significant digit is 1 or not it is, for more than half of your values for i (a/2 < i ≤ a). You might put your goal near the top of the post and have the title reflect it. $\endgroup$
    – greybeard
    Dec 6 '16 at 12:21
  • 2
    $\begingroup$ What is your code trying to accomplish? It appears to be counting something. Also, you should probably replace your code with pseudocode. $\endgroup$ Dec 6 '16 at 12:36
  • 2
    $\begingroup$ Sorry, but optimizing your code is off-topic here. $\endgroup$ Dec 6 '16 at 20:00
  • $\begingroup$ @DavidRicherby It's about getting an algorithm with better running time. $\endgroup$ Dec 6 '16 at 22:16
2
$\begingroup$

You would pick some number a, run the code, and see if you can find a pattern. There will be an obvious pattern. Then you think how you can use that pattern to find long ranges of numbers i where r ends up being 1, and long ranges where r does not end up being 1.

When you've done that, all you do is add up the number of values in those ranges of values i that end up being 1.

The best way unless you are a super genius (in which case you wouldn't be asking here) is to play around with the code, figure out its behaviour, and think about ways to take shortcuts.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.