Length of the smallest number which is divisible by K and formed by using 1’s only

0 0 8 minutes read

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 number
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
int main()
{
 
    int K = 7;
    cout << numLen(K);
 
    return 0;
}

Java

// Java implementation of the approach
class 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 number
def 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 code
K = 7;
print(numLen(K));
 
# This code contributed by Rajput-Ji

C#

// C# implementation of the approach
using System;
 
class 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
static 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 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++)
    {
 
        // 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:

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 number
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
int main()
{
 
    int K = 7;
    cout << numLen(K);
 
    return 0;
}

Java

// Java implementation of the approach
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(String[] args)
    {
        int K = 7;
        System.out.print(numLen(K));
    }
}

Python3

# Python3 implementation of the approach
 
# Function to return length
# of the resultant number
def 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 code
K = 7
print(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 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++) {
 
        // 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
var K = 7;
document.write(numLen(K));
 
 
// This code contributed by shikhasingrajput 
 
</script>

Output:

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 zambiatek!