problem no 50:josephus problem:(recursion problem).

-

 QUESTION:

Josephus problem
Easy Accuracy: 52.47% Submissions: 34010 Points: 2

Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle in a fixed direction.

The task is to choose the safe place in the circle so that when you perform these operations starting from 1st place in the circle, you are the last one remaining and survive.

Example 1:

Input:
n = 3 k = 2
Output: 3
Explanation: There are 3 persons so 
skipping 1 person i.e 1st person 2nd 
person will be killed. Thus the safe 
position is 3.

 

Example 2:

Input:
n = 5 k = 3
Output: 4
Explanation: There are 5 persons so 
skipping 2 person i.e 3rd person will 
be killed. Thus the safe position is 4. 
 
ANSWER: 

int josephus(int n, int k)
    {
       if (n == 1)
        return 1;
    else
       
        return (josephus(n - 1, k) + k-1) % n + 1;
    }

Comments

Post a Comment

Popular posts from this blog

problem 3: given two integers N and M. The problem is to find the number closest to N and divisible by M. If there are more than one such number, then output the one having maximum absolute value.

-
  Closest Number Given non-zero two integers N and M . The problem is to find the number closest to N and divisible by M . If there are more than one such number, then output the one having maximum absolute value .   Example 1: Input: N = 13 , M = 4 Output: 12 Explanation: 12 is the Closest Number to 13 which is divisible by 4. Example 2: Input: N = -15 , M = 6 Output: -18 Explanation: -12 and -18 are both similarly close to -15 and divisible by 6. but -18 has the maximum absolute value. So, Output is -18   ANSWER:   int closestNumber(int n , int m) { int q = n / ...
Read more

problem no 7:Given two numbers A and B, find Kth digit from right of AB.

-
 QUESTION: Given two numbers A and B , find K th digit from right of A B .   Example 1: Input: A = 3 B = 3 K = 1 Output: 7 Explanation: 3 3 = 27 and 1st digit from right is 7 Example 2: Input: A = 5 B = 2 K = 2 Output: 2 Explanation: 5 2 = 25 and second digit from right is 2. ANSWER: int kthDigit(int A,int B,int K){      long long int num=pow(A,B);      int count=0;      int rem;      while(num>0)      {                    rem=num%10;                    num=num/10;          count=count+1;          if(count!=K)          {         ...
Read more

Problem no 16: count the number of squares below N.

-
QUESTION: Consider a sample space S consisting of all perfect squares starting from 1, 4, 9 and so on. You are given a number N , you have to output the number of integers less than N in the sample space S. Example 1: Input : N = 9 Output: 2 Explanation: 1 and 4 are the only Perfect Squares less than 9. So, the Output is 2. Example 2: Input : N = 3 Output: 1 Explanation: 1 is the only Perfect Square less than 3. So, the Output is 1.   ANSWER:   int countSquares(int N) { int c=0; for(int i=1;i*i<N;i++) { c=c+1; } return c; }
Read more