Lucky Number Program In Java

In this problem section, we are going to create the lucky number program in Java. We are going to see 2 different approaches to find the first N lucky numbers. Additionally, we will also create a program that tells us if a number is lucky or not.

Table Of Contents

1. Introduction To Lucky Number
2. Find All Lucky Numbers Before Given number
   1. Method 1
   2. Method 2
3. Program To Check If Number Is Lucky Or Not
4. Conclusion

Introduction To Lucky Number

Lucky numbers are a sequence of natural numbers that we get when we remove every second digit, then every third digit, then every fourth digit, and so on, from the natural number sequence. The numbers that are left from the sequence are known as lucky numbers.

Consider the following sequence of natural numbers:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

First, remove every second digit. The remaining numbers are:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, ...

Then remove every third digit. The remaining numbers are:

1, 3, 7, 9, 13, 15, 19, ...

Then remove every fourth digit. The remaining numbers are:

1, 3, 7, 13, 15, 19, ...

Then remove every fifth digit. The remaining numbers are:

1, 3, 7, 13, 19, ...

The above process is repeated for every digit. The remaining numbers are the lucky numbers.

Find All Lucky Numbers Before Given number

Now as we know what lucky numbers are, we have also seen lucky numbers before 20 which are 1, 3, 7, 13, 19.

Let's now create a program in Java that will find all lucky numbers before a given number.

We are going to create a program for this using 2 different approaches. Let's begin.

Method 1: Lucky Number Program In Java

In this first approach, we will create an array of size N and fill it with natural numbers from 1 to N.

Then as the program progresses we will change the value of every 2nd element to 0. Then in the next operation, we will change the value of every 3rd element that is not 0 to 0. Then in the next operation, we will change the value of every 4th element that is not 0 to 0. And so on.

Here is the complete program using this approach:

import java.util.Scanner;

public class luckyNumbers {
  public static void main(String[] args) {
    // take number input
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter number: ");
    int num = sc.nextInt();
    // initiate array
    int arr[] = new int[num];
    for(int i = 0; i < num; i++) {
      arr[i] = i+1;
    }

    // find lucky number
    for (int step = 2; step < num/2; step++) {
      int count = 0;
      for (int i = 0; i < num; i++) {
        // the variable 'count' increase only when the element is not 0
        // this way we can get coorect non-zero elements
        if (arr[i] != 0) {
          count++;
        }
        // using count to get the correct element
        // and change it to 0
        if (count % step == 0) {
          arr[i] = 0;
        }
      }
    }
    // print array
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] != 0) {
        System.out.print(arr[i] + " ");
      }
    }
    System.out.println();
    // close scanner
    sc.close();
  }
}

Output:

$ java luckyNumbers
Enter number: 20
1 3 7 9 13 15 19
Enter number: 50
1 3 7 13 19 27 39 49
Enter number: 100
1 3 7 13 19 27 39 49 63 79 91

Code Explanation:

Method 2: Lucky Number Program In Java

In previous approach we replaced the numbers with 0. But in this approach we will shift the numbers to left.

First we will shift the number to left starting from 2n position, then again starting from 3n position, and so on.

Here is the complete program using this approach:

import java.util.Scanner;

class luckyNumbers {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();

    // initiate array
    int arr[] = new int[num];
    for (int i = 0; i < num; i++) {
      arr[i] = i + 1;
    }

    // find lucky number
    int step = 1;
    while (step < num) {
      for (int i = step; i < num; i += step) {
        for (int j = i; j < num - 1; j++) {
          arr[j] = arr[j + 1];
        }
        num--;
      }
      step++;
    }

    // print array
    for (int i = 0; i < num; i++) {
      System.out.print(arr[i] + "   ");
    }
    System.out.println();
    // close scanner
    sc.close();
  }
}

Output:

$ java luckyNumbers
Enter number: 10
1 3 7
Enter number: 100
1 3 7 13 19 27 39 49 63 79 91

Program to Check if Number is Lucky or Not

Finding a Lucky number is quite easy but telling whether a number is a Lucky number or not is a bit tricky.

What approach will you use to tell whether a number is a lucky number or not?🤔

Take your time⏳ and think about it.

Let the number to check be 9. Consider the following series: 1, 2, 3, 4, 5, 6, 7, 8, 9. Position of 9 is 9th in the series.

After the first step, that is removal of every 2nd element, we get 1, 3, 5, 7, 9. So the position of 9 is 5th which is 9 - floor(9/2) = previous_position - floor(previous_position/2).

Again after the next step, that is removal of every 3rd element, we get 1, 3, 7, 9. So the position of 9 is 4th which is 5 - floor(5/3) = previous_position - floor(previous_position/3).

So the position of the number can be tracked using this formula: previous_position - floor(previous_position/step).

Also if the current position becomes equal to the step the number will be removed from the series. Making the number a non-lucky number.

Using these facts here is the program to find if a number is lucky or not:

import java.util.Scanner;

public class isLuckyNumber {
  static int step = 2;

  static boolean isLucky(int num) {
    int position = num;
    // if the position of the number falls at the step
    // then it will be removed from series
    if (position % step == 0)
      return false;
    // if step becomes greater than position
    // then it's definitely a lucky number
    if (step > position)
      return true;
    
    position = position - position / step;
    step++;
    return isLucky(position);
  }

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter number: ");
    int num = sc.nextInt();

    boolean lucky = isLucky(num);
    if (lucky) {
      System.out.println(num + " is a lucky number.");
    } else {
      System.out.println(num + " is  not a lucky number.");
    }
    // close scanner
    sc.close();
  }
}

Output:

$ java isLuckyNumber
Enter number: 9
9 is a lucky number.
Enter number: 10
10 is not a lucky number.