medium
0 views

Integer – Max Factor Count

Find the integer with the maximum number of factors from a given list of integers

Understand the Problem

Problem Statement

Given N integers, find the integer that has the maximum number of factors. Print both the integer and its factor count. If multiple integers have the same maximum factor count, choose the first occurring one.

Constraints

  • 2 <= N <= 100
  • 1 <= Each integer value <= 10^5
  • All integers are positive
  • Input will always contain at least 2 integers

Examples

Example 1
Input
6
13 45 67 89 40 24
Output
40 8
Explanation

40 has 8 factors (1, 2, 4, 5, 8, 10, 20, 40), which is the maximum. Although 24 also has 8 factors, 40 appears first in the list.

Example 2
Input
5
25 1 32 53 16
Output
32 6
Explanation

32 has 6 factors (1, 2, 4, 8, 16, 32), which is more than any other number in the list.

Example 3
Input
3
12 18 6
Output
12 6
Explanation

12 has 6 factors (1, 2, 3, 4, 6, 12), which is more than 18 (6 factors: 1, 2, 3, 6, 9, 18) and 6 (4 factors: 1, 2, 3, 6).

Solution

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    
    int numbers[100];
    for (int i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
    }
    
    int maxFactors = 0;
    int resultNumber = 0;
    
    for (int i = 0; i < n; i++) {
        int currentNumber = numbers[i];
        int factorCount = 0;
        
        // Count factors of current number
        for (int j = 1; j <= currentNumber; j++) {
            if (currentNumber % j == 0) {
                factorCount++;
            }
        }
        
        // Update maximum if current has more factors
        if (factorCount > maxFactors) {
            maxFactors = factorCount;
            resultNumber = currentNumber;
        }
    }
    
    printf("%d %d\n", resultNumber, maxFactors);
    
    return 0;
}
Time:O(N * M) where N is the number of integers and M is the maximum value among them
Space:O(1) - constant extra space (excluding input array)
Approach:

The C solution:

  1. Reads N and the array of integers
  2. Iterates through each number in the array
  3. For each number, counts its factors by checking divisibility from 1 to the number itself
  4. Keeps track of the number with the maximum factor count
  5. Prints the result

The algorithm uses nested loops: outer loop for array elements, inner loop for factor counting.

Visual Explanation

Loading diagram...
All Problems