Can you solve it?

Link : https://www.hackerrank.com/contests/intra-aust-preliminary-round-senior-group/challenges

18449995_1018356501634797_1094689825_n

আমাকে N দেয়া হবে এবং আমার ১ থেকে N পর্যন্ত সব ইন্টিজার এর বাইনারি রিপ্রেসেন্টেশন এ কতটি ১ আছে, তা বলতে হবে। ধরি N = ৮। উপরের চিত্র তে আমি ০ থেকে ৮ পর্যন্ত সংখ্যাগুলির বাইনারি লিখেছি। লক্ষ্য করলে দেখা যায়, এই বাইনারি এর মাঝে একটি নির্দিষ্ট সময় পরপর ১ আসে। প্রথম ঘর এর জন্য একটি ০, একটি ১, এভাবে, দ্বিতীয় ঘরের জন্য দু’টি ০, দু’টি ১, এভাবে… খেয়াল করলে দেখা যায় ব্যাপারটা আসলে ২ এর পাওয়ার হিসেবে আসতে থাকে। আমরা বাইনারি নম্বর এর এই ব্যাপারগুলি অবশ্যি জানি। এখন আমি এই জিনিসটি থেকে একটি প্যাটার্ন বানানোর চেষ্টা করবো।

যেহেতু আমার N জানা আছে, কাজেই প্রথমে N এর বাইনারি বের করে ফেলি। ৮ এর ক্ষেত্রে ১০০০। এখন খেয়াল করি, (ডান দিক থেকে ০ – ৮ সকল নম্বর) প্রথম ঘরে, ০ থেকে ৮ এর মাঝে ১ আছে মোট ৪ টি। দ্বিতীয় ঘরেও ৪ টি, তৃতীয় ঘরেও ৪ টি, চতুর্থ ঘরে ১ টি। মোট ১৩ টি ১ আছে। প্রতি ঘরের জন্য এই ১ এর কাউন্ট টা কিভাবে করবো ? কিছু টেস্টকেস চিন্তা করলে ব্যাপারটা সবার ধরতে পারার কথা। প্যাটার্ন বের করতে পারলে ভালো, নাহলে চিত্রের বামদিকে আমি আমার প্যাটার্ন এর ফরমুলা লিখে দিয়েছি। এখানে xtra জিনিসটি একটু ইম্পরটেন্ট। নরমালি আমরা ১,২,৪,৮,১৬… ২ এর পাওয়ার এর ব্যাপারগুলি সহজে প্যাটার্ন এ ফেলেতে পারি, কিন্তু যদি ৯,১৩,২১,…এরকম নম্বর থাকে, যেটা আসলে কমপ্লিট প্যাটার্ন এর মধ্যে পরে না, তাদের জন্য বারতি কিছু যোগ এর দরকার হয়। ৯ এর জন্য চিন্তা করলে এমনটা দেখা যাবে। যাহোক, এখানে ব্যাপারটা হল N এর বাইনারির length পর্যন্ত আমাকে লুপ চালায়ে আর কিছু ক্যালকুলেশন করে টোটাল কতটি ১ আছে তা বের করতে হবে।

Timus 1014 : Product of Digit

Prob link: Timus 1014: Product of Digit

প্রব্লেম এ চাওয়া হয়েছে যে , আমাকে একটা integer দেয়া হবে, আমাকে minimum এমন একটা integer বের করতে হবে যেখানে ঐ integer এর প্রত্যেক digit এর গুনফল ঐ integer এর সমান হয়।

test case চিন্তা করলে দেখা যায়, N = 10 ;

10 কে এভাবে লিখা যায়ঃ (2 * 5) , (5 * 2) .. দেখা যাচ্ছে যে আসলে 10 এর গুননীয়ক গুলা নিয়ে আমাদের চিন্তা করা লাগবে। দেখা যাচ্ছে  25 , 52 ,… 25 হচ্চে সবচেয়ে ছোট, তাই answre 25 for N = 10;

আমরা কিন্ত ( 1 * 10 ) এই combination টা নেইনাই , কারন 1,1,0 or 1,0,1 এর digit এর গুনফল N এর সমান হয়না।

এখন এটা solve করা যায় কিভাবে ? প্রশ্নে এ বলা হইছে digit এর গুনফল  N এর সমান হবে, এরমানে একটা জিনিস বলা যায় যে আমার উত্তর আসলে 0 to 9 digit এর কোন সংখ্যা হবে।

তাহলে loop এর code অনেকটা এরকম হবেঃ

for ( int digit = 9 ; digit > 1 ; digit — )

{

         // rest of the code

}

