প্যালিনড্রমিক সংখ্যা এবং SPOJ-The Next Palindrome সমস্যা

1. প্যালিনড্রমিক সংখ্যা

প্যালিনড্রমিক সংখ্যা আসলে কি জিনিস এটা খাই না পরে??? 

আজকে আমি যে বিষয় নিয়ে আলোচনা করবো সেটা হচ্ছে প্যালিনড্রমিক সংখ্যা।আসলে কোন সংখ্যা অথবা কোন একটা লেখা কে তখনই আমরা প্যালিনড্রমিক বলবো যখন সংখ্যাটাকে ডান থেকে বামে অথবা বাম থেকে ডানে উল্টিয়ে লেখলে একি হবে যেমন ২৩৩২,abkba,madam ইত্যাদি।প্রথমে আমরা যদি ২৩৩২ কে ডান থেকে উল্টিয়ে লেখি তাহলে সবার ডানে রয়েছে ২ তার  পর ৩ তার পর আবার ৩ এবং ২।তাহলে উল্টানো সংখ্যা হবে ২৩৩২।দেখেন এটা কিন্তু আমাদের আগের সংখ্যাটাই তার মানে এই সংখ্যা টা একটা প্যালিনড্রমিক সংখ্যা বলতে পারবো।যদি কোন একটা সংখ্যা প্যালিনড্রমিক সংখ্যা হয় তাহলে সবার ডানের সংখ্যা তার সাথে সবার বামের সংখ্যা টা মিলে যাবে,এই ভাবে করে ডানের এবং বামের সংখ্যা পরীক্ষা করলেই আমরা বুঝতে পারবো এটা কি আসলে প্যালিনড্রমিক সংখ্যা কি না?আর এই পরীক্ষাটা হবে সংখ্যাটার লেন্তের মাঝ পর্যন্ত।তাহলে এইবার আমরা কোন একটা সংখ্যা প্যালিনড্রমিক কিনা  দেখার জন্য একটা প্রোগ্রাম লেখে ফেলি।নিচে কোড দেয়া হল। 

 public static boolean Ispalindrome(String s)
    {
        for(int i=0,j=s.length()-1;i<j;i++,j--)
        {
            if(s.charAt(i) !=s.charAt(j))
            {
                return false;
            }
        }
        return true;
    }

 উপরের public static boolean Ispalindrome(String s); এই ফাংশন টা আসলে তখনই সত্যি হবে যখন ফাংশন এর ভিতর দেয়া স্ট্রিং s এর মান প্যালিনড্রমিক হবে। 

যাক তাহলে আমরা প্যালিনড্রমিক সংখ্যা নিয়ে মোটামুটি জেনেগেছি,যে এটা খাই না পরে।

এই বার একটা সমস্যার দিকে যাবো। 

সমস্যা টি হচ্ছে-: http://www.spoj.com/problems/PALIN/
এই সমস্যাই বলা হয়েছে k একটা সংখ্যা দেয়া হবে যার মান 1000000 থেকে ছোট,এবং k থেকে বড় এমন একটা সংখ্যা বের করতে হবে যে সংখ্যাটি প্যালিনড্রমিক সংখ্যা কিন্ত এটাই সবচে ছোট প্যালিনড্রমিক সংখ্যা যেটা k থেকে বড়।তাহলে এই সমস্যা সমধানের জন্য একটা ফাংশন লেখি যেটা আসলে k থেকে বড় এটা প্যালিনড্রমিক সংখ্যা সংখ্যা দিবে
   public static String bruteForce(String s)
   {
       BigInteger i=new BigInteger(s);
       while(true)
       {
           i=i.add(BigInteger.ONE);
          final String result=i.toString();
          if(Ispalindrome(result))
          {
              return result;
          }
       }
   }
এই  bruteForce(String s); ফাংশন টা আসলে আমাদের একটা স্ট্রিং উপহার দিবে যেটা কিনা k থেকে বড় একটা প্যালিনড্রমিক সংখ্যা।কি মজা প্রবলেম সমাধান হয়ে গেল...... :) :)
এই ধরনের সমধান কে বলা হয় brute-force।

