Given an integerĀ . The task is to find another integer which is permutation of n, divisible by 3 but not divisible by 6. Given that n is divisible by 6. If no such permutation is possible print -1.
Examples:Ā Ā
Input: n = 336 Output: 363 Input: n = 48 Output: -1
For a number to be divisible by 6, it must be divisible by 3 as well as 2, means every even integer divisible by 3 is divisible by 6. So, an integer which is divisible by 3 but not 6 is odd integer divisible by 3.
So, if integer n contains any odd integer then there exists a permutation which is divisible by 3 but not 6, else no such permutation exist.
Algorithm:
- let LEN is length of integer (i.e. ceil(log10(n))).
- iterate over LEN and check whether n is even or odd.
- if n is odd return n
- else right ā rotate n once. and continue.
- if LEN is over return -1
Below is the implementation of the above approach:Ā
C++
// C++ program to find permutation of n // which is divisible by 3 but not // divisible by 6 Ā
#include <bits/stdc++.h> using namespace std; Ā
// Function to find the permutation int findPermutation( int n) { Ā Ā Ā Ā // length of integer Ā Ā Ā Ā int len = ceil ( log10 (n)); Ā
Ā Ā Ā Ā for ( int i = 0; i < len; i++) { Ā Ā Ā Ā Ā Ā Ā Ā // if integer is even Ā Ā Ā Ā Ā Ā Ā Ā if (n % 2 != 0) { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // return odd integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return n; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā else { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // rotate integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = (n / 10) + (n % 10) * pow (10, len - i - 1); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continue ; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā } Ā
Ā Ā Ā Ā // return -1 in case no required Ā Ā Ā Ā // permutation exists Ā Ā Ā Ā return -1; } Ā
// Driver Code int main() { Ā Ā Ā Ā int n = 132; Ā
Ā Ā Ā Ā cout << findPermutation(n); Ā
Ā Ā Ā Ā return 0; } |
Java
// Java program to find permutation // of n which is divisible by 3 // but not divisible by 6 import java.lang.*; import java.util.*; Ā
class GFG { // Function to find the permutation static int findPermutation( int n) { Ā Ā Ā Ā // length of integer Ā Ā Ā Ā int len = ( int )Math.ceil(Math.log10(n)); Ā
Ā Ā Ā Ā for ( int i = 0 ; i < len; i++) Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā // if integer is even Ā Ā Ā Ā Ā Ā Ā Ā if (n % 2 != 0 ) Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // return odd integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return n; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā else Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // rotate integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = (n / 10 ) + (n % 10 ) * Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ( int )Math.pow( 10 , len - i - 1 ); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continue ; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā } Ā
Ā Ā Ā Ā // return -1 in case no required Ā Ā Ā Ā // permutation exists Ā Ā Ā Ā return - 1 ; } Ā
// Driver Code public static void main(String args[]) { Ā Ā Ā Ā int n = 132 ; Ā
Ā Ā Ā Ā System.out.println(findPermutation(n)); } } Ā
// This code is contributed // by Akanksha Rai(Abby_akku) |
Python3
# Python3 program to find permutation # of n which is divisible by 3 but # not divisible by 6 from math import log10, ceil, pow Ā
# Function to find the permutation def findPermutation(n): Ā Ā Ā Ā Ā Ā Ā Ā Ā # length of integer Ā Ā Ā Ā len = ceil(log10(n)) Ā
Ā Ā Ā Ā for i in range ( 0 , len , 1 ): Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # if integer is even Ā Ā Ā Ā Ā Ā Ā Ā if n % 2 ! = 0 : Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # return odd integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return n Ā Ā Ā Ā Ā Ā Ā Ā else : Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # rotate integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = ((n / 10 ) + (n % 10 ) * Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā pow ( 10 , len - i - 1 )) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continue Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # return -1 in case no required Ā Ā Ā Ā # permutation exists Ā Ā Ā Ā return - 1 Ā
# Driver Code if __name__ = = '__main__' : Ā Ā Ā Ā n = 132 Ā
Ā Ā Ā Ā print ( int (findPermutation(n))) Ā
# This code is contributed # by Surendra_Gangwar |
C#
// C# program to find permutation // of n which is divisible by 3 // but not divisible by 6 using System; Ā
class GFG { // Function to find the permutation static int findPermutation( int n) { Ā Ā Ā Ā // length of integer Ā Ā Ā Ā int len = ( int )Math.Ceiling(Math.Log10(n)); Ā
Ā Ā Ā Ā for ( int i = 0; i < len; i++) Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā // if integer is even Ā Ā Ā Ā Ā Ā Ā Ā if (n % 2 != 0) Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // return odd integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return n; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā else Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // rotate integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = (n / 10) + (n % 10) * Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ( int )Math.Pow(10, len - i - 1); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continue ; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā } Ā
Ā Ā Ā Ā // return -1 in case no required Ā Ā Ā Ā // permutation exists Ā Ā Ā Ā return -1; } Ā
// Driver Code public static void Main() { Ā Ā Ā Ā int n = 132; Ā
Ā Ā Ā Ā Console.WriteLine(findPermutation(n)); } } Ā
// This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php // PHP program to find permutation // of n which is divisible by 3 but // not divisible by 6 Ā
// Function to find the permutation function findPermutation( $n ) { Ā Ā Ā Ā // length of integer Ā Ā Ā Ā $len = ceil (log10( $n )); Ā
Ā Ā Ā Ā for ( $i = 0; $i < $len ; $i ++) Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā // if integer is even Ā Ā Ā Ā Ā Ā Ā Ā if ( $n % 2 != 0) Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // return odd integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return (int) $n ; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā else Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // rotate integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā $n = ( $n / 10) + ( $n % 10) * Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā pow(10, $len - $i - 1); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continue ; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā } Ā
Ā Ā Ā Ā // return -1 in case no required Ā Ā Ā Ā // permutation exists Ā Ā Ā Ā return -1; } Ā
// Driver Code $n = 132; Ā
echo findPermutation( $n ); Ā
// This code is contributed by mits ?> |
Javascript
<script> // java scriptĀ program to find permutation // of n which is divisible by 3 but // not divisible by 6 Ā
// Function to find the permutation function findPermutation(n) { Ā
Ā Ā Ā Ā // length of integer Ā Ā Ā Ā let len = Math.ceil(Math.log10(n)); Ā
Ā Ā Ā Ā for (let i = 0; i < len; i++) Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // if integer is even Ā Ā Ā Ā Ā Ā Ā Ā if (n % 2 != 0) Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // return odd integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return parseInt(n); Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā else Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // rotate integer Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n = (n / 10) + (n % 10) * Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Math.pow(10, len - i - 1); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā continue ; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā Ā // return -1 in case no required Ā Ā Ā Ā // permutation exists Ā Ā Ā Ā return -1; } Ā
// Driver Code let n = 132; Ā
document.write( findPermutation(n)); Ā
// This code is contributed by sravan kumar (vignan) </script> |
213
Ā
Time complexity: O(logn) for given input number n
Auxiliary space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!