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 টা নেইনাই , কারন 110 or 101 এর 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

}

}

For calculation part let’s see for N = 10 how does the code works,

—> 10 % 5 == 0

so it will enter inside while loop. Inside loop we get that 5 is a valid digit for our final result, so we will take 5 as our first digit and store it in a variable say SUM ,

so now SUM = 5, then we have to divide N by 5 as we have already taken 5 as our digit,

so N = N / 5 . so now N = 2;

then again we see that N % 2 == 0 so we get our next digit ( আশা করি এতক্ষনে সবাই বুঝে গেছি আমরা কেন লুপ ৯ থেকে ২ পর্যন্ত চালিয়েছি। )

now we get our second digit 2 so our final sum will be 25 which can be written like this :

25  =  2 * 10 + 5 * 1 ( multiple করার ব্যাপারটা তোমরা নিজেরা try করে দেখো )

so answer is 25 ;

again for 120 answer is  3 * 100 + 5 * 10 + 8 * 1 = 358.

Critical test case :

N = 0 , answer is 10  ( 0 is neither a positive or a negative number for this problem, so 10 is the first non-negative digit )

for N = 1 answer is 1

And what if N is a prime number ? There lies a last condition that checks the value of N after the loop. I guess you all clearly understand now if N != 1 then the answer will be -1 as no digit could MOD the desired N , hence N may or may not be prime :p

সবাই 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