Cyclic Number

0 0 7 minutes read

A cyclic number is an integer in which cyclic permutations of the digits are successive multiples of the number. The most widely known is the six-digit number 142857 (Please see below explanation given in examples).
The following trivial cases are typically excluded for Cyclic Numbers.

Single digits, e.g.: 5
Repeated digits, e.g.: 555
Repeated cyclic numbers, e.g.: 142857142857

Given a number, check if it is cyclic or not.
Examples:

Input : 142857
Output : Yes
Explanation
    142857 × 1 = 142857
    142857 × 2 = 285714
    142857 × 3 = 428571
    142857 × 4 = 571428
    142857 × 5 = 714285
    142857 × 6 = 857142

We generate all cyclic permutations of the number and check if every permutation divides number of not. We also check for three conditions. If any of the three conditions is true, we return false.

C++

// Program to check if a number is cyclic. 
#include <bits/stdc++.h> 
using namespace std; 
  
#define ull unsigned long long int 
  
// Function to generate all cyclic permutations 
// of a number 
bool isCyclic(ull N) 
{ 
    // Count digits and check if all 
    // digits are same 
    ull num = N; 
    int count = 0; 
    int digit = num % 10; 
    bool allSame = true; 
    while (num) { 
        count++; 
        if (num % 10 != digit) 
            allSame = false; 
        num = num / 10; 
    } 
  
    // If all digits are same, then 
    // not considered cyclic. 
    if (allSame == true) 
        return false; 
  
    // If counts of digits is even and 
    // two halves are same, then the 
    // number is not considered cyclic. 
    if (count % 2 == 0) { 
        ull halfPower = pow(10, count / 2); 
        ull firstHalf = N % halfPower; 
        ull secondHalf = N / halfPower; 
        if (firstHalf == firstHalf && isCyclic(firstHalf)) 
            return false; 
    } 
  
    num = N; 
    while (1) { 
  
        // Following three lines generates a 
        // circular permutation of a number. 
        ull rem = num % 10; 
        ull div = num / 10; 
        num = (pow(10, count - 1)) * rem + div; 
  
        // If all the permutations are checked 
        // and we obtain original number exit 
        // from loop. 
        if (num == N) 
            break; 
  
        if (num % N != 0) 
            return false; 
    } 
  
    return true; 
} 
  
// Driver Program 
int main() 
{ 
    ull N = 142857; 
    if (isCyclic(N)) 
        cout << "Yes"; 
    else
        cout << "No"; 
    return 0; 
} 

Java

// Java Program to check if a number is cyclic 
  
class GFG { 
    // Function to generate all cyclic 
    // permutations of a number 
    static boolean isCyclic(long N) 
    { 
        // Count digits and check if all 
        // digits are same 
        long num = N; 
        int count = 0; 
        int digit = (int)(num % 10); 
        boolean allSame = true; 
        while (num > 0) { 
            count++; 
            if (num % 10 != digit) 
                allSame = false; 
            num = num / 10; 
        } 
  
        // If all digits are same, then 
        // not considered cyclic. 
        if (allSame == true) 
            return false; 
  
        // If counts of digits is even and 
        // two halves are same, then the 
        // number is not considered cyclic. 
        if (count % 2 == 0) { 
            long halfPower = (long)Math.pow(10, count / 2); 
            long firstHalf = N % halfPower; 
            long secondHalf = N / halfPower; 
            if (firstHalf == firstHalf && isCyclic(firstHalf)) 
                return false; 
        } 
  
        num = N; 
        while (true) { 
            // Following three lines generates a 
            // circular permutation of a number. 
            long rem = num % 10; 
            long div = num / 10; 
            num = (long)(Math.pow(10, count - 1)) 
                      * rem 
                  + div; 
  
            // If all the permutations are checked 
            // and we obtain original number exit 
            // from loop. 
            if (num == N) 
                break; 
  
            if (num % N != 0) 
                return false; 
        } 
  
        return true; 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        long N = 142857; 
        if (isCyclic(N)) 
            System.out.print("Yes"); 
        else
            System.out.print("No"); 
    } 
} 
  
// This code is contributed by Anant Agarwal. 

Python3

