Gotitt

Strange Counter

noreply@blogger.com (Dinesh) — Sun, 18 Sep 2016 18:19:00 +0000

Bob has a strange counter. At the first second, , it displays the number . At each subsequent second, the number displayed by the counter decrements by .

The counter counts down in cycles. In the second after the counter counts down to , the number becomes the initial number for that countdown cycle and then continues counting down from the new initial number in a new cycle. The diagram below shows the counter values for each time in the first three cycles:

Given a time, , find and print the value displayed by the counter at time .

Hints:

The last 'time' value of cycle 1 is 3 which is 3*1=3*(2^1-1).
The last 'time' value of cycle 2 is 9 which is 3*3=3*(2^2-1).
The last 'time' value of cycle 3 is 21 which is 3*7=3*(2^3-1).

So, we will use a while loop and keep doubling n, which will represents 2^1, 2^2, 2^3 part. The loop stops when it reaches to a cycle whose max time is bigger than the real time t, then we know that it has reached the last cycle.

For example :
In the second cycle, time =7 has value=3, and the max time of the second cycle is 9. We find the relationship between them is 3 = 9 - 7 + 1, which is why we print (3 * (n - 1) - t + 1) to get the output of 3 when t is 7.

Here is my code:

#include <iostream>using namespace std;

int main(){

long long t,n=2;

cin >> t;

**while(3(n-1)<t)n=2;**

**cout<<3*(n-1)-t+1<<endl;**

return 0;

}

Question source:- hackerrank.com

Almost Sorted

noreply@blogger.com (Dinesh) — Sun, 18 Sep 2016 15:55:00 +0000

Given an array with elements, can you sort this array in ascending order using only one of the following operations?

Swap two elements.
Reverse one sub-segment.

Input Format
The first line contains a single integer,

, which indicates the size of the array.
The next line contains

integers separated by spaces.

n  
d1 d2 ... dn

Constraints

All

are distinct.

Output Format

If the array is already sorted, output yes on the first line. You do not need to output anything else.
If you can sort this array using one single operation (from the two permitted operations) then output yes on the first line and then:
If you cannot sort the array in either of the above ways, output no in the first line

Here are my tips.

Create a dynamic Array A of size n+2, input the values in the array with A[0]=0 and A[ n+2] =max_value of n.
Starting from index 1, loop through it till you get the first anomaly (i.e when A[ i ]>A[ i+1] ) take note of the index and break the loop.
Now starting from index n till index j, loop though it and check for all the anomaly, take the index of the first anomaly. Now take note of all the anomaly whether it's a peak or valley as well as number of anomaly (peak in case when A[ i ]>A[ i+1] && A[ i ] >A[ i-1] and valley is case when A[ i ]<A[ i+1] && A[ i ] <A[ i-1] ). See my code below for more clarification. Keep track of the index of the peak/valley with the help of a vector.
Now if the output is yes than the following will be true.
if all of 4 is not there than we cannot sort the array in one operation so output "no".

Here are few sample input to boost your thinking.

Input:

1 5 4 3 2 6

Output : reverse 2 5

Input

1 2 9 4 5 6 7 8 3

Output: swap 3 9

Input

1 2 9 4 5 8 7 6 3

Output: no

Input:

1 2 10 4 5 8 7 6 9 3

Output: no

Input

1 2 4 3 5

Output: swap 2 5

My solution:

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n,j=0,k=0,count=0,dn=0,up=0; /*initializing j and k to take note of the first anomaly from beginning and end, count to keep track of the number of anomaly, dn for valley and up for peak */

cin>>n;

vector<int> s;

int* A=new int[n+2]; /* initializing a dynamic array A of size n+2 */

A[0]=0; /* assigning A[0] =0 */

for(int i=1 ; i<=n; i++){

cin>>A[ i ]; /* Filling the array */

}

A[n+1]=1000001; /* assigning A[n+1]= Max_value of n i.e 100001 */

for(int i=1 ; i<=n-1 ; i++){

if(A[ i ]>A[ i+1] ){

if(count==0){j=i ;count++ ;break ; /* searching for first anomaly from index 1 */

}

}}

