tag:blogger.com,1999:blog-48661595999097873792024-02-08T04:31:16.375-08:00Spoj SolutionsBlog for beginners... whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.comBlogger113125tag:blogger.com,1999:blog-4866159599909787379.post-81836806560642726142015-08-22T03:33:00.001-07:002015-08-22T03:38:30.745-07:00Finding largest rectangle in a given matrix when swapping of columns is possible <div dir="ltr" style="text-align: left;" trbidi="on">
you are given a matrix with 0 and 1's. you have to find the largest rectangle in the matrix such that you can swap columns<br />
with any other column.<br />
Ex- 0 1 0 1 0<br />
0 1 0 1 1<br />
1 1 0 1 0<br />
the largest rectangle's area is 6 in this case because we can swap column 2 with column 3 so<br />
the matrix after swapping will be<br />
0 0 1 1 0<br />
0 0 1 1 1<br />
1 0 1 1 0<br />
<br />
<h4 style="text-align: left;">
Solution - </h4>
step 1 - first of all we have to calculate no of consecutive 1's in any particular column so we will take a 2D array<br />
to store them<br />
so for this the values in array will be<br />
0 1 0 1 0<br />
0 2 0 2 1<br />
1 3 0 3 0<br />
so the mechanism of filling the array will<br />
ar[i][j] = ar[i-1][j]+1 if i>0 && a[i][j]==1<br />
= 1 if i==0 && a[i][j]=1<br />
= 0 else<br />
<br />
step 2 - we will sort the rows in decreasing fashion<br />
so after sorting step the matrix will be<br />
1 1 0 0 0<br />
2 2 1 0 0<br />
3 3 1 0 0<br />
<br />
step 3 - now we will traverse each row and check for the max area<br />
<br />
#include<bits/stdc++.h><br />
using namespace std;<br />
<div class="line number14 index13 alt1 highlighted" style="background: none rgb(224, 224, 224) !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp comments" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 130, 0) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
int n;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
int rect(int a[][100]){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>int i,j;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>int ar[n+1][n+1];</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>//constructing the histogram</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<n;i++){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[0][i]=a[0][i]; // if we are in the first row</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(j=1;j<n;j++){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(a[j][i]==0){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[j][i]=0;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}else{</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[j][i]=ar[j-1][i]+1;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>int k;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>//sorting rows</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>//using count sort for better time complexity</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<n;i++){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>int br[n+1]={0},x=0;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(j=0;j<n;j++){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>br[ar[i][j]]++; // counting occurrence</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(j=n;j>=0;j--){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(br[j]>0){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(k=0;k<br[j];k++){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[i][x]=j;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>x++;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>//checking for the maximum value</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>int x;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>int max=0;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<n;i++){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(j=0;j<n;j++){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>x=(j+1)*ar[i][j];</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(x>max){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>max=x;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>return max;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
int main(){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>int b,c,d,i,j,a[100][100];</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&n);</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<n;i++){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(j=0;j<n;j++){</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&a[i][j]);</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("area of the biggest rectangle is = %d\n",rect(a));</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;</div>
<div style="color: black; font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
}</div>
</code></div>
<div class="line number15 index14 alt2 highlighted" style="background: none rgb(224, 224, 224) !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code></div>
<br />
<br />
Time complexity = O(n^2) if we use count sort for sorting rows otherwise it will be O(n^2*log(n)).<br />
Extra space = O(n^2)<br />
<br />
<br />
<br />
<br />
<br /></div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-61749241399024728442015-08-21T20:14:00.000-07:002015-08-21T20:19:57.596-07:00Minimum number of jumps to reach end<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; vertical-align: baseline;">
Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). <span id="more-13209" style="border: 0px; margin: 0px; padding: 0px; vertical-align: baseline;"></span>If an element is 0, then cannot move through that element.</div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; vertical-align: baseline;">
Example:</div>
<pre style="background-color: #e0e0e0; border-radius: 10px; border: 1px solid rgb(237, 237, 237); font-family: Consolas, Monaco, 'Lucida Console', monospace; font-size: 12px; line-height: 1.514285714; margin-bottom: 10px; overflow: auto; padding: 10px; vertical-align: baseline;">Input: arr[] = {1, 2, 5, 7, 6, 2, 6, 3, 2, 8, 9}
Output: 3 (1-> 2 -> 7 ->9)
</pre>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; vertical-align: baseline;">
First element is 1, so can only go to 2. Second element is 2, so can make at most 2 steps eg to 5 or 7.</div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; text-align: left; vertical-align: baseline;">
<span style="color: #cc0000;">Solution</span> - we can do it with several methods.</div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; text-align: left; vertical-align: baseline;">
(1) recursion (2) DP</div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; text-align: left; vertical-align: baseline;">
here i'll only discuss the dynamic programming approach</div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; text-align: left; vertical-align: baseline;">
(1) Time - O(n^2) & Space - O(n)</div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; text-align: left; vertical-align: baseline;">
<span style="line-height: 22.2857151031494px;">In this method, we will maintain an array from left to right such that the array contains information about minimum number of jumps needed to reach ar[i] from ar[0]. So the nth element of the new array will have the information about minimum number of steps to reach the end.</span></div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; text-align: left; vertical-align: baseline;">
<span style="line-height: 22.2857151031494px;">#include<bits/stdc++.h> </span><span style="line-height: 22.2857151031494px;">using namespace std;</span></div>
<div class="line number35 index34 alt2" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp color1 bold" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"></code><br />
<div class="line number6 index5 alt1 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp color1 bold" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><code class="cpp comments" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 130, 0) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">// Returns minimum number of jumps to reach nth step from the first</code></code></div>
<code class="cpp color1 bold" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
</code>
<br />
<div class="line number7 index6 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp color1 bold" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><code class="cpp color1 bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: gray !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">int</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">minjumps(</code><code class="cpp color1 bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: gray !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">int</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">ar[], </code><code class="cpp color1 bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: gray !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">int</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">n)</code><span style="background-color: initial; color: black; font-size: 1em; line-height: 1.1em;">{</span></code></div>
<code class="cpp color1 bold" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
</code>
<div class="line number9 index8 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp color1 bold" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><span style="color: #757575;"> </span><span style="color: grey;"><b>int jump[n+2];</b></span></code><code class="cpp plain" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp comments" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 130, 0) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">// jump[n-1] will hold the result</code></code></div>
<code class="cpp color1 bold" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<div class="line number9 index8 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp comments" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 130, 0) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"></code><code class="cpp keyword bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> if</code><span style="color: #757575; font-size: 1em; line-height: 14.3000001907349px;"> </span><code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">(n == 0 || ar[0] == 0) //<span style="color: #38761d;">impossible situation</span></code></div>
<div class="line number13 index12 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp keyword bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">return</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">INT_MAX;</code></div>
<div class="line number14 index13 alt1 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp color1 bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: gray !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> int</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">i,j;</code></div>
<div class="line number11 index10 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<span style="color: #757575;"></span><span style="color: #444444;"> for(i=0;i<n;i++)</span></div>
<div class="line number11 index10 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<span style="color: #444444;"> jump[i]=INT_MAX;</span></div>
<div class="line number15 index14 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp plain" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">jump[0] = 0; </code><code class="cpp plain" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><span style="color: #38761d;">//no of step to reach the first step</span></code></div>
<div class="line number16 index15 alt1 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
// Find the minimum number of jumps to reach arr[i]</div>
<div class="line number18 index17 alt1 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp comments" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 130, 0) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">// from arr[0], and assign this value to jumps[i]</code></div>
<div class="line number19 index18 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp keyword bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">for</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">(i = 0; i < n; i++)</code><span style="background-color: initial; color: black; font-size: 1em; line-height: 1.1em;">{</span></div>
<div class="line number22 index21 alt1 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp keyword bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">for</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">(j = 1; j <= ar[i] && i+j<n; j++)</code><span style="background-color: initial; color: black; font-size: 1em; line-height: 1.1em;">{</span></div>
<div class="line number24 index23 alt1 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><span style="color: #757575;"> </span><span style="color: #006699;"><b>jump[i+j]=min(jump[i+j],jump[i]+1);</b></span></code></div>
<div class="line number29 index28 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">}</code></div>
<div class="line number30 index29 alt1 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">}</code></div>
<div class="line number31 index30 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp keyword bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">return</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">jump[n-1];</code></div>
<div class="line number32 index31 alt1 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-weight: normal; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">}</code></div>
</code></div>
<div class="line number35 index34 alt2" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp color1 bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: gray !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">int</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">main()</code></div>
<div class="line number36 index35 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">{</code></div>
<div class="line number37 index36 alt2" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><span style="color: #757575;"> </span><b>int ar[100000],n,i,j;</b></code></div>
<div class="line number38 index37 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> <b>scanf("%d",&n);</b></code></div>
<div class="line number38 index37 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><b> for(i = 0; i < n; i++){</b></code></div>
<div class="line number38 index37 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><b> scanf("%d",&ar[i]);</b></code></div>
<div class="line number38 index37 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><b> }</b></code></div>
<div class="line number39 index38 alt2" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp functions bold" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">printf</code><code class="cpp plain" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">(</code><code class="cpp string" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: blue !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">"Minimum number of jumps to reach end is %d "</code><code class="cpp plain" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">, minjumps(ar,n));</code></div>
<div class="line number40 index39 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp keyword bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">return</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">0;</code></div>
<div class="line number41 index40 alt2" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">}</code></div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; text-align: left; vertical-align: baseline;">
<br /></div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; vertical-align: baseline;">
(2) Time - O(n) & Space - O(n) - </div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; vertical-align: baseline;">
<span style="color: #3f4549; font-family: 'Helvetica Neue', arial, sans-serif; font-size: 15px; line-height: 21px;">basically i used the information that if we updated an index once then we don't need to update that for further numbers, because whatever we'll try we can't get less steps then that.</span></div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; vertical-align: baseline;">
<span style="color: #3f4549; font-family: 'Helvetica Neue', arial, sans-serif; font-size: 15px; line-height: 21px;">#include<bits/stdc++.h> </span><span style="color: #3f4549; font-family: 'Helvetica Neue', arial, sans-serif; font-size: 15px; line-height: 21px;">using namespace std;</span></div>
<div class="line number6 index5 alt1 highlighted" style="background: none rgb(224, 224, 224) !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp comments" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 130, 0) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">// Returns minimum number of jumps to reach nth step from first</code></div>
<div class="line number7 index6 alt2 highlighted" style="background: none rgb(224, 224, 224) !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp color1 bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: gray !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">int</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">minjumps(</code><code class="cpp color1 bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: gray !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">int</code> a<code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">r[], </code><code class="cpp color1 bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: gray !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">int</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">n)</code><span style="background-color: initial; color: black; font-size: 1em; line-height: 1.1em;">{</span></div>
<div class="line number9 index8 alt2 highlighted" style="background: none rgb(224, 224, 224) !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><span style="color: grey;"><b>int jump[n+2];</b></span></code><code class="cpp plain" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp comments" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 130, 0) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">// jump[n-1] will hold the result</code></div>
<div class="line number9 index8 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre; width: auto !important;">
<code class="cpp comments" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 130, 0) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"></code><code class="cpp keyword bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> if</code><span style="color: #757575; font-size: 1em; line-height: 14.3000001907349px;"> </span><code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">(n == 0 || ar[0] == 0) //<span style="color: #38761d;">impossible situation</span></code></div>
<div class="line number13 index12 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp keyword bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">return</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">INT_MAX;</code></div>
<div class="line number14 index13 alt1 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre; width: auto !important;">
<code class="cpp color1 bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: gray !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><span style="font-family: Times New Roman;"> </span>int</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">i,j;</code></div>
<div class="line number15 index14 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp plain" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">jump[0] = 0; </code><code class="cpp plain" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><span style="color: #38761d;">//no of step to reach the first step</span></code></div>
<div class="line number18 index17 alt1 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp comments" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 130, 0) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">// from arr[0], and assign this value to jumps[i] </code></div>
<div class="line number19 index18 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre; width: auto !important;"> </code><span style="background-color: transparent; font-size: 13px; line-height: 14.3000001907349px; white-space: pre;"><span style="font-family: Consolas, Bitstream Vera Sans Mono, Courier New, Courier, monospace;"><b><span style="color: #444444;">int k=0; </span><span style="color: #38761d;">//this will avoid repeat</span><span style="color: #444444;">
for (i = 0; i < n; i++){
for (j = k+1; j <= i+ar[i] && j<n; j++)
{
jump[j]=jump[i]+1;
}
k=max(k,i+ar[i]);
}</span></b></span></span></div>
<div class="line number31 index30 alt2 highlighted" style="background-attachment: initial !important; background-clip: initial !important; background-color: rgb(224, 224, 224) !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp keyword bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">return</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">jump[n-1];</code></div>
<div class="line number32 index31 alt1 highlighted" style="background: none rgb(224, 224, 224) !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">}</code></div>
<div class="line number35 index34 alt2" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp color1 bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: gray !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">int</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">main()</code></div>
<div class="line number36 index35 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">{</code></div>
<div class="line number37 index36 alt2" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><span style="color: #757575;"> </span><b>int ar[100000],n,i,j;</b></code></div>
<div class="line number38 index37 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> <b>scanf("%d",&n);</b></code></div>
<div class="line number38 index37 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><b> for(i = 0; i < n; i++){</b></code></div>
<div class="line number38 index37 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><b> scanf("%d",&ar[i]);</b></code></div>
<div class="line number38 index37 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><b> }</b></code></div>
<div class="line number39 index38 alt2" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp functions bold" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">printf</code><code class="cpp plain" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">(</code><code class="cpp string" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: blue !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">"Minimum number of jumps to reach end is %d "</code><code class="cpp plain" style="background-attachment: initial !important; background-clip: initial !important; background-color: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-image-outset: initial !important; border-image-repeat: initial !important; border-image-slice: initial !important; border-image-source: initial !important; border-image-width: initial !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">, minjumps(ar,n));</code></div>
<div class="line number40 index39 alt1" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp spaces" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="cpp keyword bold" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; font-weight: bold !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">return</code> <code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">0;</code></div>
<div class="line number41 index40 alt2" style="background: none white !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<code class="cpp plain" style="background: none !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: black !important; direction: ltr !important; display: inline !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 1em !important; height: auto !important; left: auto !important; line-height: 1.1em !important; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">}</code></div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; vertical-align: baseline;">
<span style="color: #3f4549; font-family: 'Helvetica Neue', arial, sans-serif; font-size: 15px; line-height: 21px;"><br /></span></div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; vertical-align: baseline;">
<span style="color: #3f4549; font-family: 'Helvetica Neue', arial, sans-serif; font-size: 15px; line-height: 21px;"><br /></span></div>
<div style="background-color: white; border: 0px; font-family: 'Open Sans', Helvetica, Arial, Verdana, sans-serif; font-size: 13px; line-height: 1.714285714; margin-bottom: 10px; padding: 0px; vertical-align: baseline;">
<span style="color: #3f4549; font-family: 'Helvetica Neue', arial, sans-serif; font-size: 15px; line-height: 21px;"><br /></span></div>
<div class="line number6 index5 alt1 highlighted" style="background: none rgb(224, 224, 224) !important; border-radius: 0px !important; border: 0px !important; bottom: auto !important; box-shadow: none !important; box-sizing: content-box !important; color: #757575; direction: ltr !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace; font-size: 13px; height: auto !important; left: auto !important; line-height: 14.3000001907349px; margin: 0px !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0em !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre !important; width: auto !important;">
<br /></div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-61057062814557936392015-06-09T09:54:00.000-07:002015-06-09T09:54:01.915-07:00Amusing numbers<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/TSHOW1/" target="_blank">problem statement is here</a></h3>
<br />
#include<stdio.h><br />
#include<math.h><br />
<br />
int main()<br />
{<br />
long long int a,t,i,j,n,b;<br />
scanf("%lld",&t);<br />
while(t--){<br />
scanf("%lld",&a);<br />
for(i=1; ;i++){<br />
if(a>(pow(2,i)-2) && a<=(pow(2,i+1)-2)){<br />
b=a-(pow(2,i)-2);<br />
break;<br />
}<br />
}<br />
n=i;<br />
for(j=1;j<=n;j++){<br />
if(b>pow(2,i-1)){<br />
printf("6");<br />
b=b-pow(2,i-1);<br />
}else{<br />
printf("5");<br />
}<br />
i--;<br />
}<br />
printf("\n");<br />
}<br />
return 0;<br />
}<br />
<div>
<br /></div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-54384200855154474762015-06-09T09:52:00.002-07:002015-06-09T09:52:25.581-07:00Playing with isosceles triangle<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/TRIISO/" target="_blank">problem statement is here</a></h3>
<br />
#include<stdio.h><br />
#include<math.h><br />
int main() {<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>long int n,t,s,flag,i,c;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%ld", &t);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(t--) {<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%ld",&s);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>flag=0;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(s%2==0){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(s%2==0)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>s=s/2;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>n=(sqrt(s));<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=3;i<=n;i+=2){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(s%i==0){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(i%4==1)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>flag = 1;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(s%i==0)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>s=s/i;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(s==1)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>break;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(s!=1&&s%4==1)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>flag=1;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(flag==0){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("NO\n");<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>} else {<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("YES\n");<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;<br />
}<br />
<br />
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-42012609038366051272015-06-09T09:48:00.000-07:002015-06-09T09:48:02.517-07:00Counting Triangles<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/TRICOUNT/" target="_blank">problem statement is here</a></h3>
<br />
<br />
#include<stdio.h><br />
int main(){<br />
long long int totel,x,y;<br />
scanf("%lld",&x);<br />
while(x--){<br />
scanf("%lld",&y);<br />
totel=(y*(y+2)*(2*y+1))/8;<br />
printf("%lld\n",totel);<br />
}<br />
return 0;<br />
}<br />
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-45199049927470343392015-06-09T09:46:00.001-07:002015-06-09T09:46:24.756-07:00Traversing Grid<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/TRGRID/" target="_blank">problem statement is here</a></h3>
<br />
<br />
#include<stdio.h><br />
int main(){<br />
long long int n,m;<br />
int t;<br />
scanf("%d",&t);<br />
while(t--){<br />
scanf("%lld %lld",&n,&m);<br />
if(n%2==0 && m%2==0){<br />
if(n>m){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("U\n");<span class="Apple-tab-span" style="white-space: pre;"> </span><br />
}else if(m>=n)<br />
printf("L\n");<br />
}<br />
else if(n%2!=0 && m%2!=0){<br />
if(n>m)<br />
printf("D\n");<br />
else if(m>=n)<br />
printf("R\n");<br />
}<br />
else{<br />
if(n%2==0 && m%2!=0)<br />
{<br />
if(n>m)<br />
printf("D\n");<br />
else<br />
printf("L\n");<br />
}<br />
if(n%2!=0 && m%2==0)<br />
{<br />
if(n<m)<br />
printf("R\n");<br />
else<br />
printf("U\n");<br />
}<br />
}<br />
}<br />
return 0;<br />
}<br />
<div>
<br /></div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-86492587767359120352015-06-09T09:43:00.003-07:002015-06-09T09:43:43.703-07:00To and Fro<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/TOANDFRO/" target="_blank">problem statement is here</a></h3>
<br />
<br />
#include<stdio.h><br />
#include<string.h><br />
<br />
int main()<br />
{<br />
int a,i,j,n,b,k;<br />
char ar[210];<br />
while(1){ <br />
scanf("%d",&a);<br />
if(a==0)<br />
break;<br />
else{<br />
scanf("%s",ar);<br />
b=strlen(ar);<br />
j=a;<br />
for(i=0;i<a;i++){<br />
printf("%c",ar[i]);<br />
for(k=2; ;k+=2){<br />
if((k*j-i-1)<b){<br />
printf("%c",ar[k*j-i-1]);<br />
}else{<br />
break;<br />
}<br />
if((k*j+i)<b){<br />
printf("%c",ar[k*j+i]);<br />
}else{<br />
break;<br />
}<br />
}<br />
}<br />
printf("\n");<br />
}<br />
}<br />
return 0;<br />
}<br />
<br />
<div>
<br /></div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-37988204944082067332015-06-09T09:34:00.000-07:002015-06-09T09:34:17.656-07:00Movie Theatre Madness<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/THEATRE/" target="_blank">problem statement is here</a></h3>
<br />
<br />
#include<stdio.h><br />
#include<iostream><br />
#include<algorithm><br />
#include<queue><br />
using namespace std;<br />
<br />
struct compare <br />
{ <br />
bool operator()(const long long & l, const long long & r) <br />
{ <br />
return l > r; <br />
} <br />
}; <br />
<br />
int main(){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>priority_queue<long long,vector<long long>, compare > pq;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>int n,i,a;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>long long ar[100005],max=1;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&n);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<n;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lld",&ar[i]);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<n;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>pq.push(ar[i]);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(1){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(pq.top()==ar[i]){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>break;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}else{<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>max=(max*(ar[i]))%1000000007;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>pq.pop();<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>max=max%1000000007;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("%lld\n",max);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span><br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;<br />
}<br />
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-20938207098986268892015-06-09T09:31:00.002-07:002015-06-09T09:31:35.981-07:00Finding the Tesserect<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/TESSER/" target="_blank">problem statement is here</a></h3>
<div>
<div>
#include<iostream></div>
<div>
#include<cstdio></div>
<div>
#include<cstring></div>
<div>
using namespace std;</div>
<div>
int main(){</div>
<div>
int t;</div>
<div>
scanf("%d\n",&t);</div>
<div>
while(t--)</div>
<div>
{</div>
<div>
int n,i;</div>
<div>
scanf("%d\n",&n);</div>
<div>
long long int a,b;</div>
<div>
scanf("%lld",&a);</div>
<div>
char ar[1000000],br[1000000];</div>
<div>
for(i=1;i<n;i++){</div>
<div>
scanf("%lld",&b);</div>
<div>
if(b>a){</div>
<div>
ar[i-1]='G';</div>
<div>
}else if(b==a){</div>
<div>
ar[i-1]='E';</div>
<div>
}else{</div>
<div>
ar[i-1]='L';</div>
<div>
}</div>
<div>
a=b;</div>
<div>
}</div>
<div>
ar[n]='\0';</div>
<div>
scanf("%s",br);</div>
<div>
if(strstr(ar,br))</div>
<div>
printf("YES\n");</div>
<div>
else</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("NO\n");</div>
<div>
}</div>
<div>
return 0;</div>
<div>
}</div>
</div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-23268084651224465942015-06-09T09:30:00.001-07:002015-06-09T09:30:08.932-07:00A Famous ICPC Team<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/TEAM2/" target="_blank">problem statement is here</a></h3>
<br />
#include<cstdio><br />
#include<algorithm><br />
using namespace std;<br />
int main()<br />
{<br />
long long int a[4],p;<br />
int j,i=1;<br />
while(scanf("%lld ",&a[0])!=EOF)<br />
{<br />
<br />
for(j=1;j<4;j++)<br />
{ <br />
scanf("%lld",&a[j]);<br />
<br />
}<br />
sort(a,a+4);<br />
p=a[3]+a[2];<br />
printf("Case %d: %lld\n",i,p);<br />
i++;<br />
}<br />
return 0;<br />
}<br />
<br />
<br />
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-28525922546594766982015-06-09T09:24:00.000-07:002015-06-09T09:24:47.808-07:00Balanced base-3<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/TAP2014B/" target="_blank">problem statement is here</a></h3>
<br />
#include<stdio.h><br />
int main() {<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>int t,y,z,n,ar[10000],i;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&t);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(t--){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&n);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>z=0;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(n){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[z]=n%3;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>z++;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>n/=3;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[z]=0;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<=z;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(ar[i]==2){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[i]=-1;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[i+1]++;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}else if(ar[i]==3){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[i]=0;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[i+1]++;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>y=0;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=z;i>=0;i--){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(ar[i]!=0){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>y=1;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(ar[i]==1)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("+");<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>else if(ar[i]==-1)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("-");<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>else if(y==1)<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("0");<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("\n");<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<span class="Apple-tab-span" style="white-space: pre;"> </span><br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;<br />
}<br />
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-86088761053177192062015-06-09T09:23:00.000-07:002015-06-09T09:23:02.335-07:00War<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/TAP2013G/" target="_blank">problem statement is here</a></h3>
<br />
#include<stdio.h><br />
#include<algorithm><br />
using namespace std;<br />
int main(){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>long long int s,ar[100009],br[100009],i,j,z,p,a;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lld",&s);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<s;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lld",&ar[i]);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<s;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lld",&br[i]);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>sort(ar,ar+s);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>sort(br,br+s);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>z=s-1;p=0;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=s-1;i>=0;i--){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(ar[i]<br[z]){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>p++;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>z--;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("%lld\n",p);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;<br />
}<br />
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-8017185267547630632015-06-09T09:21:00.000-07:002015-06-09T09:21:13.117-07:00WHAT A CO-ACCIDENT<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/SYNC13C/" target="_blank">problem statement is here</a></h3>
<br />
#include<stdio.h><br />
int main(){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>long long int a,b,t;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lld",&t);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(t--){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lld %lld",&a,&b);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(a%2==0 || b%2==0){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("Suresh\n");<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}else{<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("Ramesh\n");<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;<br />
}<br />
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-28765783730544437252015-01-24T07:09:00.001-08:002015-01-24T07:09:10.685-08:00Faridi and Yadav<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/CHOTU/" target="_blank">problem statement is here</a></h3>
<br />
#include<stdio.h><br />
#include<math.h><br />
<br />
int main(){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>double x,y,r,t;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lf",&t);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(t--){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lf%lf",&x,&y);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>r=2*(sqrt((x*x)-(y*y)));<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("%.3lf\n",r );<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;<br />
}<br />
<div>
<br /></div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-86929377251866619062015-01-24T07:08:00.000-08:002015-01-24T07:08:02.419-08:00Party<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/CFPARTY/" target="_blank">problem statement is here</a></h3>
<br />
#include <algorithm><br />
#include <cstdio><br />
using namespace std;<br />
<br />
int main() {<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>int t, n;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d", &t);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(t--) {<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d", &n);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("%d\n", max(0, n-2));<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;<br />
}<br />
<div>
<br /></div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-90642196562319768332015-01-24T07:03:00.002-08:002015-01-24T07:03:45.103-08:00Count on Cantor<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/CANTON/" target="_blank">problem statement is here</a></h3>
<br />
#include<stdio.h><br />
<br />
int main()<br />
{<br />
long long int t,a,b,c,i,j,k;<br />
scanf("%lld",&t);<br />
while(t--){<br />
scanf("%lld",&a);<br />
for(i=0; ;i++){<br />
if(((i*(i+1))/2)<a && a<=(((i+1)*(i+2))/2) ){<br />
b=a-((i*(i+1))/2);<br />
break;<br />
}<br />
}<br />
c=i+1;<br />
if(c%2==0){<br />
j=b;<br />
k=c+1-b;<br />
}else{<br />
j=c+1-b;<br />
k=b;<br />
}<br />
printf("TERM %lld IS %lld/%lld\n",a,j,k);<br />
}<br />
return 0;<br />
}<br />
<br /></div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-35000054102817806202015-01-24T07:01:00.000-08:002015-01-24T07:01:18.971-08:00Black Widow Rings<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/BWIDOW/" target="_blank">problem statement is here</a></h3>
<br />
#include<stdio.h><br />
int main(){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>long int max,t,n,ar[10000],br[10000],i,j,p,m;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%ld",&t);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(t--){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>max=0;m=0;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%ld",&n);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<n;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%ld %ld",&ar[i],&br[i]);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(ar[i]>max){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>max=ar[i];<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>p=i;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>br[p]=0;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<n;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(m<br[i]){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>m=br[i];<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(max>m){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("%ld\n",p+1);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}else{<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("-1\n");<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;<br />
}<br />
<div>
<br /></div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-69226775888266955492015-01-12T13:55:00.002-08:002015-01-12T13:55:59.333-08:00Pattern Find<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://problem%20statement%20is%20here/" target="_blank">problem statement is here</a></h3>
<div>
<br /></div>
<div>
it is a basic concept of KMP algorithm</div>
<div>
if u want to read about KMP algorithm u can find it <a href="http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/">here</a></div>
<div>
<br /></div>
<div>
<div>
#include<stdio.h></div>
<div>
#include<string.h></div>
<div>
#include<stdlib.h></div>
<div>
int zr[1000002],q;</div>
<div>
void computeLPSArray(char *pat, int M, int *lps){</div>
<div>
int len=0,i=1;</div>
<div>
lps[0]=0;</div>
<div>
while (i < M){</div>
<div>
if (pat[i] == pat[len]){</div>
<div>
len++;</div>
<div>
lps[i] = len;</div>
<div>
i++;</div>
<div>
}else{</div>
<div>
if (len != 0){</div>
<div>
len = lps[len-1];</div>
<div>
}else{</div>
<div>
lps[i] = 0;</div>
<div>
i++;</div>
<div>
}</div>
<div>
}</div>
<div>
}</div>
<div>
}</div>
<div>
void KMPSearch(char *pat, char *txt){</div>
<div>
int M = strlen(pat);</div>
<div>
int N = strlen(txt);</div>
<div>
int *lps = (int *)malloc(sizeof(int)*M);</div>
<div>
int j=0,i=0; </div>
<div>
computeLPSArray(pat, M, lps);</div>
<div>
while (i < N){</div>
<div>
if(pat[j] == txt[i]){</div>
<div>
j++;</div>
<div>
i++;</div>
<div>
}</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span> if (j == M){</div>
<div>
zr[q++]=i-j+1;</div>
<div>
j = lps[j-1];</div>
<div>
}else if (i < N && pat[j] != txt[i]){</div>
<div>
if (j != 0)</div>
<div>
j = lps[j-1];</div>
<div>
else</div>
<div>
i = i+1;</div>
<div>
}</div>
<div>
}</div>
<div>
free(lps);</div>
<div>
}</div>
<div>
int main(){</div>
<div>
int t,i;</div>
<div>
scanf("%d",&t);</div>
<div>
while(t--){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>q=0;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>char ar[1000006],br[1000005];</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%s %s",ar,br);</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>KMPSearch(br,ar);</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(q==0){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("Not Found\n");</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}else{</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("%d\n",q);</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<q;i++){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("%d ",zr[i]);</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("\n");</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div>
<br /></div>
<div>
}</div>
<div>
return 0;</div>
<div>
}</div>
</div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-32958631471448901792014-12-31T08:47:00.002-08:002014-12-31T08:47:37.129-08:00Playing with GCD<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/NAJPWG/" target="_blank">problem statement is here</a></h3>
<div>
<br /></div>
<div>
<div>
#include<stdio.h></div>
<div>
long long ar[100004];</div>
<div>
void etf(){</div>
<div>
long long k,i,z;</div>
<div>
ar[0]=0;</div>
<div>
for(k=1;k<100001;k++){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>long long n=k;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>long long r=n;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=2;i*i<=n;i++){ </div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>if (n%i==0) </div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>r-=r/i; </div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(n%i==0) </div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>n/=i; </div>
<div>
} </div>
<div>
if (n>1)</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>r-=r / n; </div>
<div>
z=k-r;</div>
<div>
ar[k]=ar[k-1]+z;</div>
<div>
} </div>
<div>
}</div>
<div>
int main(){</div>
<div>
long long t,num,c=1;</div>
<div>
etf();</div>
<div>
scanf("%lld",&t);</div>
<div>
while(t--){</div>
<div>
scanf("%lld",&num);</div>
<div>
printf("Case %lld: %lld\n",c,ar[num]);</div>
<div>
c++;</div>
<div>
}</div>
<div>
return 0;</div>
<div>
}</div>
</div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-16845714686147723432014-12-30T12:30:00.002-08:002014-12-30T12:30:53.347-08:00Game of chocolate<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/NAJGC/" target="_blank">problem statement is here</a></h3>
<div>
<br /></div>
<div>
<div>
#include<stdio.h></div>
<div>
long long gcd(long long a,long long b){</div>
<div>
if(b==0){</div>
<div>
return a;</div>
<div>
}</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>return gcd(b,a%b);</div>
<div>
}</div>
<div>
int main(){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>long long a,b,c,d,e,f,g,i,j,cc=1,t;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lld",&t);</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(t--){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lld %lld %lld %lld",&a,&b,&c,&d);</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>e=a*(c+1)+b*(d+1);</div>
<div>
f=(a+b)*(c+1+d);</div>
<div>
g=gcd(e,f);</div>
<div>
if(g>0){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>e/=g;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>f/=g;</div>
<div>
}</div>
<div>
if(e==0){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("Case %lld: 0\n",cc);</div>
<div>
}else{</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("Case %lld: %lld/%lld\n",cc,e,f);</div>
<div>
}</div>
<div>
cc++;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;</div>
<div>
}</div>
</div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-4279739347711452202014-12-30T12:01:00.003-08:002014-12-30T12:01:42.921-08:00Rivals<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/RIVALS/" target="_blank">problam statement is here</a></h3>
<div>
<br /></div>
<div>
<div>
#include<stdio.h></div>
<div>
#define MOD 1000000007</div>
<div>
<br /></div>
<div>
long long ar[2000010];</div>
<div>
void fact(){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>long long i;</div>
<div>
ar[0]=1;</div>
<div>
ar[1]=1;</div>
<div>
for(i=2;i<=2000000;i++)</div>
<div>
ar[i]=(ar[i-1]*i)%MOD;</div>
<div>
}</div>
<div>
long long fermet(long long x){</div>
<div>
long long a=1,p=x,n=MOD-2;</div>
<div>
while(n){</div>
<div>
if(n&1)</div>
<div>
a=(a*p)%MOD;</div>
<div>
p=(p*p)%MOD;</div>
<div>
n>>=1;</div>
<div>
}</div>
<div>
return a;</div>
<div>
}</div>
<div>
int main(){</div>
<div>
int t,a,b;</div>
<div>
long long c,d;</div>
<div>
fact() ;</div>
<div>
scanf("%d",&t);</div>
<div>
while(t--){</div>
<div>
scanf("%d %d",&a,&b);</div>
<div>
c=(fermet(ar[a])*fermet(ar[b]))%MOD;</div>
<div>
d=(ar[a+b]*c)%MOD;</div>
<div>
printf("%lld\n",d);</div>
<div>
}</div>
<div>
return 0;</div>
<div>
}</div>
</div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-86038830056855280712014-12-29T10:26:00.001-08:002014-12-29T10:26:28.888-08:00Balanced base-3<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/TAP2014B/" target="_blank">problem statement is here</a></h3>
<div>
<div>
#include<stdio.h></div>
<div>
<br /></div>
<div>
int main() {</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>int t,y,z,n,ar[10000],i;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&t);</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(t--){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&n);</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>z=0;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(n){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[z]=n%3;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>z++;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>n/=3;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[z]=0;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<=z;i++){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(ar[i]==2){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[i]=-1;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[i+1]++;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}else if(ar[i]==3){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[i]=0;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>ar[i+1]++;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>y=0;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=z;i>=0;i--){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(ar[i]!=0){</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>y=1;</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(ar[i]==1) </div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("+");</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>else if(ar[i]==-1)</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("-");</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>else if(y==1) </div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("0");</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("\n");</div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<span class="Apple-tab-span" style="white-space: pre;"> </span></div>
<div>
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;</div>
<div>
}</div>
</div>
<div>
<br /></div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-77107969653697556682014-12-29T08:11:00.000-08:002014-12-29T08:28:26.658-08:00Tulip And Numbers<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/submit/TULIPNUM/" target="_blank">problem statement is here</a></h3>
<div>
#include<stdio.h><br />
int main(){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>int a,b,c,d,i,j,n,m,t,ar,x=1,br[100005];<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&t);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>while(t--){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d %d",&n,&m);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&ar);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>a=ar;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>br[0]=0;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>br[1]=1;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=1;i<n;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&ar);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(a==ar){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>br[i+1]=br[i];<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}else{<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>br[i+1]=br[i]+1;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>a=ar;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("Case %d:\n",x);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>x++;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=0;i<m;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d %d",&a,&b);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(a==1){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>c=br[b];<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}else{<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(br[a]==br[a-1]){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>c=br[b]-br[a-1]+1;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}else{<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>c=br[b]-br[a-1];<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("%d\n",c);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span><br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>return 0;<br />
}</div>
</div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-17859303244184787192014-11-14T04:53:00.003-08:002014-11-14T04:53:45.249-08:00D - Playing with Marbles<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/BOMARBLE/" target="_blank">problem statement is here</a></h3>
<br />
#include<stdio.h><br />
int main()<br />
{<br />
long long int s,n,j,x;<br />
while (1)<br />
{<br />
s=0;<br />
scanf("%lld",&n);<br />
if(n==0)<br />
break;<br />
else<br />
{<br />
x=n+1;<br />
s=(3*x*x-x)/2;<br />
}<br />
printf("%lld\n",s);<br />
}<br />
return 0;<br />
}<br />
<br /></div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0tag:blogger.com,1999:blog-4866159599909787379.post-23781547889086456482014-11-14T04:51:00.003-08:002014-11-14T04:51:58.335-08:00Board<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
<a href="http://www.spoj.com/problems/BOARD1/" target="_blank">problem statement is here</a></h3>
<br />
#include <stdio.h><br />
<br />
long long int dp[10010]={0};<br />
int t,n;<br />
<br />
long long int min(long long int a,long long int b){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>return a > b ? b : a;<br />
}<br />
<br />
int main(){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>int i, h,j,z,m;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>long long int ar[10000],sum=0,min=100000000;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d", &t);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%d",&z);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=1;i<t;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>scanf("%lld",&ar[i]);<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>sum+=ar[i];<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(i=1;i<t;i++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>m=i;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(j=1;j<=z;j++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(m>=1){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(dp[m-1]<min){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>min=dp[m-1];<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>m--;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>dp[i]=min+ar[i];<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>min=100000000;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>for(j=1;j<=z;j++){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>if(dp[t-j]<min){<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>min=dp[t-j];<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>}<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>sum-=min;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>printf("%lld\n",sum);<br />
return 0;<br />
}<br />
<br /></div>
whishkyhttp://www.blogger.com/profile/14897454400996798149noreply@blogger.com0