Start with an integer x with 0 ≤ x < 10^d and repeat the following.
Write the current number with leading zeros so that it has exactly d digits, then subtract the number formed by its digits in increasing order from the number formed by its digits in decreasing order. The difference is the next number.
For example, with d = 4, 2111 becomes 2111 − 1112 = 999. 999 is written 0999, so it becomes 9990 − 0999 = 8991.
Call the numbers obtained this way a0 = x, a1, a2, … in order.
There are only 10^d numbers of d digits with leading zeros, so sooner or later an earlier number appears again.
Let aj be the first time an earlier number appears again, and let ai (i < j) be when that number first appeared.
You cannot know in advance how many steps it takes, so loop with a while statement.
For each input line, print i, j − i, and the smallest of the numbers forming the cycle ai, a(i+1), …, a(j−1), on one line separated by single spaces.
Print the smallest number as a plain integer without leading zeros.
Input
First line T (1 ≤ T ≤ 1000). Then T lines with d and x (2 ≤ d ≤ 10, 0 ≤ x < 10^d). x is given without leading zeros.
Output
T lines, each "i j−i smallest"
Example 1 · stdin
4
4 3524
4 2111
4 1111
2 9
stdout
3 1 6174
5 1 6174
1 1 0
0 5 9
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
A loop whose number of rounds you do not know is a while. Python while a not in seen:, C, C++, Java, C#, JavaScript and TypeScript while (...), Craykon while (condition) { }. The stopping condition is "have I seen this number before", and if you record number → step at which it first appeared in a map, i is right there (Python dict, JS/TS Map, Java HashMap<Long, Integer>, C# Dictionary<long, int>, C++ std::map, Craykon Dict() with Contains). C has no map, but with d ≤ 10 no more than thirty numbers appear, so scanning an array from the start is enough. Four traps: (1) turning the number into a string drops leading zeros. Treat 0999 as the three-digit 999 and you get 999 − 999 = 0 and stop. Pad it, as in Python str(a).zfill(d), JS/TS String(a).padStart(d, "0"), Java String.format("%0" + d + "d", a), C# a.ToString().PadLeft(d, '0'), Craykon ("" + a).PadLeft(d, "0"), or, as in C, peel off exactly d digits with % 10 so the zeros are counted. (2) With d = 10, numbers like 9876543210 exceed int (about 2.1 billion). C and C++ need long long, Java and C# need long, and Java's Integer.parseInt throws on such a number. Python integers have no size limit, and JS/TS/Craykon numbers are exact up to 2^53, so they work as they are. (3) Writing "stop when it equals the previous number" only stops at numbers that stand still, like 6174. With d = 2, five numbers go round, 09 → 81 → 63 → 27 → 45 → 09, and the loop never ends. (4) It is easy to report j, the step of the repeat, as the step count. What is asked is i, the number of steps before entering the cycle.
Pythonmain.py · 19 lines
def step(a, d): s = str(a).zfill(d) # 앞에 0을 채워 꼭 d자리로 big = int("".join(sorted(s, reverse=True))) small = int("".join(sorted(s))) return big - smallt = int(input())for _ in range(t): d, x = map(int, input().split()) first_seen = {} # 수 → 처음 나온 걸음 번호 a, k = x, 0 while a not in first_seen: first_seen[a] = k a = step(a, d) k += 1 i = first_seen[a] loop = [v for v, at in first_seen.items() if at >= i] print(i, k - i, min(loop))
JavaScriptmain.js · 28 lines
const lines = require("fs").readFileSync(0, "utf8").trim().split("\n");function step(a, d) { const digits = String(a).padStart(d, "0").split(""); // 앞에 0을 채워 꼭 d자리로 digits.sort(); const small = Number(digits.join("")); const big = Number(digits.reverse().join("")); return big - small;}const t = Number(lines[0]);const out = [];for (let c = 1; c <= t; c++) { const [d, x] = lines[c].trim().split(" ").map(Number); const firstSeen = new Map(); // 수 → 처음 나온 걸음 번호 let a = x; let k = 0; while (!firstSeen.has(a)) { firstSeen.set(a, k); a = step(a, d); k++; } const i = firstSeen.get(a); let min = Infinity; for (const [v, at] of firstSeen) if (at >= i) min = Math.min(min, v); out.push(`${i} ${k - i} ${min}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 29 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").trim().split("\n");function step(a: number, d: number): number { const digits: string[] = String(a).padStart(d, "0").split(""); // 앞에 0을 채워 꼭 d자리로 digits.sort(); const small = Number(digits.join("")); const big = Number(digits.reverse().join("")); return big - small;}const t = Number(lines[0]);const out: string[] = [];for (let c = 1; c <= t; c++) { const [d, x] = lines[c].trim().split(" ").map(Number); const firstSeen = new Map<number, number>(); // 수 → 처음 나온 걸음 번호 let a = x; let k = 0; while (!firstSeen.has(a)) { firstSeen.set(a, k); a = step(a, d); k++; } const i = firstSeen.get(a)!; let min = Infinity; for (const [v, at] of firstSeen) if (at >= i) min = Math.min(min, v); out.push(`${i} ${k - i} ${min}`);}console.log(out.join("\n"));
JavaMain.java · 41 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.HashMap;import java.util.Map;public class Main { // 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long으로 센다 static long step(long a, int d) { char[] digits = String.format("%0" + d + "d", a).toCharArray(); // 앞에 0을 채워 꼭 d자리로 Arrays.sort(digits); long small = Long.parseLong(new String(digits)); long big = Long.parseLong(new StringBuilder(new String(digits)).reverse().toString()); return big - small; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int c = 0; c < t; c++) { String[] p = in.readLine().trim().split(" "); int d = Integer.parseInt(p[0]); long a = Long.parseLong(p[1]); Map<Long, Integer> firstSeen = new HashMap<>(); // 수 → 처음 나온 걸음 번호 int k = 0; while (!firstSeen.containsKey(a)) { firstSeen.put(a, k); a = step(a, d); k++; } int i = firstSeen.get(a); long min = Long.MAX_VALUE; for (Map.Entry<Long, Integer> e : firstSeen.entrySet()) if (e.getValue() >= i) min = Math.min(min, e.getKey()); out.append(i).append(' ').append(k - i).append(' ').append(min).append('\n'); } System.out.print(out); }}
C#Main.cs · 42 lines
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ // 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long으로 센다 static long Step(long a, int d) { char[] digits = a.ToString().PadLeft(d, '0').ToCharArray(); // 앞에 0을 채워 꼭 d자리로 Array.Sort(digits); long small = long.Parse(new string(digits)); Array.Reverse(digits); long big = long.Parse(new string(digits)); return big - small; } static void Main() { int t = int.Parse(Console.ReadLine().Trim()); var out_ = new StringBuilder(); for (int c = 0; c < t; c++) { string[] p = Console.ReadLine().Trim().Split(' '); int d = int.Parse(p[0]); long a = long.Parse(p[1]); var firstSeen = new Dictionary<long, int>(); // 수 → 처음 나온 걸음 번호 int k = 0; while (!firstSeen.ContainsKey(a)) { firstSeen[a] = k; a = Step(a, d); k++; } int i = firstSeen[a]; long min = firstSeen.Where(e => e.Value >= i).Min(e => e.Key); out_.Append($"{i} {k - i} {min}\n"); } Console.Write(out_); }}
C++main.cpp · 37 lines
#include <algorithm>#include <iostream>#include <map>#include <string>// 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long long으로 센다long long step(long long a, int d) { std::string s = std::to_string(a); s.insert(0, d - s.size(), '0'); // 앞에 0을 채워 꼭 d자리로 std::sort(s.begin(), s.end()); long long small = std::stoll(s); std::reverse(s.begin(), s.end()); long long big = std::stoll(s); return big - small;}int main() { int t; std::cin >> t; while (t--) { int d; long long a; std::cin >> d >> a; std::map<long long, int> firstSeen; // 수 → 처음 나온 걸음 번호 int k = 0; while (!firstSeen.count(a)) { firstSeen[a] = k; a = step(a, d); k++; } int i = firstSeen[a]; long long min = -1; for (const auto& [v, at] : firstSeen) if (at >= i) { min = v; break; } // map은 작은 수부터 돈다 std::cout << i << ' ' << k - i << ' ' << min << '\n'; }}
Cmain.c · 40 lines
#include <stdio.h>/* 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long long으로 센다 */long long step(long long a, int d) { int count[10] = {0}; for (int i = 0; i < d; i++) { /* 꼭 d번 떼어 내면 앞자리 0도 센다 */ count[a % 10]++; a /= 10; } long long big = 0, small = 0; for (int g = 9; g >= 0; g--) for (int r = 0; r < count[g]; r++) big = big * 10 + g; for (int g = 0; g <= 9; g++) for (int r = 0; r < count[g]; r++) small = small * 10 + g; return big - small;}int main(void) { int t; scanf("%d", &t); while (t--) { int d; long long a; scanf("%d %lld", &d, &a); long long seen[64]; /* 나온 수를 차례대로(d ≤ 10이면 30개를 넘지 않는다) */ int k = 0, i = -1; while (1) { for (int s = 0; s < k; s++) if (seen[s] == a) i = s; if (i >= 0) break; seen[k++] = a; a = step(a, d); } long long min = seen[i]; for (int s = i; s < k; s++) if (seen[s] < min) min = seen[s]; printf("%d %d %lld\n", i, k - i, min); } return 0;}
Craykonmain.cray · 40 lines
// 한 걸음: 앞에 0을 채워 꼭 d자리로 쓰고, 큰 것부터 늘어놓은 수 − 작은 것부터 늘어놓은 수한걸음(a, d){ s = ("" + a).PadLeft(d, "0"); digits = []; foreach (ch in s) { digits.Add(ch); } digits.Sort(); small = digits.Join("").ToNumber(); digits.Reverse(); big = digits.Join("").ToNumber(); return big - small;}t = Console.ReadLine().Trim().ToNumber();for (c = 0; c < t; c++){ p = Console.ReadLine().Trim().Split(" "); d = p[0].ToNumber(); a = p[1].ToNumber(); firstSeen = Dict(); // 수 → 처음 나온 걸음 번호 order = []; // 나온 차례대로 k = 0; while (!firstSeen.Contains(a)) { firstSeen[a] = k; order.Add(a); a = 한걸음(a, d); k += 1; } i = firstSeen[a]; least = order[i]; for (s = i; s < k; s++) { least = Mathf.Min(least, order[s]); } Console.WriteLine(i + " " + (k - i) + " " + least);}