DTCC | OAMaster

01Find Reciprocal

Given an integer, find its reciprocal. The reciprocal will end in infinitely recurring digits. Print the recurrence twice with a space between the first and second repetition. For example, if N = 8, its reciprocal is 1/8 = 0.12500000..., so print 0.1250 0. If N = 9, its reciprocal is 1/9 = 0.111111..., so print 0.1 1. Function Description Complete the function findReciprocal in the editor. findReciprocal has the following parameter:

int N: the integer to find the reciprocal of Returns String: the recurrence of the reciprocal printed twice with a space between the repetitions

Constraints

2 ≤ N ≤ 10⁵

Example 1

Input:

N = 8

Output:

"0.1250 0"

Explanation: The reciprocal of 8 is 1/8 = 0.12500000..., so the output is 0.1250 0.

Example 2

Input:

N = 9

Output:

"0.1 1"

Explanation: The reciprocal of 9 is 1/9 = 0.111111..., so the output is 0.1 1.

解法

模拟长除法：从余数 1 开始，每步 rem = (rem * 10) % N，记录每个出现过的 rem 第一次出现的位置。再次出现时即为循环开始位置；之前的数字是非循环部分。最后输出 0. + 前缀 + 一个循环 + 空格 + 一个循环。复杂度 O(N)，空间 O(N)。

def find_reciprocal(N: int) -> str:
    digits = []
    seen = {}
    rem = 1
    while rem != 0 and rem not in seen:
        seen[rem] = len(digits)
        rem *= 10
        digits.append(str(rem // N))
        rem %= N
    if rem == 0:
        body = "".join(digits)
        return f"0.{body} 0"
    start = seen[rem]
    prefix = "".join(digits[:start])
    cycle = "".join(digits[start:])
    return f"0.{prefix}{cycle} {cycle}"

import java.util.*;

class Solution {
    String findReciprocal(int N) {
        StringBuilder digits = new StringBuilder();
        Map<Integer, Integer> seen = new HashMap<>();
        int rem = 1;
        while (rem != 0 && !seen.containsKey(rem)) {
            seen.put(rem, digits.length());
            rem *= 10;
            digits.append(rem / N);
            rem %= N;
        }
        if (rem == 0) return "0." + digits + " 0";
        int start = seen.get(rem);
        String prefix = digits.substring(0, start);
        String cycle = digits.substring(start);
        return "0." + prefix + cycle + " " + cycle;
    }
}

class Solution {
public:
    string findReciprocal(int N) {
        string digits;
        unordered_map<int, int> seen;
        int rem = 1;
        while (rem != 0 && !seen.count(rem)) {
            seen[rem] = digits.size();
            rem *= 10;
            digits += char('0' + rem / N);
            rem %= N;
        }
        if (rem == 0) return "0." + digits + " 0";
        int start = seen[rem];
        string prefix = digits.substr(0, start);
        string cycle = digits.substr(start);
        return "0." + prefix + cycle + " " + cycle;
    }
};