Algorithm question

Algorithm question
0

#1

Hi,

So I was presented with this question in a test. I don’t fully grasp the meaning of it. Could someone please explain this to me? Here is the question

Create an algorithm that find the smallest coefficient of 7 where the remainder of its division to 2, 3, 4, 5, and 6 is 1.

Hint: when you divide this number to 2, 3, 4, 5, 6 respectively the remainder of it should be 1.

And the answer I gave

  1. Create four variables input, newInput, number and count =2

  2. newInput += input

  3. number = newInput

  4. If number % count = 1. Then add one to count and continue. If not then reset count=2 .go back to 2 and loop.

  5. If (count+1) = number. Print number. If not go back to 4

Thanks for helping.


#2

What is “a coefficient of 7”? That statement has real mathematical terms, but they are misapplied.

Do you mean multiple?


#3

Yeah that is why I couldn’t understand it. English is not the teachers first language so I think that is why it is worded that way.

What is meant by the question is -

What is the lowest number that can be divided by the all numbers from 2-6 inclusive with the remainder 1

Eg n%2 ==1

The answer is 301


#4

That is a confusing question. I’m not sure that I understand the question even after you explained it. Was 301 the answer given by the teacher?

I’m thinking the lowest number divisible by all in that range with remainder 1 would be 61.

Not sure about the phrase coefficient of 7. If that means multiple of 7 then I’m thinking 91.


#5

They may mean “coefficient” as in “that by which you multiply 7 to get the number”. So, if 28 is the multiple, 4 is the coefficient.


#6

The brute force method would be to start checking numbers. A step up would be checking multiples of 7. Of course, since the number is 1 less than a number divisible by 2, we know it is odd. So I might start with 7 and then add 14 to it on every iteration and check 3, 4, 5, 6.

Another option would be to check the multiples of the LCM or 2, 3, 4, 5, 6 (really 4, 5, and 6 since they contain the other two) and see if one less than it is divisible by 7 - that might be faster.


#7

Going through the math pretty quickly, I think the lowest multiple of 7 that has a remainder of 1 for each of those is 201, making the coefficient 43 - if I’m understanding it. But that’s the easy part. The tricky part is developing the algorithm.


#8

This is the algorithm I used that comes to 301


function coefficient(){
  let number =7;
for(i=2;i<7;i++){
  if(number%i == 1){
    console.log(i)
  }else{
    i=2;
    number +=7
    console.log(i)
  }
    
  
} 
  console.log('this is '+number)
}  
coefficient()

#9

Now that I rethought that I’m getting 301 as you said. I spoke too soon. Cool algorithm problem. What class are you taking?


#10

I still think approaching it backwards would be faster - iterate by 60 and check if one more than that is divisible by 7. Fewer iterations and one remainder check instead of five. This first (most obvious) solution does 8.6 times as many iterations and 5 times as many remainder checks.

Part of what you’re trying to learn here isn’t just “what’s the easiest way to do this”, but “what’s the smartest way to do this”. It doesn’t matter here, but imagine a program that had to do this calculation a million times. Or more.

Having been through a lot of interviews and now that I’ve been hired, having listened to interviews from the other side (and the interviewers’ discussions afterwards) - that is a big part of what they are looking for. My advice is:

First ask questions to clarify anything that isn’t clear. They often leave things vague to see if you’re going to make unwarranted assumptions and put on blinders. (This can cause big problems in a real dev job.) Then talk through a simple solution. And keep talking and see if you can come up with a better solution or ways to optimize the one you have.


#11

So is this what you did?
LCM of 2to6 is 60
LCM+1 would give remainder 1 for each in 2to6
keep adding 60 more to LCM+1 until you find a multiple of 7


#12

Yes, that would be faster. 8.6 fewer iterations, and an average of 2.5X fewer remainder checks (which if I remember correctly is a relatively costly operation) meaning that it will be more than 20X faster. There may even be a sexier way to do it, but that’s what comes to mind,

The more of these you do, the easier it gets to sense them. I think the question deliberately asks you about the 7 first to set you down the wrong path, to see 8f you can consider other possibilities.


#13

Thanks to both you @kevinSmith and @abellinii for sharing.
Good stuff!


#14

If any of you return to this it may help to read about the chinese remainder theorem

I couldn’t remember what to do if the moduli aren’t coprime, so I googled it and it lead to this SO question which looks at this exact question presented here


#15

It’s part of the question, the question of “what is the LCM of 2, 3, 4, 5, 6”. Of course we can just look at it and know, but if it were a more complex number set, the CRT would come in handy.

Edit: Oops, maybe I spoke too soon. It looks like there is more to the CRT than is alluded to in the SE post. I’ll have to look into it more deeply,


#16

Thanks for the all the good information guys. Although the question is not directly related to freecodecamp, I think this is really good information for fellow campers that are relatively new to the concept of using algorithms in coding. Thanks for pointing out that although my answer works it’s best to cut the iterations down and make the algorithm as efficient as possible. I’ll take a look at the CRT and see if I can understand it.


#17

It may not be specific to FCC, but it is an important subject and complements well FCC’s mission. I think it’s a good thing to talk about.


#18

Since I’m new for Programming. I’m still a beginner… I tried in a long way…

 {
            int num;

            for (int i = 1; ; i++)
            {
                num = 7 * i;

                if (num % 2 == 1)
                {
                    if(num % 3 == 1)
                    {
                        if(num % 4 == 1)
                        {
                            if(num%5 == 1)
                            {
                                if(num%6  == 1)
                                {
                                    Console.WriteLine(num);
                                    break;
                                }
                            }
                        }
                    }
                }

            }

        }

And the Answer is


301


#19

Thats good! You are well on your way to be a great coder.

Just FYI This is the answer my teacher gave me


while (int% 2 !==1 ||int%3 !==1 ||int%4 !==1 ||int%5!==1 ||int%6 !==1 ) {
  int +=7
}
console.log(int)

#20

Thanks for Sharing…!! Its add more simple tricky ways to solve many future problems…! :slight_smile: