Mryntu

Providence Pentominoes Puzzle By Andrew Bradburn (Jigsaw)

Will this character get back his Infinity Stone?

A ​Note ​on ​N!

How do Bards prepare spells?

Trainer for recumbent bikes

Why was the Spitfire's elliptical wing almost uncopied by other aircraft of World War 2?

Will tsunami waves travel forever if there was no land?

Help to reproduce a tcolorbox with a decoration

Sci-fi novel series with instant travel between planets through gates. A river runs through the gates

Why do 401k up to company match, then fill Roth IRA, then finish filling 401k?

Can solid acids and bases have pH values? If not, how are they classified as acids or bases?

Mac Pro install disk keeps ejecting itself

Is DC-to-DC (24 V to 12 V) buck conversion typically more efficient than AC-to-DC (110 V to 12 V) conversion?

Unexpected email from Yorkshire Bank

Alternatives to Overleaf

How can Republicans who favour free markets, consistently express anger when they don't like the outcome of that choice?

Minimum value of 4 digit number divided by sum of its digits

Who is the Umpire in this picture?

Rivers without rain

Counterexample: a pair of linearly ordered sets that are isomorphic to subsets of the other, but not isomorphic between them

Question relating to a number theoretic function

Does this extra sentence in the description of the warlock's Eyes of the Rune Keeper eldritch invocation appear in any official reference?

Was it really necessary for the Lunar module LM to have 2 stages?

With a Canadian student visa, can I spend a night at Vancouver before continuing to Toronto?

Finding an element in array, whose index number and element value same

Linearithmic lower bound for 1-D “distinct” closest pair of points problemFind The missing number in range [0,n]Divide-and-Conquer ExerciseFinding a segment which has equal number of segments before and after itFind the index of minimum number that is greater than key given of a sorted array, does these two functions return same result?Creating an O(n log n) time and O(n) space algorithm for counting pairs in an arrayFinding a small element in a changing arraySearching a sorted array to find the $k$ closest values to a target value $T$Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array?Min no.of operations required to convert an array to which it should contain elements of equal frequency

1

$begingroup$

Given a sorted array of distinct integer $A[1,2.....n]$ the tightest upper bound to check the existence of any index $I$, for which $A[I]=I$ is equal to _______________ ?

---

I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A[I]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?

algorithms

share|cite|improve this question

edited 18 mins ago

Mr. Sigma.

734626

asked 7 hours ago

SresthaSrestha

286

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You have to find i.
  $endgroup$
  – gnasher729
  15 mins ago
  

  
  
  
  

add a comment | 

1

$begingroup$

Given a sorted array of distinct integer $A[1,2.....n]$ the tightest upper bound to check the existence of any index $I$, for which $A[I]=I$ is equal to _______________ ?

---

I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A[I]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?

algorithms

share|cite|improve this question

edited 18 mins ago

Mr. Sigma.

734626

asked 7 hours ago

SresthaSrestha

286

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You have to find i.
  $endgroup$
  – gnasher729
  15 mins ago
  

  
  
  
  

add a comment | 

$begingroup$

Given a sorted array of distinct integer $A[1,2.....n]$ the tightest upper bound to check the existence of any index $I$, for which $A[I]=I$ is equal to _______________ ?

---

I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A[I]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?

algorithms

share|cite|improve this question

edited 18 mins ago

Mr. Sigma.

734626

asked 7 hours ago

SresthaSrestha

286

$endgroup$

share|cite|improve this question

edited 18 mins ago

Mr. Sigma.

734626

asked 7 hours ago

SresthaSrestha

286

share|cite|improve this question

edited 18 mins ago

Mr. Sigma.

734626

asked 7 hours ago

SresthaSrestha

286

edited 18 mins ago

Mr. Sigma.

734626

edited 18 mins ago

Mr. Sigma.

734626

asked 7 hours ago

SresthaSrestha

286

asked 7 hours ago

SresthaSrestha

286

2 Answers
2

active

oldest

votes

2

$begingroup$

If the array had $A[i]=i, foralli$, then the complexity would have been $theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1. The complexity is indeed $theta(log_2n)$

share|cite|improve this answer

edited 16 mins ago

answered 6 hours ago

Mr. Sigma.Mr. Sigma.

734626

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is binary search always take an element a[I]=I?? ok, tell me one thing , if in this algorithm, I want T.C.=O(1), what modification needed for this code?
  $endgroup$
  – Srestha
  5 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You can't achieve in $O(1)$ time. E.g, 1,4,6,9,12 (index starting with 1)
  $endgroup$
  – Mr. Sigma.
  3 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Mr. Sigma, I have not got the point. Here it is told a[I]=I, that means a[1]=1, a[2]=2,a[3]=3......only this type of sequence possible here. Then how r u telling a[1]=1,a[2]=4, a[3]=6 .... is a possible sequence.
  $endgroup$
  – Srestha
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha Your question specifies that the input is a sorted array of distinct integers - it does not specify that, in the input, $A[i] = i$. If this is the case you should update your question. However, this would make the problem trivial.
  $endgroup$
  – AcId
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You have understood the question wrongly. Question involving $A[i]=i, foralli$ would be very trivial.
  $endgroup$
  – Mr. Sigma.
  57 mins ago
  
  

  
  
  
  

 | 