রাখেন মিয়া কউ যান...।এই সমাধান  যদি submit দেন তাহলে আপনাকে অবশ্যই টাইম লিমিট খেতে হবে কারণ সমস্যাই যে ধরনের সংখ্যার কথা বলা হয়েছে সেটা এইভাবে করলে অনেক সময় এর দরকার তাহলে এখন কি হবে????? সমস্যা যেখানে রয়েছে সমধান ও  সেখানেই রয়েছে একটু ভাল করে খেয়াল করলেই বুঝতে পারবো। 
দেখেন কোন একটা সংখ্যাকে  যদি আমরা  তার মধ্যের অবস্থান থেকে দর্পণ করি তাহলে কিন্তু আমরা একটা
প্যালিনড্রমিক সংখ্যা পেয়ে যাচ্ছি যেমন-ঃ ৬৫৪৩২ এই সংখ্যাকে যদি  তার মধ্যের অবস্থান থেকে দর্পণ করি তাহলে আমরা পাবো ৬৫৪৫৬ যেটা একটা প্যালিনড্রমিক সংখ্যা।এইবার আমরা একটা ফাংশন লেখি যেটা আমাদের একটা দর্পণ প্যালিনড্রমিক সংখ্যা দিবে।
  public static String Mirror(String s)
   {
       char []arr=s.toCharArray();
       int midpoint=arr.length/2;
       int i=arr.length%2==0?midpoint:midpoint+1;
       while(i<arr.length)
       {
           arr[i]=arr[midpoint-1];
           i++;
           midpoint--;
       }
       return new String(arr);
   }
public static String Mirror(String s); এই ফাংশনটা আমাদের কে একটা প্যালিনড্রমিক সংখ্যা উপহার দিবে।কিন্তু সমস্যা হচ্ছে এই দর্পণ সংখ্যাটি কোন কোন সময় k থেকে ছোট ও হয়ে যেতে পারে আসলে আমাদের k থেকে ছোট প্যালিনড্রমিক সংখ্যা দরকার নেই।যেমনঃ- k=১২৩৪৫ দর্পণ করলে আমরা পাবো ১২৩২১  যে সংখ্যাটি আসলে k থেকে ছোট। আমাদের দরকার k থেকে বড় সংখ্যা। এই অবস্থাই আমরা একটা কাজ করতে পারি k=১২৩৪৫ এই  সংখ্যার মধ্যের অবস্থান মানে ৩ কে যদি এক বারিয়ে দেয় তাহলে হবে k=১২৪৫৫ এবং এইবার তাকে দর্পণ করি তাহলে পাবো->১২৪২১ দেখেন এই সংখ্যাটা কিন্তু আমাদের k=১২৩৪৫ থেকে বড় এবং সেটাই হচ্ছে k থেকে বড় একটা  প্যালিনড্রমিক সংখ্যা যেটা আমাদের দরকার ছিল।আরেকটু বাকি আছে যেমন যদি মধ্যের অবস্তানের সংখ্যা টা ৯ হয় তাহলে আমরা কি করবো??আরে বুঝেন নাই এখন ঐ ব্যাটা ৯ কে আমরা ০ বানিয়ে দিবো এবং তার আগের সংখ্যাটিকে এক বারিয়ে দিবো যেহেতু ডেসিমাল সংখ্যার নিয়ম অনুযায়ী ৯ এর পর আর কোন সংখ্যা নেই।যেমনঃ- k=১২৯৪৫ কে আমরা যদি দর্পণ করতে চাই তাহলে প্রথমে k=১৩০৪৫ করে নিতে হবে এবং পড়ে যদি তাকে দর্পণ করি তাহলে পাবো ১৩০৩১। এই বার আমরা একটা ফাংশন লেখি যেটা কিনা আমাদের কে  k এর থেকে বড় একটা প্যালিনড্রমিক সংখ্যা  দিবে। 
  public static String incrementFromMiddle(String s);
   {
       final char[]arr=s.toCharArray();
       final int midposition=arr.length/2;
       int currentpostion=arr.length%2==0?midposition-1:midposition;
       boolean found=false;
       while(currentpostion>=0 && !found)
       {
           char c=arr[currentpostion];
           char inc;
           if(c=='9')     
           {
               inc='0';
           }
           else
           {
               inc=(char)(c+1);
               found=true;
           }
           arr[currentpostion]=inc;
           if(!found)
           {
               currentpostion--;
           }
       }
       if(!found)
       {
           char newarr[]=new char[arr.length+1];
           newarr[0]='1';
           System.arraycopy(arr, 0, newarr, 1, arr.length);
           return new String(newarr);
       }
       else
       {
           return new String(arr);
       }
   }
   এই  public static String incrementFromMiddle(String s); ফাংশন টাই আসলে আমাদের কে সেই প্যালিনড্রমিক সংখ্যা দিবে যেটা পেলে আমরা আমাদের মহারানী কে ফিরে পাবো...
সবাই ভাল থাকবেন এবং কোন ভুল হলে জানবেন... নিচে সম্পন্ন কোডটা দিলাম==>>
https://gist.github.com/fazlulkabir94/03854e302049f33b9c5d