Given an integer K, the task is to find the length of the smallest no. N which is divisible by K and formed by using 1 as its digits only. If no such number exists then print -1
Examples:
Input: K = 3
Output: 3
111 is the smallest number formed by using 1 only
which is divisible by 3.
Input: K = 7
Output: 6
111111 is the required number.
Input: K = 12
Output: -1
Naive approach:
- First we have to check if K is a multiple of either 2 or 5 then the answer will be -1 because there is no number formed by using only 1’s as its digits which is divisible by 2 or 5.
- Now iterate for every possible no. formed by using 1’s at most K times and check for its divisibility with K.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return length// of the resultant numberint numLen(int K){ // If K is a multiple of 2 or 5 if (K % 2 == 0 || K % 5 == 0) return -1; int number = 0; int len = 1; for (len = 1; len <= K; len++) { // Generate all possible numbers // 1, 11, 111, 111, ..., K 1's number = number * 10 + 1; // If number is divisible by k // then return the length if ((number % K == 0)) return len; } return -1;}// Driver codeint main(){ int K = 7; cout << numLen(K); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to return length // of the resultant number static int numLen(int K) { // If K is a multiple of 2 or 5 if (K % 2 == 0 || K % 5 == 0) { return -1; } int number = 0; int len = 1; for (len = 1; len <= K; len++) { // Generate all possible numbers // 1, 11, 111, 111, ..., K 1's number = number * 10 + 1; // If number is divisible by k // then return the length if ((number % K == 0)) { return len; } } return -1; } // Driver code public static void main(String[] args) { int K = 7; System.out.println(numLen(K)); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python implementation of the approach# Function to return length# of the resultant numberdef numLen(K): # If K is a multiple of 2 or 5 if (K % 2 == 0 or K % 5 == 0): return -1; number = 0; len = 1; for len in range(1,K+1): # Generate all possible numbers # 1, 11, 111, 111, ..., K 1's number = number * 10 + 1; # If number is divisible by k # then return the length if ((number % K == 0)): return len; return -1;# Driver codeK = 7;print(numLen(K));# This code contributed by Rajput-Ji |
C#
// C# implementation of the approachusing System;class GFG{ // Function to return length// of the resultant numberstatic int numLen(int K){ // If K is a multiple of 2 or 5 if (K % 2 == 0 || K % 5 == 0) return -1; int number = 0; int len = 1; for (len = 1; len <= K; len++) { // Generate all possible numbers // 1, 11, 111, 111, ..., K 1's number = number * 10 + 1; // If number is divisible by k // then return the length if ((number % K == 0)) return len; } return -1;}// Driver codestatic void Main(){ int K = 7; Console.WriteLine(numLen(K));}}// This code is contributed by mits |
PHP
<?php// PHP implementation of the approach// Function to return length// of the resultant numberfunction numLen($K){ // If K is a multiple of 2 or 5 if ($K % 2 == 0 || $K % 5 == 0) return -1; $number = 0; $len = 1; for ($len = 1; $len <= $K; $len++) { // Generate all possible numbers // 1, 11, 111, 111, ..., K 1's $number = $number * 10 + 1; // If number is divisible by k // then return the length if (($number % $K == 0)) return $len; } return -1;}// Driver code$K = 7;echo numLen($K);// This code is contributed by Akanksha Rai?> |
Javascript
<script>// javascript implementation of the approach // Function to return length // of the resultant number function numLen(K) { // If K is a multiple of 2 or 5 if (K % 2 == 0 || K % 5 == 0) { return -1; } var number = 0; var len = 1; for (len = 1; len <= K; len++) { // Generate all possible numbers // 1, 11, 111, 111, ..., K 1's number = number * 10 + 1; // If number is divisible by k // then return the length if ((number % K == 0)) { return len; } } return -1; } // Driver code var K = 7; document.write(numLen(K));// This code is contributed by Princi Singh </script> |
Output:
6
Time Complexity: O(K)
Auxiliary Space: O(1)
Efficient Approach: As we see in the above approach we generate all possible numbers like 1, 11, 1111, 11111, …, K times but if the value of K is very large then the no. will be out of range of data type so we can make use of the modular properties.
Instead of doing number = number * 10 + 1, we can do better as number = (number * 10 + 1) % K
Explanation: We start with number = 1 and repeatedly do number = number * 10 + 1 then in each iteration we’ll get a new term of the above sequence.
1*10 + 1 = 11
11*10 + 1 = 111
111*10 + 1 = 1111
1111*10 + 1 = 11111
11111*10 + 1 = 111111
Since we are repeatedly taking the remainders of the number at each step, at each step we have, newNum = oldNum * 10 + 1 .By the rules of modular arithmetic (a * b + c) % m is same as ((a * b) % m + c % m) % m. So, it doesn’t matter whether oldNum is the remainder or the original number, the answer would be correct.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return length// of the resultant numberint numLen(int K){ // If K is a multiple of 2 or 5 if (K % 2 == 0 || K % 5 == 0) return -1; int number = 0; int len = 1; for (len = 1; len <= K; len++) { // Instead of generating all possible numbers // 1, 11, 111, 111, ..., K 1's // Take remainder with K number = (number * 10 + 1) % K; // If number is divisible by k // then remainder will be 0 if (number == 0) return len; } return -1;}// Driver codeint main(){ int K = 7; cout << numLen(K); return 0;} |
Java
// Java implementation of the approachclass GFG { // Function to return length // of the resultant number public static int numLen(int K) { // If K is a multiple of 2 or 5 if (K % 2 == 0 || K % 5 == 0) return -1; int number = 0; int len = 1; for (len = 1; len <= K; len++) { // Instead of generating all possible numbers // 1, 11, 111, 111, ..., K 1's // Take remainder with K number = (number * 10 + 1) % K; // If number is divisible by k // then remainder will be 0 if (number == 0) return len; } return -1; } // Driver code public static void main(String[] args) { int K = 7; System.out.print(numLen(K)); }} |
Python3
# Python3 implementation of the approach# Function to return length# of the resultant numberdef numLen(K): # If K is a multiple of 2 or 5 if(K % 2 == 0 or K % 5 == 0): return -1 number = 0 len = 1 for len in range (1, K + 1): # Instead of generating all possible numbers # 1, 11, 111, 111, ..., K 1's # Take remainder with K number = ( number * 10 + 1 ) % K # If number is divisible by k # then remainder will be 0 if number == 0: return len return -1# Driver codeK = 7print(numLen(K)) |
C#
// C# implementation of the approach using System;class GFG { // Function to return length // of the resultant number public static int numLen(int K) { // If K is a multiple of 2 or 5 if (K % 2 == 0 || K % 5 == 0) return -1; int number = 0; int len = 1; for (len = 1; len <= K; len++) { // Instead of generating all possible numbers // 1, 11, 111, 111, ..., K 1's // Take remainder with K number = (number * 10 + 1) % K; // If number is divisible by k // then remainder will be 0 if (number == 0) return len; } return -1; } // Driver code public static void Main() { int K = 7; Console.WriteLine(numLen(K)); } } // This code is contributed by Ryuga |
PHP
<?php// PHP implementation of the approach // Function to return length // of the resultant number function numLen($K) { // If K is a multiple of 2 or 5 if ($K % 2 == 0 || $K % 5 == 0) return -1; $number = 0; $len = 1; for ($len = 1; $len <= $K; $len++) { // Instead of generating all possible numbers // 1, 11, 111, 111, ..., K 1's // Take remainder with K $number = ($number * 10 + 1) % $K; // If number is divisible by k // then remainder will be 0 if ($number == 0) return $len; } return -1; } // Driver code $K = 7; echo numLen($K); // This code is contributed by mits?> |
Javascript
<script>// javascript implementation of the approach // Function to return length// of the resultant numberfunction numLen(K){ // If K is a multiple of 2 or 5 if (K % 2 == 0 || K % 5 == 0) return -1; var number = 0; var len = 1; for (len = 1; len <= K; len++) { // Instead of generating all possible numbers // 1, 11, 111, 111, ..., K 1's // Take remainder with K number = (number * 10 + 1) % K; // If number is divisible by k // then remainder will be 0 if (number == 0) return len; } return -1;}// Driver codevar K = 7;document.write(numLen(K));// This code contributed by shikhasingrajput </script> |
Output:
6
Time Complexity: O(K)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