show 7 more comments

0

$begingroup$

Take the hints. The integers can be positive or negative, but they are distinct. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 < a2 < a3 < ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?

(If you figure that out, the solution is trivial).

share|cite|improve this answer

answered 10 mins ago

gnasher729gnasher729

12.3k1318

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f108642%2ffinding-an-element-in-array-whose-index-number-and-element-value-same%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

If the array had $A[i]=i, foralli$, then the complexity would have been $theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1. The complexity is indeed $theta(log_2n)$

share|cite|improve this answer

edited 16 mins ago

answered 6 hours ago

Mr. Sigma.Mr. Sigma.

734626

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is binary search always take an element a[I]=I?? ok, tell me one thing , if in this algorithm, I want T.C.=O(1), what modification needed for this code?
  $endgroup$
  – Srestha
  5 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You can't achieve in $O(1)$ time. E.g, 1,4,6,9,12 (index starting with 1)
  $endgroup$
  – Mr. Sigma.
  3 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Mr. Sigma, I have not got the point. Here it is told a[I]=I, that means a[1]=1, a[2]=2,a[3]=3......only this type of sequence possible here. Then how r u telling a[1]=1,a[2]=4, a[3]=6 .... is a possible sequence.
  $endgroup$
  – Srestha
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha Your question specifies that the input is a sorted array of distinct integers - it does not specify that, in the input, $A[i] = i$. If this is the case you should update your question. However, this would make the problem trivial.
  $endgroup$
  – AcId
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You have understood the question wrongly. Question involving $A[i]=i, foralli$ would be very trivial.
  $endgroup$
  – Mr. Sigma.
  57 mins ago
  
  

  
  
  
  

 | 
show 7 more comments

2

$begingroup$

If the array had $A[i]=i, foralli$, then the complexity would have been $theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1. The complexity is indeed $theta(log_2n)$

share|cite|improve this answer

edited 16 mins ago

answered 6 hours ago

Mr. Sigma.Mr. Sigma.

734626

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is binary search always take an element a[I]=I?? ok, tell me one thing , if in this algorithm, I want T.C.=O(1), what modification needed for this code?
  $endgroup$
  – Srestha
  5 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You can't achieve in $O(1)$ time. E.g, 1,4,6,9,12 (index starting with 1)
  $endgroup$
  – Mr. Sigma.
  3 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Mr. Sigma, I have not got the point. Here it is told a[I]=I, that means a[1]=1, a[2]=2,a[3]=3......only this type of sequence possible here. Then how r u telling a[1]=1,a[2]=4, a[3]=6 .... is a possible sequence.
  $endgroup$
  – Srestha
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha Your question specifies that the input is a sorted array of distinct integers - it does not specify that, in the input, $A[i] = i$. If this is the case you should update your question. However, this would make the problem trivial.
  $endgroup$
  – AcId
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Srestha You have understood the question wrongly. Question involving $A[i]=i, foralli$ would be very trivial.
  $endgroup$
  – Mr. Sigma.
  57 mins ago
  
  

  
  
  
  

 | 
show 7 more comments

$begingroup$

If the array had $A[i]=i, foralli$, then the complexity would have been $theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1. The complexity is indeed $theta(log_2n)$

share|cite|improve this answer

edited 16 mins ago

answered 6 hours ago

Mr. Sigma.Mr. Sigma.

734626

$endgroup$

share|cite|improve this answer

edited 16 mins ago

answered 6 hours ago

Mr. Sigma.Mr. Sigma.

734626

answered 6 hours ago

Mr. Sigma.Mr. Sigma.

734626

answered 6 hours ago

Mr. Sigma.Mr. Sigma.

734626

0

$begingroup$

Take the hints. The integers can be positive or negative, but they are distinct. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 < a2 < a3 < ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?

(If you figure that out, the solution is trivial).

share|cite|improve this answer

answered 10 mins ago

gnasher729gnasher729

12.3k1318

$endgroup$

add a comment | 

0

$begingroup$

Take the hints. The integers can be positive or negative, but they are distinct. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 < a2 < a3 < ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?

(If you figure that out, the solution is trivial).

share|cite|improve this answer

answered 10 mins ago

gnasher729gnasher729

12.3k1318

$endgroup$

add a comment | 

$begingroup$

Take the hints. The integers can be positive or negative, but they are distinct. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 < a2 < a3 < ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?

(If you figure that out, the solution is trivial).

share|cite|improve this answer

answered 10 mins ago

gnasher729gnasher729

12.3k1318

$endgroup$

share|cite|improve this answer

answered 10 mins ago

gnasher729gnasher729

12.3k1318

answered 10 mins ago

gnasher729gnasher729

12.3k1318

answered 10 mins ago

gnasher729gnasher729

12.3k1318