for(int i=n ; i>j-1 ;i--){

if(A[i]<A[i-1]){

if(count==1){ /* searching for first anomaly from index n */

k=i ; dn++ ; s.push_back(i); /* taking note of the first anomaly from the end i.e. k=i . this will be a valley so increasing the value of dn by 1 and also noting it's index in the vector*/

}

if(A[ i ]<A[ i+1] && count>1){

dn++ ; s.push_back(i); /* counting the number of valley's and noting their index in the vector */

}

count++; /* counting the number of anomaly */

}

if(A[ i ]>A[ i+1 ] && A[ i ]>A[ i-1]){

up++; s.push_back(i); /* counting the number of peaks and noting their index in the vector*/

}

if(count==0){cout<<"yes";} /* if no anomaly */

else if(n==2){

if(A[1]>A[2])cout<<"yes"<<endl<<"swap "<<1<<" "<<2;

/* if n=2 than we can directly compare the values and output accordingly */

}

else if(A[ j ]<A[ k+1] && A[ k]>A[ j-1] && ((s.size()==4 &&s[0]-s[1]==1 && s[2]-s[3]==1)|| (s.size()==2 && s[0]-s[1]==1)) ) {

cout<<"yes"<<endl<<"swap "<<j<<" "<<k;

/* this is a very big condition so take a look properly, remember that j is the first anomaly from beginning and k is the first anomaly from the end. After swap, the array will be sorted only when A[ j ]<A[ k+1] && A[ k]>A[ j-1] and i have already explained the other conditions in the points above */

}

else if(A[ j ]<A[k+1] && A[k]>A[ j-1] && count==(k-j+1))

cout<<"yes"<<endl<<"reverse "<<j<<" "<<k;

/* Reverse operation will be applicable only when number of anomaly i.e. count is equal to the difference in their index +1 i.e. ( count =k-j+1 ), see the sample input's for more clarification */

else cout<<"no"; /* if all the above are not true than we cannot sort the array in one operation */

return 0;

}

*****

If you have a better solution in mind than please do share it in the comment section below

Want me to explain any particular question, than comment below

*****

Question source : hackerrank.com

Bigger is Greater

noreply@blogger.com (Dinesh) — Mon, 12 Sep 2016 19:06:00 +0000

In this problem i will explain the following problem taken from hackerrank.com

Lexicographically greater means that suppose if we were to arrange these words on a dictionary than s should come just after w.

We will use the word "mekhfa" in our example.

The key observation in this algorithm is that when we want to compute the next word in a dictionary "s" such that it contains all the letters as "w" OR equivalently when we want to compute the next permutation of the word "w", we must “increase” the sequence as little as possible. Just like when we count up using numbers, we try to modify the rightmost elements and leave the left side alone (ex. if we want to fin the next permutation of the number 234 we would start from the right most element rather than the first element).

Similarly here also we will start from the end and find the largest sub-string that is non-increasing, non increasing means string[i-1] > string[ i ], in our case it's

This sub-string is already in the highest permutation, so we can’t make a next permutation just by modifying it – we need to modify some element(s) to the left of it.

Now, look at the element immediately to the left of the index of "k" (in the example it’s "e") and call it the pivot. (If there is no such element – i.e. the entire sequence is non-decreasing – then this is already the last permutation.) The pivot is necessarily less than the head of the sub-string (in the example it’s "k"). So some element in the sub-string is greater than the pivot. If we swap the pivot with the smallest element in the sub-string that is greater than the pivot ("f" in our case), then the beginning (i.e. m, f ) of the string is minimized. (The string is everything in the sequence except for the new sub-string. i.e.

(Note that if the sub-string has multiple copies of the new pivot, we should take the rightmost copy – this plays into the next step.)

Finally, we sort the sub-string in non-decreasing (i.e. weakly increasing) order because we increased the prefix, so we want to make the new suffix as low as possible. In fact, we can avoid sorting and simply reverse the suffix, because the replaced element respects the weakly decreasing order. So finally, we get the sequence

which is the next permutation that we wanted.

Here are the steps.

Start from the end and find the index i such that string[ i ] < string[ i +1].
The element at index i (i.e. string[ i ] ) is called pivot. Now Search the elements with index > i and find the element which is next greater than string[ i ] . Let say we find the element at index j to be next greater than string[ i ] .
Swap string [ j ] and string[ i ].
Reverse Or sort the sub-string starting at string[ i+1] .

Here is my code for reference.

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int t;

cin>>t;

for (int i = 0; i < t; i++){

string s;

cin >> s;

int n = s.length();

int j, k;

for (j = n - 2; j >= 0; j--) { /* initializing j which is pointing to element at index n-2 */

for (k = n - 1; k > j && s[k] <= s[j]; k--); /* finding the largest non-increasing sub-string */

if (k == j) continue;

char tmp = s[k];

s[k] = s[j];

s[j] = tmp; /* swaping the elements */

sort(s.begin() + j + 1, s.end()); /* sorting the sub-string */

break;

}

if (j < 0) cout << "no answer" << endl; /* if no permutation exist than this will get executed */

else cout << s << endl; /* if permutation exist than print it */

}

return 0;

}

