algoadvance

Leetcode 2549. Count Distinct Numbers on Board

Problem Statement

2549. Count Distinct Numbers on Board

You are given a positive integer n representing the initial number written on a board. Every day, for any number x written on the board, you write down every factor of x - 1 on the board. This process continues until no more new numbers can be written on the board. You need to determine how many distinct numbers will be present on the board at the end.

Clarifying Questions

  1. Are we only writing factors of x - 1 where x is the current number written on the board?
    • Yes, every day you write factors of x - 1 for the numbers currently on the board.
  2. What is the constraint on the input value of n?
    • The problem should give constraints, but typically it will be something along the lines of 1 <= n <= 10^9 considering the problem statement described.
  3. Do we start with only the number n on the board initially?
    • Yes, we start with n and based on the factors of x - 1, other numbers are added to the board.

Strategy

  1. Initialization:
    • Start with the number n on the board and a set to hold distinct numbers.
  2. Process:
    • For every number x currently on the board, add all factors of x - 1 to the set.
    • Use a loop or recursion to continue this process until no new numbers are generated.
  3. Tracking Factors:
    • For each new number x - 1, find all its factors efficiently using integer factorization.
  4. Stopping Condition:
    • The process continues until no new number is added to the set.

Code

Here’s a Java implementation to determine the number of distinct numbers on the board:

import java.util.HashSet;
import java.util.Set;

public class CountDistinctNumbersOnBoard {
    
    public static int countDistinctNumbers(int n) {
        Set<Integer> board = new HashSet<>();
        board.add(n);
        
        while (true) {
            Set<Integer> newNumbers = new HashSet<>();
            for (int number : board) {
                if (number > 1) {
                    int value = number - 1;
                    for (int i = 1; i * i <= value; i++) {
                        if (value % i == 0) {
                            newNumbers.add(i);
                            if (i != value / i) {
                                newNumbers.add(value / i);
                            }
                        }
                    }
                }
            }
            // If no new numbers are added, we are done
            if (board.containsAll(newNumbers)) {
                break;
            }
            board.addAll(newNumbers);
        }
        
        return board.size();
    }
    
    public static void main(String[] args) {
        int n = 12;  // example input, can be changed
        System.out.println(countDistinctNumbers(n));
    }
}

Time Complexity

Given the above considerations, the time complexity can be high for larger values of n, but steps are taken to ensure only distinct numbers are processed.

By executing and understanding the logic, you should be able to understand how many distinct numbers will eventually be on the board.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI