Strange Counter

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

Read More

Almost Sorted

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

1. Swap two elements.
2. 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 

1. If the array is already sorted, output yes on the first line. You do not need to output anything else.
2. 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 can sort the array by swapping  and , output swap l r in the second line.  and  are the indices of the elements to be swapped, assuming that the array is indexed from  to .
   •   Else if it is possible to sort the array by reversing the segment d [l....r] , output reverse l r in the second line. l and r are the indices of the first and last elements of the sub-sequence to be reversed, assuming that the array is indexed from 1 to n.
   •  represents the sub-sequence of the array, beginning at index  and ending at index , both inclusive.  d [l....r] represents the sub-sequence of the array, beginning at index l and ending at index r , both inclusive.
   • If an array can be sorted by either swapping or reversing, stick to the swap-based method.
3. If you cannot sort the array in either of the above ways, output no in the first line

Here are my tips.

1. 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.
2. 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.
3. 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.
4. Now if the output is yes than the following will be true.
   1. if no anomaly than the array is already sorted.
   2. swap when the there are exactly 1 peak and 1 valley  OR 2 peaks and 2 valleys and difference between the consecutive index of a peak and a valley is 1.
   3. reverse when only 1 peak and 1 valley and the difference between the their index is not 1.
5.  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:

6

1 5 4 3 2 6

Output : reverse 2 5

Input

9

1 2 9 4 5 6 7 8 3

Output: swap 3 9

Input

9

1 2 9 4 5 8 7 6 3

Output: no

Input:

10

1 2 10 4 5 8 7 6 9 3

Output: no

Input

5

1 2 4 3 5

Output: swap 2 5

Read More

Bigger is Greater

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.

m

e

k

h

f

a

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  

k

h

f

a

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.

k

h

e

a

 (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 

m

f

a

e

h

k

which is the next permutation that we wanted.

Here are the steps.

1. Start from the end and find the index i such that string[ i ] < string[ i +1].
2. 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 ] .
3. Swap string [ j ] and string[ i ].
4. 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

*****

Read More

Kangaroo

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

            v1*T = (x2 - x1) + v2*T

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 

Read More