*****

IF YOU WANT ME TO EXPLAIN A PERTICULAR PROBLEM THAN PLEASE LEAVE A LINK TO THE PROBLEM IN THE COMMENT SECTION

*****

Kangaroo

noreply@blogger.com (Dinesh) — Mon, 12 Sep 2016 09:15:00 +0000

There are two kangaroos on an x-axis ready to jump in the positive direction (i.e, toward positive infinity). The first kangaroo starts at location and moves at a rate of meters per jump. The second kangaroo starts at location and moves at a rate of meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they'll ever land at the same location at the same time?

Input Format

A single line of four space-separated integers denoting the respective values of , , , and .

Constraints

0<= x1 < x2 <= 10000

1 <= x1 <= 10000

1<= v2 <= 10000

Output Format

Print `YES` if they can land on the same location at the same time; otherwise, print `NO`.

MY EXPLANATION:

This is a simple high school maths problem like 2 trains start at different location,given their velocity can you find whether they will ever meet or not?

Let's name the kangaroo's as K1 and K2 and given K2 starts ahead of K1 (i.e. x2 > x1).

Now, they will meet only when distance traveled by K1 is equal to the sum of distance traveled by K2 and their initial separation(i.e. (x1-x2) + distance(K2) ). This is visualized below.

let say they meet after time T then the condition will be

**v1T = (x2 - x1) + v2T

In other word, they will meet if

T = ( x2 - x1 ) % ( v1 - v2 ) is equal to 0** ( zero)

Now try to write your own code keeping these things in mind.

If you don't succeed than take a look at my solution.

#include <iostream>

using namespace std;

int main(){

int x1, x2, v1, v2; /* Initializing variables */

cin >> x1 >> v1 >> x2 >> v2; /* assigining values to the variables */

if( v1>v2 && (x2-x1)%(v1-v2)==0 )cout<<"YES"; /* if this is the case than they will meet , so print YES */

else cout<<"NO"; /* In any other case they wont meet */

return 0;

}

Question Source: hackerrank.com

Lisa's Workbook

noreply@blogger.com (Dinesh) — Sat, 10 Sep 2016 09:30:00 +0000

In this post i will explain the solution of the following problem at hackerrank.com.

Here is the problem statement.

This problem looks difficult at the first sight but it's not too difficult if you go step by step.

Create a loop which runs through the chapters.
Inside that loop create another loop which runs through all the problems in that particular chapter and checks whether the problem number is equal to chapter number or not.

AN ADVICE : Try writing a code before reading further.Keep in mind the above 2 steps. If you don't succeed than come back here and read further.
First of all initialize two int variables to keep track of the page number and the number of special problem,i have initialized pagenum and spb as these two variables.Initialize another three variables for the number of chapters, maximum number of problems per page and the number of problems per chapter.
Take the inputs i.e. the number of chapters and the maximum number of problems per chapter. Now create a loop which runs through the chapters.
Now take another input which will be the number of problems per chapter. After that create another loop which will run through the problems in a particular chapter and check whether the problem number is equal to the page number or not. If equal than increase the variable spb by 1, if not than continue. Take a look at my solution.
Hope it helped you :)