# Program to check if 
# a number is cyclic 
# Function to generate 
# all cyclic permutations 
# of a number 
def isCyclic(N): 
  
    # Count digits and check if all 
    # digits are same 
    num = N 
    count = 0
    digit =(num % 10) 
    allSame = True
  
    while (num>0): 
        count+= 1
        if (num % 10 != digit): 
            allSame = False
        num = num // 10
      
   
    # If all digits are same, then 
    # not considered cyclic. 
    if (allSame == True): 
        return False
   
    # If counts of digits is even and 
    # two halves are same, then the 
    # number is not considered cyclic. 
    if (count % 2 == 0): 
      
        halfPower = pow(10, count//2) 
        firstHalf = N % halfPower 
        secondHalf = N / halfPower 
        if (firstHalf == firstHalf and
            isCyclic(firstHalf)): 
            return False
      
   
    num = N 
    while (True): 
   
        # Following three lines 
        # generates a 
        # circular permutation 
        # of a number. 
        rem = num % 10
        div = num // 10
        num = pow(10, count - 1) * rem + div 
   
        # If all the permutations 
        # are checked 
        # and we obtain original 
        # number exit 
        # from loop. 
        if (num == N): 
            break
   
        if (num % N != 0): 
            return False
      
    return True
  
# Driver code 
  
N = 142857
if (isCyclic(N)): 
    print("Yes") 
else: 
    print("No") 
  
# This code is contributed 
# by Anant Agarwal. 

C#

// C# Program to check if a number is cyclic 
using System; 
  
class GFG { 
      
    // Function to generate all cyclic 
    // permutations of a number 
    static bool isCyclic(long N) 
    { 
          
        // Count digits and check if all 
        // digits are same 
        long num = N; 
        int count = 0; 
        int digit = (int)(num % 10); 
        bool allSame = true; 
        while (num > 0) 
        { 
            count++; 
            if (num % 10 != digit) 
                allSame = false; 
            num = num / 10; 
        } 
  
        // If all digits are same, then 
        // not considered cyclic. 
        if (allSame == true) 
            return false; 
  
        // If counts of digits is even and 
        // two halves are same, then the 
        // number is not considered cyclic. 
        if (count % 2 == 0) { 
            long halfPower = (long)Math.Pow(10, 
                                    count / 2); 
                                      
            long firstHalf = N % halfPower; 
              
            // long secondHalf = N / halfPower; 
            if (firstHalf == firstHalf &&  
                           isCyclic(firstHalf)) 
                return false; 
        } 
  
        num = N; 
        while (true) 
        { 
              
            // Following three lines generates a 
            // circular permutation of a number. 
            long rem = num % 10; 
            long div = num / 10; 
            num = (long)(Math.Pow(10, count - 1)) 
                    * rem + div; 
  
            // If all the permutations are checked 
            // and we obtain original number exit 
            // from loop. 
            if (num == N) 
                break; 
  
            if (num % N != 0) 
                return false; 
        } 
  
        return true; 
    } 
  
    // Driver code 
    public static void Main() 
    { 
        long N = 142857; 
          
        if (isCyclic(N)) 
            Console.WriteLine("Yes"); 
        else
            Console.WriteLine("No"); 
    } 
} 
  
// This code is contributed by vt_m. 

PHP

<?php 
// Program to check if a number is cyclic 
  
// Function to generate all cyclic  
// permutations of a number 
function isCyclic($N) 
{ 
    // Count digits and check if all 
    // digits are same 
    $num = $N; 
    $count = 0; 
    $digit = ($num % 10); 
    $allSame = true; 
  
    while ($num > 0) 
    { 
        $count += 1; 
        if ($num % 10 != $digit) 
        $allSame = false; 
        $num = (int)($num / 10); 
    } 
  
    // If all digits are same, then 
    // not considered cyclic. 
    if ($allSame == true) 
        return false; 
  
    // If counts of digits is even and 
    // two halves are same, then the 
    // number is not considered cyclic. 
    if ($count % 2 == 0) 
    { 
        $halfPower = pow(10, (int)($count / 2)); 
        $firstHalf = $N % $halfPower; 
        $secondHalf = $N / $halfPower; 
        if ($firstHalf == $firstHalf &&  
                 isCyclic($firstHalf)) 
            return false; 
    } 
  
    $num = $N; 
    while (true) 
    { 
  
        // Following three lines generates a 
        // circular permutation of a number. 
        $rem = $num % 10; 
        $div = (int)($num / 10); 
        $num = pow(10, $count - 1) * $rem + $div; 
  
        // If all the permutations are checked 
        // and we obtain original number, exit 
        // from loop. 
        if ($num == $N) 
            break; 
  
        if ($num % $N != 0) 
            return false; 
    } 
    return true; 
} 
  
// Driver code 
$N = 142857; 
if (isCyclic($N)) 
    print("Yes"); 
else
    print("No"); 
  
// This code is contributed by mits 
?> 

Javascript

<script> 
// Javascript Program to check if a number is cyclic 
  
    // Function to generate all cyclic 
    // permutations of a number 
    function isCyclic(N) 
    { 
        // Count digits and check if all 
        // digits are same 
        let num = N; 
        let count = 0; 
        let digit = Math.floor(num % 10); 
        let allSame = true; 
        while (num > 0) { 
            count++; 
            if (num % 10 != digit) 
                allSame = false; 
            num = Math.floor(num / 10); 
        } 
    
        // If all digits are same, then 
        // not considered cyclic. 
        if (allSame == true) 
            return false; 
    
        // If counts of digits is even and 
        // two halves are same, then the 
        // number is not considered cyclic. 
        if (count % 2 == 0) { 
            let halfPower = Math.floor(Math.pow(10, count / 2)); 
            let firstHalf = Math.floor(N % halfPower); 
            let secondHalf = Math.floor(N / halfPower); 
            if (firstHalf == firstHalf && isCyclic(firstHalf)) 
                return false; 
        } 
    
        num = N; 
        while (true) { 
            // Following three lines generates a 
            // circular permutation of a number. 
            let rem = num % 10; 
            let div = Math.floor(num / 10); 
            num = Math.floor(Math.pow(10, count - 1)) 
                      * rem 
                  + div; 
    
            // If all the permutations are checked 
            // and we obtain original number exit 
            // from loop. 
            if (num == N) 
                break; 
    
            if (num % N != 0) 
                return false; 
        } 
    
        return true; 
    } 
  
// driver function 
  
        let N = 142857; 
        if (isCyclic(N)) 
            document.write("Yes"); 
        else
            document.write("No"); 
  
</script> 

Output:

Yes

Reference :
https://en.wikipedia.org/wiki/Cyclic_number
This article is contributed by Ajay Puri. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above..

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!