REPFREE - Editorial

editorial
1

Prerequisite : none.

Problem :- Given an integer N with at most nine digits, find and print the smallest repetition-free number that is larger than N. For instance, if N is 99, the answer would be 123. If there is no repetition-free number larger than N, we should print 0.

Explanation :-

Increment and Check:
Start from the given number n.
Increment n by 1, and for each incremented value, check if it’s a repetition-free number.
Keep incrementing n until you find the smallest repetition-free number larger than the given number.

Checking Repetition:

  • To check if a number is repetition-free, maintain a frequency array freq to keep track of the occurrences of each digit (from 1 to 9).
  • Iterate through each digit of the number, updating the frequency array.
    If any digit appears more than once or if the digit is 0, the number is not repetition-free.
  • If all digits appear exactly once and none of them is 0, the number is repetition-free.

C++ Solution :-

#include <bits/stdc++.h>

using namespace std;
bool check(int n) {
  int freq[10] = {
    0
  };
  while (n > 0) {
    int k = n % 10;
    freq[k]++;
    if (freq[k] > 1 || k == 0) {
      return false;
    }
    n /= 10;
  }
  return true;
}

int main() {
  int n;
  cin >> n;
  n++;
  while (n <= 987654321) {
    if (check(n)) {
      cout << n << endl;
      return 0;
    }
    n++;
  }
  cout << "0" << endl;
  return 0;
}