#include <iostream>
using namespace std;
int main() {
int n,k,pagenum=1,spb=0, numprob;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>numprob;

for(int j=1; j&lt =numprob; j++){ /* looping through the problems. */
if( pagenum==j&nbsp)spb++; /*if problem number is equal to page number than increase spb.*/
if( j==numprob || j%k==0 ) pagenum++; /*if j reaches the problem number or j%k=0 then increase the page number.*/
}
}
cout<<spb; /*print the number of special problems.*/
return 0;
}

*****

IF YOU WANT ME TO EXPLAIN A PERTICULAR PROBLEM THAN PLEASE LEAVE A LINK TO THE PROBLEM IN THE COMMENT SECTION

*****

Absolute Permutation

noreply@blogger.com (Dinesh) — Sat, 10 Sep 2016 09:29:00 +0000

This is the most efficient solution of the Absolute Permutation question asked
at hackerrank.com .

Here is the question.

We define

to be a permutation of the first

natural numbers in the range

. Let

denote the position of

in permutation

(please use

-based indexing).

is considered to be an absolute permutation if

holds true for every

Given

and

, print the lexicographically smallest absolute permutation,

; if no absolute permutation exists, print -1.

Input Format

The first line of input contains a single integer,

, denoting the number of test cases.
Each of the

subsequent lines contains

space-separated integers describing the respective

and

values for a test case.

Constraints

Output Format

On a new line for each test case, print the lexicographically smallest absolute permutation; if no absolute permutation exists, print -1.

Key observations.

The value of k should be less than or equal to n/2 other wise abs(pos¡ -i) =k will not hold true for every i.
K should be a divisor of n (i.e.n%k=0) .Take a pen and a paper and experiment with different k (divisor and non-divisor of n). It's better for you if you try it yourself.
The quotient of n/k should be divisible by 2. (i.e. (n/k)%2=0) Again think!!

If you still didn't get this than a detailed explanation is there at the end of this post.I have not given the full explanation here since i want you all to try with these hint's first.

That's it . That was all the hidden tricks that was there in this problem.

Here is my code.

#include <iostream>
#include <vector>
using namespace std;
int main(){
int t,n,k,dev;
cin >> t;
for(int a0 = 0; a0 < t; a0++){
cin >> n >> k;
dev=n/k;
vector<int> pos(n);
if(k==0){ //if k=0 print the array itself without manipulating any thing
for(int i=1;i<=n;i++)cout<<i<<" ";
}
else if ((k<=n/2)&&(n%k==0)&&(dev%2 ==0)){ //else if k<=n/2 and n%k==0 and (n/k)%2==0 than do this
for(int i=0;i<n;i++){
if((i/k)%2 == 0) pos[i] = i + k+1;
else pos[i] = i - k+1;
}
for (int i = 0; i< n; i++) cout << pos[i] << " ";
}
else cout << "-1";
cout <<endl;
}
return 0;
}

Here is the complete explanation in case someone is still struggling.

Note: k<=n/2 is very apparent so I have not discussed that here.

Please forgive me for explaining this in paper since I don't have enough time to type it in my computer.

*****

IF YOU WANT ME TO EXPLAIN A PERTICULAR PROBLEM THAN PLEASE LEAVE A LINK TO THE PROBLEM IN THE COMMENT SECTION

*****

Circular Array Rotation

noreply@blogger.com (Dinesh) — Sat, 10 Sep 2016 09:24:00 +0000

In this post i will explain the Circular array rotation problem in the most efficient way. Here is the problem statement taken directly from hackerrank.com.

Here is the trick. We will consider 2 cases, 1st is when k<m and 2nd is when k>m, you will get to know why we are considering these two cases as we go on.

Let the input parameters be n, k=4 and m=5, so the numbers would be (1,2,3,4,5,6,7,8,9...n-1,n) keep note of the number at index m-k (i.e. at index 1). Now after k=4 rotations the resulting numbers will be (n-3,n-2,n-1,n,1,2,3,4 ...n-5,n-4). Note that the current number at index m=5(which in this case is 2) was at an index 1 (i.e. at m-k). So we can directly find the element at index m=5 without actually rotating the array by outputting the element at index (m-k).
Now let k=4 and m=3. In this case the number that is at index m=3 was actually at an index (n-k+m). Here also we can find the element at m=3 without rotating the array by outputting the element at index (n-k+m).

