Lucky Numbers

PHOTO EMBED

Sun Feb 06 2022 23:08:00 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #recursion #luckynumbers

class Solution
{
    public static boolean check(int n,int counter)
    {
        if(counter<=n){
            if(n%counter==0)
                return false;
		    // calculate next position of input number
		    n=n-n/counter;
		    counter++;
		    // make recursive call with updated counter 
		    // and position return check(n, counter);
		    return check(n, counter);
        }    
       	else
       		return true;
    }
    
    // n: Input n
    // Return True if the given number is a lucky number else return False
    public static boolean isLucky(int n)
    {
        return check(n,2);
    }
}
content_copyCOPY

Lucky Numbers Lucky numbers are subset of integers. Rather than going into much theory, let us see the process of arriving at lucky numbers, Take the set of integers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,…… First, delete every second number, we get following reduced set. 1, 3, 5, 7, 9, 11, 13, 15, 17, 19,………… Now, delete every third number, we get 1, 3, 7, 9, 13, 15, 19,….…. Continue this process indefinitely…… Any number that does NOT get deleted due to above process is called “lucky”. Example 1: Input: N = 5 Output: 0 Explanation: 5 is not a lucky number as it gets deleted in the second iteration. Example 2: Input: N = 19 Output: 1 Explanation: 19 is a lucky number Your Task: You don't need to read input or print anything. You only need to complete the function isLucky() that takes N as parameter and returns either False if the N is not lucky else True. Expected Time Complexity: O(sqrt(N)). Expected Auxiliary Space: O(sqrt(N)). Constraints: 1 <= N <= 10^5

https://practice.geeksforgeeks.org/problems/lucky-numbers2911/1/?track=DSASP-Recursion&batchId=190