Nearest Integer – Factor

Find the nearest integer to N where the concatenation of its first and last digits is a factor of the integer itself.

Understand the Problem

Problem Statement

The program must accept an integer N as the input. The program must print the nearest integer of N based on the following conditions:

The concatenation of the first digit and the last digit of the integer must be a factor of the same integer.
If two such integers are equidistant to N, then program must print the smallest integer.

Constraints

100 ≤ N ≤ 10^8
The nearest integer must be within a reasonable range where the first-last digit concatenation forms a valid two-digit number (10-99)
If multiple valid integers are equidistant, choose the smaller one

Examples

Example 1

Input

Output

Explanation

The nearest possible integer is 105. The concatenation of the first digit (1) and the last digit (5) in 105 is 15. 15 is a factor of 105 (105 ÷ 15 = 7). So 105 is printed as the output.

Example 2

Input

Output

Explanation

For 240: first digit is 2, last digit is 0, concatenation gives 20. 20 is a factor of 240 (240 ÷ 20 = 12). This is the nearest valid integer to 241.

Example 3

Input

Output

Explanation

For 341 itself: first digit is 3, last digit is 1, concatenation gives 31. 31 is a factor of 341 (341 ÷ 31 = 11). Since N itself satisfies the condition, it is the nearest valid integer.

Solution

#include <stdio.h>
#include <stdlib.h>

int getFirstDigit(int n) {
    while (n >= 10) {
        n /= 10;
    }
    return n;
}

int getLastDigit(int n) {
    return n % 10;
}

int isFactor(int num, int factor) {
    return (factor != 0 && num % factor == 0);
}

int findNearestInteger(int N) {
    int left = N;
    int right = N;
    
    while (1) {
        // Check left side (decreasing)
        int first = getFirstDigit(left);
        int last = getLastDigit(left);
        int concatenated = first * 10 + last;
        
        if (isFactor(left, concatenated)) {
            return left;
        }
        
        // Check right side (increasing)
        if (right != left) {
            first = getFirstDigit(right);
            last = getLastDigit(right);
            concatenated = first * 10 + last;
            
            if (isFactor(right, concatenated)) {
                return right;
            }
        }
        
        left--;
        right++;
    }
}

int main() {
    int N;
    scanf("%d", &N);
    
    int result = findNearestInteger(N);
    printf("%d\n", result);
    
    return 0;
}

Time:O(k) where k is the distance to the nearest valid integer

Space:O(1)

Approach:

The C solution implements the bidirectional search approach:

getFirstDigit(): Extracts the first digit by repeatedly dividing by 10
getLastDigit(): Uses modulo operator to get the last digit
isFactor(): Checks if the concatenated number is a valid factor
findNearestInteger(): Searches outward from N in both directions

The main function reads input, calls the search function, and prints the result.

Visual Explanation

Loading diagram...

All Problems