Beautiful Non Divisible Number
Given an integer N find an N digit positive number X such that GCD of X and any of its digit is not greater than 1. Print -1 if the answer does not exist.
Examples:
Input: N = 5
Output: 57777
Explanation: 57777 has in total 5 digits in which gcd(57777, 5) = 1 and gcd(57777, 7) = 1Input: N = 2
Output: 57
Explanation: 57 has in total 2 digits in which gcd(57, 5)=1 and gcd(57, 7) = 1
Approach: To solve the problem, follow the below idea:
So, the main idea here is that we need to take in total N digits in a number X which should be > 0 and at the same time their gcd with X should be 1. If we try to take every time first digit as 5 in X and the remaining digit i.e N – 1 as 7 we are done with our target. As, this number has each digit > 0 and there gcd with s is always bound to be 1.
Step-by-step algorithm:
- Check if N == 1, then it is impossible to construct the answer.
- Initialize a string X of length N having all characters as ‘7’.
- Change the first character to 5.
- Print the string X as the final answer.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N = 13;
// If N == 1, then it is impossible to construct the answer
if (N == 1) {
cout << "-1\n";
}
// Construct a number having N digits, all equal to 7
string X(N, '7');
// Change the first digit to 5
X[0] = '5';
cout << X << "\n";
return 0;
}
public class Main {
public static void main(String[] args) {
int N = 13;
// If N == 1, then it is impossible to construct the answer
if (N == 1) {
System.out.println("-1");
}
// Construct a number having N digits, all equal to 7
StringBuilder X = new StringBuilder("7".repeat(N));
// Change the first digit to 5
X.setCharAt(0, '5');
System.out.println(X);
}
}
// This code is contributed by rambabuguphka
def GFG(N):
# If N == 1, then it is impossible to construct the answer
if N == 1:
return "-1"
# Construct a number having N digits all equal to 7
X = "7" * N
# Change the first digit to 5
X = "5" + X[1:]
return X
# Main function
def main():
N = 13
X = GFG(N)
print(X)
main()
using System;
class Program
{
static void Main()
{
int N = 13;
// If N == 1, then it is impossible to construct the answer
if (N == 1)
{
Console.WriteLine("-1");
}
else
{
// Construct a string having N digits, all equal to '7'
string X = new String('7', N);
// Change the first digit to '5'
X = '5' + X.Substring(1);
Console.WriteLine(X);
}
}
}
function GFG(N) {
// If N == 1, then it is impossible to the construct the answer
if (N === 1) {
return "-1";
}
// Construct a number having N digits
// all equal to 7
let X = "7".repeat(N);
// Change the first digit to 5
X = "5" + X.substring(1);
return X;
}
// Main function
function main() {
const N = 13;
const X = GFG(N);
console.log(X);
}
main();
Output
5777777777777
Time Complexity: O(N), where N is the number of digits of number X.
Auxiliary Space: O(1)
Contact Us