{"id":25535,"date":"2017-05-30T18:59:26","date_gmt":"2017-05-30T13:29:26","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25535"},"modified":"2017-05-30T18:59:26","modified_gmt":"2017-05-30T13:29:26","slug":"write-a-program-to-calculate-pow-xn","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/write-a-program-to-calculate-pow-xn\/","title":{"rendered":"Write a program to calculate pow (x,n)"},"content":{"rendered":"

Below solution divides the problem into subproblems of size y\/2 and call the subproblems recursively<\/a>.<\/strong><\/p>\n[ad type=\u201dbanner\u201d]\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%20%0A%2F*%20Function%20to%20calculate%20x%20raised%20to%20the%20power%20y%20*%2F%0Aint%20power(int%20x%2C%20unsigned%20int%20y)%0A%7B%0A%20%20%20%20if%20(y%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20else%20if%20(y%252%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%20power(x%2C%20y%2F2)*power(x%2C%20y%2F2)%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20return%20x*power(x%2C%20y%2F2)*power(x%2C%20y%2F2)%3B%0A%7D%0A%20%0A%2F*%20Program%20to%20test%20function%20power%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20x%20%3D%202%3B%0A%20%20%20%20unsigned%20int%20y%20%3D%203%3B%0A%20%0A%20%20%20%20printf(%22%25d%22%2C%20power(x%2C%20y))%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Time Complexity: <\/strong>O(n)
\nSpace Complexity:<\/strong> O(1)
\nAlgorithmic Paradigm: <\/strong>Divide and conquer.<\/p>\n

Above function can be optimized to O(logn) by calculating power(x, y\/2) only once and storing it.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F*%20Function%20to%20calculate%20x%20raised%20to%20the%20power%20y%20in%20O(logn)*%2F%0Aint%20power(int%20x%2C%20unsigned%20int%20y)%0A%7B%0A%20%20%20%20int%20temp%3B%0A%20%20%20%20if(%20y%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20temp%20%3D%20power(x%2C%20y%2F2)%3B%0A%20%20%20%20if%20(y%252%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%20temp*temp%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20return%20x*temp*temp%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Time Complexity of optimized solution:<\/strong> O(logn)
\nLet us extend the pow function to work for negative y and float x.<\/p>\n[ad type=\u201dbanner\u201d]\n[pastacode lang=\u201dc\u201d manual=\u201d%2F*%20Extended%20version%20of%20power%20function%20that%20can%20work%0A%20for%20float%20x%20and%20negative%20y*%2F%0A%23include%3Cstdio.h%3E%0A%20%0Afloat%20power(float%20x%2C%20int%20y)%0A%7B%0A%20%20%20%20float%20temp%3B%0A%20%20%20%20if(%20y%20%3D%3D%200)%0A%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20temp%20%3D%20power(x%2C%20y%2F2)%3B%20%20%20%20%20%20%20%0A%20%20%20%20if%20(y%252%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%20temp*temp%3B%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if(y%20%3E%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20x*temp*temp%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20(temp*temp)%2Fx%3B%0A%20%20%20%20%7D%0A%7D%20%20%0A%20%0A%2F*%20Program%20to%20test%20function%20power%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20float%20x%20%3D%202%3B%0A%20%20%20%20int%20y%20%3D%20-3%3B%0A%20%20%20%20printf(%22%25f%22%2C%20power(x%2C%20y))%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"

Write a program to calculate pow(x,n) – Divide and Conquer – Above function can be optimized to O(logn) by calculating power(x, y\/2) only once and storing it.<\/p>\n","protected":false},"author":1,"featured_media":26073,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73719],"tags":[73765,73766,73773,73778,73780,73776,73768,73767,73770,73771,73772,73769,73774,73779,73777,73764],"class_list":["post-25535","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-divide-and-conquer","tag-c-program-to-calculate-power-of-a-number","tag-c-program-to-calculate-power-of-a-number-using-recursion","tag-c-program-to-find-power-of-a-number-using-for-loop","tag-c-program-to-find-power-of-a-number-using-function","tag-c-program-to-find-power-of-a-number-without-using-pow-function","tag-c-programming-power-function","tag-calculate-power-of-a-number","tag-how-to-calculate-power","tag-how-to-calculate-power-in-c","tag-how-to-calculate-power-number","tag-how-to-calculate-power-of-2","tag-how-to-calculate-power-of-a-number","tag-implement-powx","tag-implement-power-function-leetcode","tag-implement-power-function-using-binary-search","tag-write-a-program-to-calculate-powx"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25535","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25535"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25535\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/26073"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25535"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25535"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25535"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}