Answer to Question #216745 in Java | JSP | JSF for asd

Question

Akshita loves chocolates, numbers and algorithms. Her friends Ina and Mina gave her a and b chocolates respectively.  Given her love for numbers, she likes all the numbers that are divisible by either ‘a’ or ‘b’ or both. She wants to find the nth smallest such number that is divisible by either a or b. Suggest her an algorithm to find the desired number, describe the principle on which the algorithm is based, write the pseudocode and the recurrence relation for the same. Also state which subproblem will give the answer to the original problem.

Expected Complexity → O(log(N∗min(A,B))).  

Assume a and b to be co-prime positive integers.

Answer 1

int a=8, b=9;
int num=0;
while(true){
    if(num%a==0 or num%b==0){
        break;
    }
    num++;
}
print(num);