TIFR CSE 2020 | Part B | Question: 12

Question

Given the pseudocode below for the function $\textbf{remains()}$, which of the following statements is true about the output, if we pass it a positive integer $n>2$?

int remains(int n)
{  
     int x = n;
     for (i=(n-1);i>1;i--)  {
        x = x % i ;
   }
     return x;
}

• A. Output is always $0$
• B. Output is always $1$
• C. Output is $0$ only if $n$ is NOT a prime number
• D. Output is $1$ only if $n$ is a prime number
• E. None of the above

Answer 1

BASIC point :-

1%1 = 0

1% x = 1, for x > 1

x+1%x = 1, for all x.

 

for(i=(n-1);i>1;i--)
    x=x%i;

when i=(n-1) ===> x will updated to 1 due to x%i returns 1

after that it never changed.

if i=1, then x will updated to 0 but when i=1, condition evaluates to false, So x can't updated one more time.

Answer 2

loop continues from n-1  down to 2.
in first iteration
x%i become n%(n-1).
and  which results in  1 for any value of n>=2
and after first iteration x will become 1 and then x%i will always results 1  ( for i>1)