তাহলে তো প্রব্লেম টা খুবই সহজ হয়ে গেলো। আমাদের দেখতে হবে যে 2 থেকে 9 এর মাঝে কোন কোন digit দিয়ে N কে mod করা যায়, মানে ভাগশেষ শুন্য হয়। যখনই কোন সংখ্যা দিয়ে N ভাগ যাবে ঐ সংখ্যা দিয়ে N কে ভাগ করতে থাকতে হবে যতক্ষন N  আর ভাগ না যায়।

 অর্থাৎ,

while ( N % digit ==0 )

আমাদের মূল কাজ হল N এর divisor digit গুলি বের করা,মানে যেসব digit দিয়ে N কে মড করা যায় এমন digit.

এখন যেহেতু আমাদের নতুন একটা integer বের করতে হবে, কাজেই কেবলমাত্র একবার N কে মড করার পরেই থেমে গেলে হবে না, যতক্ষন মড করা যায় করতে থাকতে হবে। কাজেই , while লিখা হয়েছে।

উদাহরন দিলে ব্যাপারটা বোঝা সহজ হবে ,
N = 50  >>  ans = 255
N = 120 >> ans = 358

( Digit নিয়ে কাজ করার এইটা একটা reason , অনেকে Digit না নিয়ে only sqrt ( N ) পর্যন্ত লুপ চালায়ে first যেটা দিয়ে ভাগ যায় সেই সংখ্যা আর  N /  ( সেই সংখ্যা ) ans print করে , যা ভুল ; 120 এর জন্য খেয়াল করলেই বুঝা যায়ঃ

for ( int digit = 2 ; digit <= 9 ; digit++ ){
if ( N % digit == 0 ) {
cout << digit << N / digit << endl ;

                    return 0;

           }

}

120 এর জন্য হবে 260 ,যেটা ভুল কারন  2 * 6 * 0 == 0  ( not 120 )

valid code :

for ( int digit = 9 ; digit > 1 ; digit– ){
while ( N % digit == 0 ){
// rest of the calculation
}
}
এখন হিসাবের জন্য N = ১০ ধরি,
—> 10 % 5 == 0
কাজেই এটি while লুপ এ ঢুকবে। লুপের ভিতর আমরা দেখি যে 5 একটি ভ্যালিড ডিজিট আমাদের ফাইনাল রেজাল্ট এর জন্য, তাই আমরা 5 কে আমাদের প্রথম ডিজিট হিসেবে নিয়ে একটি ভ্যারিয়েবল ( SUM ) এ সেইভ করে রাখবো।এখন SUM এর মান 5, কাজেই আমাদের এখন N কে 5 দিয়ে ভাগ করতে হবে, কেননা আমরা 5 কে আমাদের ডিজিট হিসেবে নিয়ে নিয়েছি।

কাজেই N = N / 5 = 2
এরপর আমরা আবার দেখবো N % 2 == 0, কাজেই আমরা আমদের পরের ডিজিট টিও পেয়ে গেলাম।

( আশা করি এতক্ষনে সবাই বুঝে গেছি আমরা কেন লুপ ৯ থেকে ২ পর্যন্ত চালিয়েছি। )

কাজেই আমাদের ফাইনাল রেজাল্ট হবে এরকমঃ
25  =  2 * 10 + 5 * 1 ( multiple করার ব্যাপারটা তোমরা নিজেরা try করে দেখো )
অর্থাৎ রেজাল্ট = 25।
120 এর জন্য :  3 * 100 + 5 * 10 + 8 * 1 = 358.

Critical test case

N = 0 হলে আমাদের রেজাল্ট হবে 10, কারন 0 পজিটিভ, নেগেটিভ কোনটিই না এই প্রব্লেম এর জন্য। কাজেই 10 হচ্ছে প্রথম পজিটিভ রেজাল্ট।
N = 1 হলে রেজাল্ট হবে 1.
এখন N যদি প্রাইম নাম্বার হয়? এখানে একটি কন্ডিশন আছে, যা লুপ এর শেষে N কে চেক করে, আমরা এটি বুঝতে পারছি যে, লুপের শেষে N যদি 1 হয়, তাহলে আমাদের ফাইনাল অ্যান্সার হবে -1, কারন কোন ডিজিট ই N কে মড ( MOD ) করতে পারেনি। এটি আশা করি সবাই বুঝে গেছো।


ধন্যবাদ কষ্ট করে পড়ার জন্য। সবাই AC করায় ফেল 🙂

UVA 11254 : Consecutive Integers

Prob link : UVA 11254: Consecutive Integers

Problem টায় বলা হয়েছে আমাকে একটা integer দেয়া হবে, আমাকে ঐ integer টি আরো কতোগুলি consecutive integer এর summation এর মাধ্যমে বানানো যায় তা print করতে হবে।
Suppose 15 কে আমরা লিখতে পারি এভাবে ——>
15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8
15 = 15

দেখা যাচ্ছে যে এর মধ্যে প্রথম টির integer সংখ্যা বেশি, তাই আমাকে প্রথম টি ই print করা লাগবে।print করার জন্যে question এ যে format এর কথা বলা হয়েছে, সে অনুযায়ী print করলে আমাদের output হবে এরকম  :::
15 = 1 + … + 5  ( অর্থাৎ আমাকে consecutive integers এর  first এবং last integer টা print করতে হবে )
যদি এমন integer হয়, যাকে কোন consecutive integer এর summation এ ফেলা যায় না, তখন কেবল ঐ integer টাই print হবে।
Ex : For N = 8  ans   ===   8 = 8 + … + 8

Solve Technique :

আমরা sum of arithmetic progression সম্পর্কে নিশ্চই জানি।
যদি n তম integer পর্যন্ত summation বের করতে হয়, তাহলে সূত্র ঃ sum, Sn ( n terms ) = n / 2 + [ 2 * a + ( n – 1 ) * d ]
যেখানে , a = first term , n = last term , d = interval between numbers .
আমরা এই সূত্র ব্যবহার করে আমাদের উত্তর বের করবো।
যেহেতু আমাদের বলা আছে , consecutive integers, so আমাদের d এর মান হবে  one  ( 1 ) .
এখন আমাদের n জানা আছে, আমরা চাইলে brute force করে করতে পারি,  কিন্তু আমাদের range টাকে ( 10 ^ 9 ) মাথায় রাখতে হবে।
এতবড় জিনিস বারবার loop চালায়ে করলে TLE  ( Time Limit Exceeded ) খাওয়ার সম্ভাবনা অনেক বেশি, তাই আমরা আমাদের সূত্র ব্যবহার করে একটা ফরমুলা বানানোর চেষ্টা করবো যাতে আমাদের brute force এর time complexity কম হয়।
সূত্র টাকে আরেকভাবে লিখা যাক,  a = ( 2 * Sn + n – n * n ) / ( 2 * n )

হিসাবের সুবিধার জন্য আমরা এভাবে লিখলাম, এখন খেয়াল করে দেখো আমাদের জানা মান হল Sn , যা qs এ দেয়া থাকবে, আমাদের বের করতে হবে a এবং n । আমরা ২ টা কাজ করতে পারি, প্রতি a  এর জন্য লুপ চালায়ে n বের করতে পারি, অথবা উলটা কাজটাও করতে পারি।

এখন কথা হল লুপ চালাবো কতক্ষন ?

equation খেয়াল করলে দেখা যায় আমাদের R.H.S এ আছে 2 * Sn , আমরা square root of 2 * Sn থেকে 1 পর্যন্ত integer এর উপর লুপ চালায়ে n  এর মান বের করতে পারি এবং n  এর মান আমরা equation এ বসায়ে  a এর মান এর validity check করতে পারি।যখন ই আমরা valid একটা মান পাবো তখন আমাদের result এর a হবে equation থেকে প্রাপ্ত মান এবং n হবে   a + ( যেই মান এর জন্য আমরা valid a পেলাম সেই মান) – 1 ।

Qs 1 : Why sqrt ( 2 * Sn )  ?

Ans :
equation থেকে এটা easily observe করা যায়, n * n এই value টার আগে minus sign আছে, কাজেই, আমার  n এর মান sqrt ( 2 * Sn ) এর বেশি হলে negative integer আসবে , যা আসলে ভুল result দিবে।

Qs 2 : a এর validity check করবো কিভাবে ?

Ans : আমরা a = ( 2 * Sn + n – n * n ) / ( 2 * n )  এই সূত্র টা কাজে লাগাবো, sqrt ( 2 * Sn ) থেকে 1 পর্যন্ত লুপ চালায়ে আমরা প্রতি n এর জন্য  a এর মান এর validity দেখবো। a valid হবে তখনই যখন আমার equation এ n এবং Sn বসালে তা সত্য হবে।

a = ( 2 * Sn + n – n * n )  এটা থেকে আমরা একটা মান পাবো, এখন কখন এই মানটা সত্য? যখন a কে  ( 2 * n ) দিয়ে মড করলে মান শুন্য আসবে, কেবলমাত্র তখনই আমরা a এর একটা integer value পাবো এবং value টা হবে ( 2 * Sn + n – n * n ) / ( 2 * n ).

আশা করি এখন code লিখতে কোন সমস্যা হবার কথা না। code embed করে দিলাম, কিন্তু, suggestion রইল যাতে আগে সবাই নিজে চেষ্টা করে দেখবে। ধন্যবাদ।

Solution