Using String as Integer and Integer as String

Sometimes we encounter questions like Given a integer N and you are allowed to swap adjacent digits. Find minimum swaps such that number is divisible by 25. If it is impossible to obtain a number that is divisible by 25, then print “Not Possible”.

1 <= N <= 10^18

We can easily tell for number being divisible by 25 its last two digits must be “00” , “25” , “50” or “75”.

A Brute force solution would be try every available digits at last two places and we will do this greedily and this will give us minimum swaps.

But Question is Performing swaps and then checking number is divisible by 25 or not , will be hard if we take N as an integer input , even if take N as string input then division will bother us.

So here are some inbuilt functions to solve this problem which can convert integer to string and string to integer.

converting Integer into String : string s = to_string( N ) ;

More generally to_string() is an overloaded function so it will convert any numeric value into string.

converting String into Integer : long long N = atoll( s.c_str() ) ;

atoll returns long long int value , but if you want to return long int value then you can use atol( s.c_str() ) and for double value go for atof( s.c_str() ) .

Now it is easier for us to deal with this problem. As now we dealing with digits polynomial time want bother us any more

Now we can use counter i ( it will place i’th digit at last place ) and counter j ( it will place j’th digit at last second place ) to iterate over digits starting from first index of number.Then if current number is divisible by 25 we will update answer with current swap count if it is smaller than least count encountered yet.

One question may arise what if we encounter any leading zeros?? In that case swap it with nearest non zero digit in number.

Here is the code for given task ( When you see algorithm don’t just see it take a pen and paper , now think of a test case and apply steps of algorithms on that test case )

CODE
#include<bits/stdc++.h>

using namespace std ;

int main()
{
    long long n ;
    cin >> n ;

    string s = to_string( n ) ;   /// CONVERTS NUMBER TO STRING

    int l = s.size() ;  /// STORING SIZE OF STRING

    long long ans = 1e16 ;  /// INTIALLY WE NEED INFINITE SWAPS

    for( int i = 0 ; i < l ; i++ )
        for( int j = 0 ; j < l ; j++ )
        {
            if( i == j ) continue ;

            long long swaps = 0 ;   /// COUNT NUMBER OF SWAPS

            string temp = s ;  ///  WE NEED ORIGINAL STRING AGAIN SO STORE IT IN TEMP
                                        ///  AND APPLY YOUR OPPERATIONS ON IT

            for( int k = i ; k < l - 1 ; k++ )   ///   TAKING i th DIGIT TO LAST POSITION
            {
                swap( temp[ k ] , temp[ k + 1 ] ) ;
                swaps++ ;
            }

            for( int k = j - ( j > i ) ; k < l - 2 ; k++ )   /// TAKING j th DIGIT TO LAST SECOND POS
            {
                swap( temp[ k ] , temp[ k + 1 ] ) ;
                swaps++ ;
            }

            int pos = -1 ;  /// INTIALLY WE CONSIDER THERE ARE NO LEADING ZEROS

            for( int k = 0 ; i < l ; k++ )  ///   IS THERE ANY LEADING ZEROS??
                if( temp[ k ] != '0' )
                {
                    pos = k ;
                    break ;
                }

            while( pos > 0 )
            {
                swap( temp[ pos ] , temp[ pos - 1 ] ) ;
                swaps++ ;
                pos-- ;
            }

            /// NOW ITS TIME TO CHECK NUMBER WE RECVIED IS
            ///  DIVISIBLE BY 25

            long long temp_number = atoll( temp.c_str() ) ;  /// CONVERTING STRING INTO 
                                                                                                      INTEGER

            if( temp_number % 25 == 0 )
                ans = min( ans , swaps ) ;
        }

    if( ans != 1e16 )    ///  If it is possible to obtain a number that is divisible by 25
        cout << ans << endl ;
    else
        cout << "Not Possible" << endl ;
}
6 Likes