Optimal channel allocation is a key performance engineering aspect in single-carrier frequency-division multiple access (SC-FDMA). It is of significance to consider minimum sum power (Min-Power), subject to meeting specified user's demand, since mobile users typically employ battery-powered handsets. In this paper, we prove that Min-Power is polynomial-time solvable for interleaved SC-FDMA (IFDMA). Then we propose a channel allocation algorithm for IFDMA, which is guaranteed to achieve global optimum in polynomial time. We numerically compare the proposed algorithm with optimal localized SC-FDMA (LFDMA) for Min-Power. The results show that LFDMA outperforms IFDMA in the maximal supported user demand. When the user demand can be satisfied in both LFDMA and IFDMA, LFDMA performs slightly better than IFDMA. However Min- Power is polynomial-time solvable for IFDMA whereas it is not for LFDMA.