Lucky Numbers Program in Java and Python
Lucky numbers program with algorithm, explanation, Java solution and simple Python solution for ICSE and ISC students.
Question:
Consider the sequence of natural numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 and so on.
Removing every second number produces the sequence 1, 3, 5, 7, 9 and so on. Removing every third number from the remaining sequence produces 1, 3, 7, 9 and so on. This process continues by removing every fourth, fifth and further positioned number. The numbers that remain are called Lucky Numbers.
Write a program to generate and print lucky numbers less than a given number N.
Algorithm:
Step 1: Start.
Step 2: Accept the upper limit N.
Step 3: Create an array and store natural numbers from 1 to N.
Step 4: Store size = N to represent the current number of active elements.
Step 5: Initialize step = 2, because the first removal deletes every second number.
Step 6: Repeat while step <= size.
Step 7: Starting from position step, remove every stepth active element.
Step 8: To remove an element, shift all following elements one position left and decrease size.
Step 9: After one complete deletion pass, increase step by 1.
Step 10: Display the remaining active elements after each pass if required.
Step 11: After the loop stops, print all remaining elements from index 0 to size - 1.
Step 12: Stop.
Explanation:
The program stores the current sequence in a single array. Instead of creating a new array after every pass, it removes an element by shifting the following elements one position to the left.
The variable size is important because the physical array length remains the same, but the number of useful values keeps decreasing. Only indexes from 0 to size - 1 are treated as active.
In each pass, the program removes every stepth active element. Since array indexes begin from 0, the first deleted index for step 2 is index 1, the first deleted index for step 3 is index 2, and so on.
After deleting one element, the next elements shift left. Therefore the deletion index is advanced carefully so that the next counted position is still correct in the shortened sequence.
Lucky number generation is based on repeated deletion from a list. The program starts with a sequence of natural numbers and then removes numbers according to step sizes obtained from the remaining list. After each round, the list becomes shorter, and the next step is read from the updated list rather than from the original sequence. This is why array shifting or list compaction is important. When an element is deleted, later elements must move left so that the active list remains continuous.
Java Program:
/**
* The class LuckyNumbers generates the Lucky Numbers upto a given limit
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
* @Question Year : ISC 2001
*/
import java.util.Scanner;
class LuckyNumbers
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter the Number of Elements: ");
int n = sc.nextInt();
// The original limit is stored separately because size changes later.
int limit = n;
// The array initially stores natural numbers from 1 to n.
int a[] = new int[n];
for(int i = 0; i < n; i++)
{
a[i] = i + 1;
}
/*
* size stores the number of active elements currently present.
* The physical array length remains same, but useful elements reduce.
*/
int size = n;
/*
* step = 2 means every 2nd number is removed first.
* Then every 3rd, every 4th, and so on are removed.
*/
int step = 2;
System.out.println("\nLucky Number Operation:\n");
while(step <= size)
{
/*
* Since array index starts from 0, the step-th position is step - 1.
* Example: every 2nd element starts from index 1.
*/
int pos = step - 1;
while(pos < size)
{
/*
* Remove the element at index pos by shifting every element
* after it one position towards the left.
*/
for(int j = pos; j < size - 1; j++)
{
a[j] = a[j + 1];
}
// One active element has been removed from the sequence.
size--;
/*
* Move to the next step-th position in the shortened array.
* We add step - 1 because the current deletion already shifted
* the next element into the current index.
*/
pos = pos + step - 1;
}
// Display the sequence left after this deletion pass.
for(int i = 0; i < size; i++)
{
System.out.print(a[i] + " ");
}
System.out.println();
step++;
}
System.out.print("\nHence, the Lucky Numbers Less than " + limit + " are: ");
for(int i = 0; i < size; i++)
{
System.out.print(a[i] + " ");
}
}
}Equivalent Python Program:
n = int(input("Enter the Number of Elements: "))
# The list stores the current active sequence of numbers.
a = []
for i in range(n):
a.append(i + 1)
size = n
step = 2
# Each pass removes every step-position element from the active sequence.
print("Lucky Number Operation:")
while step <= size:
pos = step - 1
while pos < size:
# Shift values left to remove the element at index pos.
for j in range(pos, size - 1):
a[j] = a[j + 1]
size = size - 1
pos = pos + step - 1
for i in range(size):
print(a[i], end=" ")
print()
step = step + 1
print("Hence, the Lucky Numbers Less than", n, "are:", end=" ")
for i in range(size):
print(a[i], end=" ")Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.