CODEWITHSUNDEEP
javaalgorithmtime-complexity
Anirudh Balakka
Anirudh Balakka

Reputation: 15

Converting int to string reduces time complexity of calculating its length

The following code block:

Scanner in=new Scanner(System.in);
int n=in.nextInt();
//converting the integer to string and calculating
//its length reduces the complexity
//to O(n) as compared to O(n^2)
String str=Integer.toString(n);
int length=str.length();length-=1;

I found this code here.

My question is how does changing the int to string reduce the time complexity?

Upvotes: 0

Views: 1715

Answers (2)

sjana
sjana

Reputation: 64

Even finding the length of the integer using a simple while loop is O(n), not O(n^2).

Consider the following snippet:

while(n!=0)
{
    n/=10;
    ++count;
}

Upvotes: 0

syntagma
syntagma

Reputation: 24304

The author of that code claims it reduces complexity compared to another solution posted:

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int num,d,rev=0;

  cin>>num;

 // reverse a no.
  while(num!=0)
  {
    d=num%10;
    rev=rev*10+d;
    num=num/10;
  }

  // using digits of reversed no.
  while(rev!=0)
  {
    d=rev%10;
    cout<<d*d; // printing square 
    rev=rev/10;
  }

 return 0;
}

This is false, both solutions have the same complexity, O(n).

Upvotes: 4

Related Questions