In case you are wondering what about the case when k>n well we can tackle that by using the mod(%) operator.For those of you who do not know how mod(%) operator works. Basically it returns the remainder, let k=r%n, so if rotation(i.e. r) is greater than n, due to the mod(%) operator the value of k will be remainder of r/n. e.x. if r=9, n=6 than k=3 and if r is multiple of n i.e. if r=5,10,15,20..... and n=5 than k=0 after the operation.
Here is my code.

#include <iostream>
using namespace std;
int main() {
int n,k,q,m,j;
cin>>n>>k>>q;
k%=n; /* Or k=k%n which will make sure that the rotation is in circular manner. The mod(%) operator returns the remainder so if rotation(i.e. k) is greater than n, due to the mod(%) operator the value of k will be remainder of k/n. e.x. if k=9, n=6 than k=3 after this operation and if k is multiple of n i.e. if k=5,10,15,20..... and n=5 than k=0 after the operation. */
int *A= new int[n] /* OR int A[n] ---initializing an array A of size n . To know more about the format and it's use search for dynamic array */
for(int i=0;i<n;i++) cin>>A[i]; /* filling the array */
for(int i=0;i<q;i++){
cin>>m; /* taking the index */
j=m-k;
if(j<0) cout<<A[n+j]<<endl; /* the case when k>m. The output is A[n+j] which is nothing but A[n+m-k]. */
else cout<<A[j]<<endl; /* the case when k<m. The output is A[j] which is nothing but A[m-k]. */
}
return 0;
};

*****IF YOU WANT ME TO EXPLAIN A PERTICULAR PROBLEM THAN PLEASE LEAVE A LINK TO THE PROBLEM IN THE COMMENT*****

Gotitt

Strange Counter

#include <iostream>using namespace std;

int main(){

long long t,n=2;

cin >> t;

**while(3(n-1)<t)n=2;**

**cout<<3*(n-1)-t+1<<endl;**

return 0;

}

Almost Sorted

Here are my tips.

Bigger is Greater

In this problem i will explain the following problem taken from hackerrank.com

Kangaroo

#include <iostream>

using namespace std;

int main(){

int x1, x2, v1, v2; / Initializing variables /

cin >> x1 >> v1 >> x2 >> v2; / assigining values to the variables /

if( v1>v2 && (x2-x1)%(v1-v2)==0 )cout<<"YES"; / if this is the case than they will meet , so print* YES */

else cout<<"NO"; / In any other case they wont meet /

return 0;

}

Lisa's Workbook

In this post i will explain the solution of the following problem at hackerrank.com.

Absolute Permutation

Circular Array Rotation

In this post i will explain the Circular array rotation problem in the most efficient way. Here is the problem statement taken directly from hackerrank.com.

Gotitt

Strange Counter

#include <iostream>using namespace std;

int main(){

long long t,n=2;

cin >> t;

while(3*(n-1)<t)n*=2;

cout<<3*(n-1)-t+1<<endl;

return 0;

}

Almost Sorted

Here are my tips.

Bigger is Greater

In this problem i will explain the following problem taken from hackerrank.com

Kangaroo

#include <iostream>

using namespace std;

int main(){

int x1, x2, v1, v2; /* Initializing variables */

cin >> x1 >> v1 >> x2 >> v2; /* assigining values to the variables */

if( v1>v2 && (x2-x1)%(v1-v2)==0 )cout<<"YES"; /* if this is the case than they will meet , so print YES */

else cout<<"NO"; /* In any other case they wont meet */

return 0;

}

Lisa's Workbook

In this post i will explain the solution of the following problem at hackerrank.com.

Absolute Permutation

Circular Array Rotation

In this post i will explain the Circular array rotation problem in the most efficient way. Here is the problem statement taken directly from hackerrank.com.

**while(3(n-1)<t)n=2;**

**cout<<3*(n-1)-t+1<<endl;**

int x1, x2, v1, v2; / Initializing variables /

cin >> x1 >> v1 >> x2 >> v2; / assigining values to the variables /

if( v1>v2 && (x2-x1)%(v1-v2)==0 )cout<<"YES"; / if this is the case than they will meet , so print* YES */

else cout<<"NO"; / In any other case they wont meet /